Алгоритм Поліґа — Геллмана () — спеціалізований алгоритм дискретного логарифмування, який отримує перевагу від факторизації порядку мультиплікативної групи де — гладке число. Нехай буде розкладом на прості множники. Якщо тоді підхід полягає в визначенні для і тоді отримання Кожен з визначається обчисленням цифр для його -арного представлення: де
Алгоритм ВХІД: твірний елемент циклічної групи порядку і елемент
ВИХІД: дискретний логарифм
Знайти розкладення на прості множники для : де Для від до робимо наступне: (Обчислити де ) Покласти і Обчислити (Обчислити ) Для від для робимо наступне: Обчислити i Обчислити Встановити Використати, наприклад, алгоритм Гаусса для обчислення цілого такий що для Повернути.
Складність У найгіршому випадку складність алгоритму становить для групи порядку , але алгоритм ефективніший, коли порядок є гладким числом. А саме, якщо є розкладенням на прості множники , тоді складність можна виразити як Menezes, et. al 1997, pg. 108.
Приклад групи, де алгоритм ефективний, такий. Розглянемо групу , де є простим завдовжки цифр:
Порядок такий . Із того, що найбільший простий дільник для лише 350377, застосовуючи алгоритм Поліґа—Геллмана порівняно просто обчислити логарифми в цій групі.
Примітки
Джерела