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