Проблема дискретного логарифмування (стр. 3 из 3)

(7)

Позначимо в загальному вигляді

(8)

Суть

-методу Полларда розв’язання порівняння (1) міститься в наступному. Знайдемо деяку функцію , вибравши де порядок точки на ЕК

(9)

Далі знайдемо

послідовність:

...,

для пар

, таких що:

(10)

Рекомендується в простих випадках (при відносно невеликих

) послідовність розраховувати у вигляді:

(11)

При цьому

та складають частини області . Якщо область рівномірно ділиться, то (8.11) має вигляд:

(12)

При побудові множини

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

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

(13)

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

(14)

і далі

(15)

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

(16)

Більш ефективним є розрахунок

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

(17)

причому

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

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

(18)

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

(19)

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

Із (18) та (19) випливає, що задача пошуку пар

та може бути розпаралелено на процесорів, тоді

. (20)

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

(21)

а при розпаралелюванні на

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

. (22)

Під час розв’язання задач важливо успішно вибрати

. Значення рекомендується вибирати у вигляді

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

де

Размещено на