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

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

Алгоритм

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

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

1. Знайти розкладення на прості множники для ${\displaystyle n}$: ${\displaystyle n=p_{1}^{e_{1}}p_{2}^{e_{2}}\dots p_{r}^{e_{r}},}$ де ${\displaystyle e_{i}\geq 1.}$
2. Для ${\displaystyle i}$ від ${\displaystyle 1}$ до ${\displaystyle r}$ робимо наступне:

   (Обчислити ${\displaystyle x_{i}=l_{0}+l_{1}p_{i}+\dots +l_{e_{i}-1}p_{i}^{e_{i}-1},}$ де ${\displaystyle x_{i}=x\mod p_{i}^{e_{i}}}$)

   1. Покласти ${\displaystyle \gamma \gets 1}$ і ${\displaystyle l_{-1}\gets 0.}$
   2. Обчислити ${\displaystyle \alpha \gets \alpha n/p_{i}.}$
   3. (Обчислити ${\displaystyle l_{j}}$) Для ${\displaystyle j}$ від ${\displaystyle 0}$ для ${\displaystyle e_{i}-1}$ робимо наступне:

      Обчислити ${\displaystyle \gamma \gets \gamma \alpha ^{l_{j-1}p_{i}^{j-1}}}$ i ${\displaystyle {\bar {\beta }}\gets (\beta \gamma ^{-1})^{n/p_{i}^{j+1}}.}$

      Обчислити ${\displaystyle l_{j}\gets \log _{\alpha }\beta .}$

   4. Встановити ${\displaystyle x_{i}\gets l_{0}+l_{1}p_{i}+\dots +l_{e_{i}-1}p_{i}^{e_{i}-1}.}$
3. Використати, наприклад, алгоритм Гаусса для обчислення цілого ${\displaystyle x,0\leq x\leq n-1,}$ такий що ${\displaystyle x\equiv x_{i}{\pmod {p_{i}^{e_{i}}}}}$ для ${\displaystyle 1\leq i\leq r.}$
4. Повернути${\displaystyle (x)}$.

Складність

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

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

${\displaystyle p=22708823198678103974314518195029102158525052496759285596453269189798311427475159776411276642277139650833937.}$

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

Примітки

1. Menezes, et. al 1997, pg. 108

Джерела

• 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.