Алгоритм Поліґа — Геллмана

Алгоритм Поліґа — Геллмана (англ. Pohlig–Hellman algorithm) — спеціалізований алгоритм дискретного логарифмування, який отримує перевагу від факторизації порядку $n$ мультиплікативної групи $G,$ де $n$ — гладке число.
Нехай $n=p_{1}^{e_{1}}p_{2}^{e_{2}}\dots p_{r}^{e_{r}}$ буде розкладом $n$ на прості множники. Якщо $x=\log _{\alpha }\beta ,$ тоді підхід полягає в визначенні $x_{i}=x\mod p_{i}^{e_{i}}$ для $1\leq i\leq r,$ і тоді отримання $x.$ Кожен з $x_{i}$ визначається обчисленням цифр $l_{0},l_{1},\dots ,l_{e_{i}-1}$ для його $p_{i}$ -арного представлення: $x_{i}=l_{0}+l_{1}p_{i}+\dots +l_{e_{i}-1}p_{e_{i}-1},$ де $0\leq l_{j}\leq p_{i}-1.$

Алгоритм[ред. | ред. код]

ВХІД: твірний елемент $\alpha$ циклічної групи $G$ порядку $n,$ і елемент $\beta \in G.$

ВИХІД: дискретний логарифм $x=\log _{\alpha }\beta .$

Знайти розкладення на прості множники для $n$ : $n=p_{1}^{e_{1}}p_{2}^{e_{2}}\dots p_{r}^{e_{r}},$ де $e_{i}\geq 1.$
Для $i$ $i$ від $1$ $1$ до $r$ $r$ робимо наступне:
(Обчислити $x_{i}=l_{0}+l_{1}p_{i}+\dots +l_{e_{i}-1}p_{i}^{e_{i}-1},$ де $x_{i}=x\mod p_{i}^{e_{i}}$ )
1. Покласти $\gamma \gets 1$ і $l_{-1}\gets 0.$
2. Обчислити $\alpha \gets \alpha n/p_{i}.$
3. (Обчислити $l_{j}$ ) Для $j$ від $0$ для $e_{i}-1$ робимо наступне:
  Обчислити $\gamma \gets \gamma \alpha ^{l_{j-1}p_{i}^{j-1}}$ i ${\bar {\beta }}\gets (\beta \gamma ^{-1})^{n/p_{i}^{j+1}}.$
  
  Обчислити $l_{j}\gets \log _{\alpha }\beta .$
4. Встановити $x_{i}\gets l_{0}+l_{1}p_{i}+\dots +l_{e_{i}-1}p_{i}^{e_{i}-1}.$
Використати, наприклад, алгоритм Гаусса для обчислення цілого $x,0\leq x\leq n-1,$ такий що $x\equiv x_{i}{\pmod {p_{i}^{e_{i}}}}$ для $1\leq i\leq r.$
Повернути $(x)$ .

Складність[ред. | ред. код]

У найгіршому випадку складність алгоритму становить $O({\sqrt {n}})$ для групи порядку $n$ , але алгоритм ефективніший, коли порядок є гладким числом. А саме, якщо $\prod _{i}p_{i}^{e_{i}}$ є розкладенням на прості множники $n$ , тоді складність можна виразити як $O(\sum _{i}{e_{i}(\log n+{\sqrt {p}}_{i})})$ ^[1].

Приклад групи, де алгоритм ефективний, такий. Розглянемо групу $\mathrm {Z} _{p}^{*}$ , де $p$ є простим завдовжки $107$ цифр:

p=22708823198678103974314518195029102158525052496759285596453269189798311427475159776411276642277139650833937.

Порядок $\mathbb {Z} _{p}^{*}$ такий $n=p-1=2^{4}\times 104729^{8}\times 224737^{8}\times 350377^{4}$ . Із того, що найбільший простий дільник для $p-1$ лише 350377, застосовуючи алгоритм Поліґа—Геллмана порівняно просто обчислити логарифми в цій групі.