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

Алгоритм Поліґа — Геллмана (Шаблон:Lang-en) — спеціалізований алгоритм дискретного логарифмування, який отримує перевагу від факторизації порядку $n$ мультиплікативної групи $G,$ де $n$ — гладке число.
Нехай $n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{r}^{e_{r}}$ буде розкладом $n$ на прості множники. Якщо $x = \log_{α} β,$ тоді підхід полягає в визначенні $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 .$

Алгоритм

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

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

Знайти розкладення на прості множники для $n$ : $n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{r}^{e_{r}},$ де $e_{i} \geq 1 .$
Для 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. Покласти $γ \leftarrow 1$ і $l_{- 1} \leftarrow 0 .$
2. Обчислити $α \leftarrow α n / p_{i} .$
3. (Обчислити $l_{j}$ ) Для $j$ від $0$ для $e_{i} - 1$ робимо наступне:
  Обчислити $γ \leftarrow γ α^{l_{j - 1} p_{i}^{j - 1}}$ i $\bar{β} \leftarrow (β γ^{- 1})^{n / p_{i}^{j + 1}} .$
  
  Обчислити $l_{j} \leftarrow \log_{α} β .$
4. Встановити $x_{i} \leftarrow 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} (\mod 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].

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

p = 22708823198678103974314518195029102158525052496759285596453269189798311427475159776411276642277139650833937 .

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

Примітки

Шаблон:Reflist

Джерела

Шаблон:Алгоритми теорії чисел

↑ Menezes, et. al 1997, pg. 108

[Menezes97p108-1] Menezes, et. al 1997, pg. 108

[1]

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

Зміст