Алгоритм Полига-Хеллмана

Алгоритм Полига - Хеллмана (также называемый алгоритм Силвера — Полига — Хеллмана) — детерминированный алгоритм дискретного логирифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный алгоритм является полиномиальным.

История

Данный алгоритм был впервые описан американскими математиками Роланом Силвером (Roland Silver), Стефаном Полигом (Stephan Pohlig) и Мартином Хеллманом (Martin Hellman) в 1978 году в статье «An improved algorithm for computing logarithms over GF(p) and its cryptographic significance». Важной особенностью этого метода является то, что для простых чисел специального вида, можно находить дискретный логарифм за полиномиальное время.

Исходные данные

Пусть задано сравнение

$a^x\equiv b\mod{p},$

(1)

и известно разложение p − 1на простые множители:

$p-1=\prod\limits_{i=1}^{s}q_i^{\alpha_i}.$

Необходимо найти натуральное число x, удовлетворяющее сравнению (1). Заметим, что на практике всегда рассматривается случай, когда a — первообразный корень по модулю p. В этом случае сравнение (1) имеет решение при любом b, взаимно простом с p.

Идея алгоритма

Суть алгоритма в том, что достаточно найти x по модулям $q_i^{\alpha_i}$ для всех i, а затем решение исходного сравнения можно найти с помощью китайской теореме об остатках. Чтобы найти x по каждому из таких модулей, нужно решить сравнение:

$(a^{\frac{p-1}{ q_i^{\alpha_i}}})^x\equiv b^{\frac{p-1}{q_i^{\alpha_i}}}\mod{p}.$

(2)

Данное сравнение решается за полиномиальное время в случае, если q_i — небольшое (то есть, не превосходит (logp)^c, где c — некоторая константа).

Описание алгоритма

1 (составление таблицы). Составить таблицу значений {ri,j}, где
 $r_{i,j}=a^{j\frac{p-1}{q_i}},$
 $i\in\{1,...,s\},$
 $j\in\{1,...,q_i-1\}.$

NB! i перебирает сами простые множители q₁,q₂(…,q_s) а не 1..S а j может быть и нулем.

2 (нахождение $\log_a{b}\mod{q_i^{\alpha_i}}$). 
Для i от 1 до s:
 Пусть
  $x\equiv\log_a{b}\mod{q_i^{\alpha_i}}\equiv x_0+x_1q_i+...+x_{\alpha-1}q_i^{\alpha-1}\mod{q_i^{\alpha_i}},$
 где
  $0\leq x_i\leq q_i-1.$
 Тогда из (1) следует, что
  $b^{\frac{p-1}{q_i}}\equiv a^{x_0\frac{p-1}{q_i}}\mod{p}$
 С помощью таблицы, составленной на шаге 1, находим x0.
 Для j от 1 до α − 1 
  Рассматриваем сравнение
   $(ba^{-x_0-...-x_{j-1}})^{\frac{p-1}{q_i^{j+1}}}\equiv a^{x_i\frac{p-1}{q_i}}\mod{p}$
  Решение опять же находится по таблице
 Конец цикла по i
Конец цикла по j

3 (нахождение ответа). Найдя $\log_a{b}\mod{q_i^{\alpha_i}}$ для всех i, находим $\log_a{b}\mod{p-1}$ по китайской теореме об остатках.

Сложность алгоритма

Решение сравнения (1) находится за $O(\sum\limits_{i=1}^{s}\alpha_i(\log{p}+q_i))$ арифметических операций (см. [1]).

Можно также сказать, что решение находится за $O(\sqrt{q})$ арифметических операций, где q — наибольший простой делитель p-1 (см. [3]).

Если все простые делители q_i не превосходят $(\log{p})^{c_1},$ то алгоритм Полига-Хеллмана является полиномиальным и имеет сложность $O((\log{p})^{c_2})$, где c_1,2 — некоторые положительные постоянные.

Применение

Как уже было сказано, алгоритм Полига-Хеллмана крайне эффективен, если p-1 раскладывается на небольшие простые множители. Например, для чисел вида $p=2^\alpha+1,\ p=2^\alpha3^\beta+1$ и т. д. Если же у p-1 есть большой простой делитель $q>p^c,\ 0<c<1,$ то алгоритм имеет экспоненциальную сложность. Это очень важно учитывать при выборе параметров криптографических схем.

Замечание

Для применения алгоритма Полига-Хеллмана необходимо знать разложение p-1 на множители. В общем случае задача факторизации — достаточно трудоёмкая, однако если делители числа — небольшие (в том смысле, о котором сказано выше), то это число можно быстро разложить на множители даже методом последовательного деления. Таким образом, в том случае, когда эффективен алгоритм Полига-Хеллмана, необходимость факторизации не усложняет задачу.

Литература

1. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — Москва: МЦМНО, 2003. — С. 328. — ISBN 5-94057-103-4
2. Pohlig S., Hellmann M. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. — IEEE Trans. Inform. Theory, V.5, 1978. — С. 106-110.
3. Odlyzko A. M. Discrete logarithms in finite fields and their cryptographic significance // Advances in Crytology: Proceedings of EuroCrypt’84 /Thomas Beth, Norbert Cot, and Igemar Ingemarsson, editors. Berlin: Springer-Verlag, 1984 (Lect. Notes in Computer Science; V. 209). P. 224—316.