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

(4)
Для ЕК над
полем
виду
![]()
причому
,
то для двох
точок
та
таких, що
![]()
виходить
(5)
примітивний
поліном m-го
степеня;
(6)
Для
розв’язання
задачі пошуку
конфіденційного
ключа
в порівнянні
(1) розглянемо
метод
Полларда над
простимо полем
Нехай
–
базова точка,
відкритий
ключ, шукатимемо
пари цілих
та
,
таких що
(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)
Під час
розв’язання
задач важливо
успішно вибрати
.
Значення
рекомендується
вибирати у
вигляді
![]()
також можна
вибрати як
![]()
де
![]()
Размещено на /