Алгоритм Поліґа — Геллмана (англ. Pohlig–Hellman algorithm) — спеціалізований алгоритм дискретного логарифмування, який отримує перевагу від факторизації порядку
мультиплікативної групи
де
— гладке число.
Нехай
буде розкладом
на прості множники. Якщо
тоді підхід полягає в визначенні
для
і тоді отримання
Кожен з
визначається обчисленням цифр
для його
-арного представлення:
де
ВХІД: твірний елемент
циклічної групи
порядку
і елемент
ВИХІД: дискретний логарифм
- Знайти розкладення на прості множники для
:
де ![{\displaystyle e_{i}\geq 1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74ff86fe81ebbd9c9eded173467fc0ba96ff4bd4)
- Для
від
до
робимо наступне:
- (Обчислити
де
)
- Покласти
і ![{\displaystyle l_{-1}\gets 0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91cbe9323939998325d28fe9eae6c8c4b4b25de1)
- Обчислити
![{\displaystyle \alpha \gets \alpha n/p_{i}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/213b0a76858764d07ae0031b3ea669fbfed93253)
- (Обчислити
) Для
від
для
робимо наступне:
- Обчислити
i ![{\displaystyle {\bar {\beta }}\gets (\beta \gamma ^{-1})^{n/p_{i}^{j+1}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55d33649d8299979b754d5674213c2776fa6e1f4)
- Обчислити
![{\displaystyle l_{j}\gets \log _{\alpha }\beta .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/578285f080738386a1d26f2a7d39b10e7453f721)
- Встановити
![{\displaystyle x_{i}\gets l_{0}+l_{1}p_{i}+\dots +l_{e_{i}-1}p_{i}^{e_{i}-1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a66dd221ccdb5d0419fadf216cf297e38c9e2e6)
- Використати, наприклад, алгоритм Гаусса для обчислення цілого
такий що
для ![{\displaystyle 1\leq i\leq r.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ff621a117be146b7522fe2b9d3df9a0c443071d)
- Повернути
.
У найгіршому випадку складність алгоритму становить
для групи порядку
, але алгоритм ефективніший, коли порядок є гладким числом. А саме, якщо
є розкладенням на прості множники
, тоді складність можна виразити як
[1].
Приклад групи, де алгоритм ефективний, такий. Розглянемо групу
, де
є простим завдовжки
цифр:
![{\displaystyle p=22708823198678103974314518195029102158525052496759285596453269189798311427475159776411276642277139650833937.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c1b1e860514da0d46f2b1083eb70bde7b523628)
Порядок
такий
. Із того, що найбільший простий дільник для
лише 350377, застосовуючи алгоритм Поліґа—Геллмана порівняно просто обчислити логарифми в цій групі.