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

ВХІД: твірний елемент ${\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=227088231986781039743145181950291021585250524967592855}$

${\displaystyle 96453269189798311427475159776411276642277139650833937.}$

Порядок ${\displaystyle \mathbb {Z} _{p}^{*}}$ такий ${\displaystyle n=p-1=2^{4}\times 104729^{8}\times 224737^{8}\times 350377^{4}.}$ З того, що найбільший простий дільник для ${\displaystyle 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. IEEE Transactions on Information Theory (24): 106–110.
• Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (1997). Number-Theoretic Reference Problems. Handbook of Applied Cryptography. CRC Press. с. 107–109. ISBN 0-8493-8523-7.