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

Алгоритм Поліґа — Геллмана (англ. 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 .$

1. Знайти розкладення на прості множники для $n$: $n=p_{1}^{e_{1}}p_{2}^{e_{2}}\dots p_{r}^{e_{r}},$ де $e_{i}\geq 1.$
2. Для $i$ від $1$ до $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}.$
3. Використати, наприклад, алгоритм Гаусса для обчислення цілого $x,0\leq x\leq n-1,$ такий що $x\equiv x_{i}{\pmod {p_{i}^{e_{i}}}}$ для $1\leq i\leq r.$
4. Повернути$(x)$.

Складність

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

Приклад групи, де алгоритм ефективний, такий. Розглянемо групу $\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, застосовуючи алгоритм Поліґа—Геллмана порівняно просто обчислити логарифми в цій групі.

Джерела

• Mollin, Richard (18 вересня 2006). An Introduction To Cryptography (вид. 2nd). Chapman and Hall/CRC. с. 344. ISBN 978-1-58488-618-1.
• S. Pohlig and M. Hellman (1978). An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance (PDF). IEEE Transactions on Information Theory (24): 106—110. Архів оригіналу (PDF) за 27 лютого 2012. Процитовано 22 серпня 2012.
• Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (1997). Number-Theoretic Reference Problems (PDF). Handbook of Applied Cryptography. CRC Press. с. 107–109. ISBN 0-8493-8523-7.