Контрольная работа: Проблема дискретного логарифмування

При побудові множини пошук буде успішним, якщо ми знайдемо

що еквівалентно знаходженню

(13)

Зробивши прості перетворення, маємо:

(14)

і далі

(15)

З (1) та (15) випливає, що

(16)

Більш ефективним є розрахунок з розбиванням інтервалу на інтервалів. Для реальних значень рекомендується . У цьому випадку замість (11) маємо

(17)

причому та є випадкові цілі із інтервалу .

У випадку (17) розв'язок знаходиться як і раніше у вигляді (12), а потім (17). З урахуванням позначень в (17)

(18)

Успішне розв'язання задачі дискретного логарифму в групі точок ЕК вимагає

(19)

операцій на ЕК.

Із (18) та (19) випливає, що задача пошуку пар та може бути розпаралелено на процесорів, тоді

. (20)

Розроблено методики та алгоритми, які дозволяють розв'язати задачу (1) зі складністю

(21)

а при розпаралелюванні на процесорах складність визначається, як

. (22)

Під час розв’язання задач важливо успішно вибрати . Значення рекомендується вибирати у вигляді

також можна вибрати як

де

Размещено на