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

Алгоритм Полига — Хеллмана — это метод дискретного логарифмирования в конечной циклической группе, который позволяет эффективно вычислять дискретный логарифм, если порядок группы раскладывается на небольшие простые множители. Алгоритм был предложен американскими математиками Стивеном Полигом и Мартином Хеллманом в 1978 году. Он не является универсальным, но в определённых условиях (например, при использовании групп с гладким порядком) значительно ускоряет вычисления по сравнению с полным перебором.

Постановка задачи

Дискретное логарифмирование в конечной циклической группе \( G \) порядка \( n \) заключается в нахождении целого числа \( x \) ( \( 0 \le x < n \) ) такого, что для заданных элементов \( g \) и \( h \) выполняется равенство \( g^x = h \). Здесь \( g \) — образующий элемент группы. Задача дискретного логарифмирования лежит в основе многих криптографических систем, включая протокол Диффи — Хеллмана и алгоритм Эль-Гамаля. Сложность этой задачи в общем случае считается высокой, что обеспечивает стойкость таких систем. Однако алгоритм Полига — Хеллмана показывает, что если \( n \) имеет только малые простые делители, то задача становится решаемой за полиномиальное время.

Основная идея алгоритма

Алгоритм основан на китайской теореме об остатках. Если порядок группы \( n \) имеет разложение на простые множители:

\[ n = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_k^{e_k}, \]

то дискретный логарифм \( x \) по модулю \( n \) можно восстановить по его значениям по модулю каждого из простых сомножителей \( p_i^{e_i} \). Для этого сначала вычисляются частные дискретные логарифмы \( x_i \equiv x \pmod{p_i^{e_i}} \), а затем с помощью китайской теоремы об остатках находится \( x \).

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

Шаг 1. Разложение порядка группы

Пусть порядок группы \( n \) известен. Выполняется его факторизация на простые множители:

\[ n = \prod_{i=1}^{k} p_i^{e_i}. \]

Если \( n \) — простое число, то алгоритм не даёт преимущества и сводится к полному перебору или другим методам.

Шаг 2. Вычисление частных логарифмов для каждого простого множителя

Для каждого \( i \) от 1 до \( k \) выполняется:

1. Вычисляется значение \( x_i \equiv x \pmod{p_i^{e_i}} \). Для этого используется представление \( x_i \) в \( p_i \)-ичной системе счисления:

\[ x_i = a_0 + a_1 p_i + a_2 p_i^2 + \ldots + a_{e_i-1} p_i^{e_i-1}, \]

где \( 0 \le a_j < p_i \).

1. Для нахождения коэффициентов \( a_j \) применяется метод «шаг за шагом». Для \( j = 0, 1, \ldots, e_i-1 \) вычисляются:

\[ \gamma_j = g^{n / p_i^{j+1}}, \quad \delta_j = \left( h \cdot g^{-(a_0 + a_1 p_i + \ldots + a_{j-1} p_i^{j-1})} \right)^{n / p_i^{j+1}}. \]

Затем \( a_j \) находится как дискретный логарифм \( \delta_j \) по основанию \( \gamma_j \) в группе порядка \( p_i \). Поскольку порядок \( \gamma_j \) равен \( p_i \), этот логарифм можно вычислить, например, полным перебором за \( O(p_i) \) операций.

1. После нахождения всех \( a_j \) составляется \( x_i \).

Шаг 3. Восстановление полного логарифма

С помощью китайской теоремы об остатках по найденным \( x_i \) и модулям \( p_i^{e_i} \) вычисляется \( x \) по модулю \( n \):

\[ x \equiv \sum_{i=1}^{k} x_i \cdot M_i \cdot M_i^{-1} \pmod{n}, \]

где \( M_i = n / p_i^{e_i} \), а \( M_i^{-1} \) — обратный элемент к \( M_i \) по модулю \( p_i^{e_i} \).

Сложность и эффективность

Временная сложность алгоритма Полига — Хеллмана составляет:

\[ O\left( \sum_{i=1}^{k} e_i \cdot (\log n + \sqrt{p_i}) \right) \]

в предположении, что для нахождения дискретного логарифма в группе порядка \( p_i \) используется метод «шаг младенца — шаг великана» (алгоритм Шенкса). Если же применяется полный перебор, то сложность возрастает до \( O\left( \sum_{i=1}^{k} e_i \cdot p_i \right) \).

Алгоритм наиболее эффективен, когда все простые делители \( p_i \) малы (например, \( p_i < 10^{10} \)). В этом случае сложность является полиномиальной относительно \( \log n \). Если же среди делителей есть большое простое число, то алгоритм теряет преимущество, и сложность становится экспоненциальной.

Применение

Алгоритм Полига — Хеллмана используется в криптографическом анализе для проверки стойкости систем, основанных на дискретном логарифмировании. В частности, он применяется для атаки на протокол Диффи — Хеллмана в группах, порядок которых имеет малые простые делители. Для предотвращения таких атак при выборе криптографических параметров (например, в алгоритме Диффи — Хеллмана или DSA) порядок группы выбирается таким, чтобы он содержал большой простой делитель (часто — простое число Софи Жермен). Также алгоритм может быть использован для вычисления дискретных логарифмов в некоторых конечных полях и группах точек эллиптических кривых, если их порядок является гладким числом.

Пример

Рассмотрим группу \( \mathbb{Z}_{101}^* \) порядка \( n = 100 \). Разложение: \( 100 = 2^2 \cdot 5^2 \). Пусть \( g = 2 \), \( h = 3 \). Требуется найти \( x \) такое, что \( 2^x \equiv 3 \pmod{101} \).

1. Для \( p_1 = 2 \), \( e_1 = 2 \): вычисляем \( x_1 \equiv x \pmod{4} \). Представляем \( x_1 = a_0 + 2a_1 \). Находим \( a_0 \): \( \gamma_0 = 2^{100/2} = 2^{50} \equiv 100 \pmod{101} \), \( \delta_0 = 3^{100/2} = 3^{50} \equiv 100 \pmod{101} \). Дискретный логарифм 100 по основанию 100 в группе порядка 2 равен 1, поэтому \( a_0 = 1 \). Затем \( a_1 \): \( \gamma_1 = 2^{100/4} = 2^{25} \equiv 10 \pmod{101} \), \( \delta_1 = (3 \cdot 2^{-1})^{100/4} = (3 \cdot 51)^{25} \equiv 1 \pmod{101} \). Дискретный логарифм 1 по основанию 10 равен 0, поэтому \( a_1 = 0 \). Получаем \( x_1 = 1 \).

1. Для \( p_2 = 5 \), \( e_2 = 2 \): аналогично находим \( x_2 \equiv x \pmod{25} \). После вычислений получаем \( x_2 = 19 \).

1. По китайской теореме об остатках: система \( x \equiv 1 \pmod{4} \), \( x \equiv 19 \pmod{25} \) даёт \( x \equiv 69 \pmod{100} \). Проверка: \( 2^{69} \equiv 3 \pmod{101} \).

Ограничения и критика

Основным ограничением алгоритма является необходимость факторизации порядка группы. Если порядок \( n \) — большое простое число или содержит большой простой делитель, то алгоритм неэффективен. Кроме того, для работы требуется знание порядка группы, что не всегда доступно в некоторых криптографических схемах. В современных криптосистемах, таких как DSA или ECDSA, порядок группы выбирается так, чтобы он был простым числом или содержал большой простой делитель, что делает алгоритм Полига — Хеллмана неприменимым для атаки.

Источники

• Pohlig, S., Hellman, M. (1978). «An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance». IEEE Transactions on Information Theory, 24(1), 106–110.
• Menezes, A., van Oorschot, P., Vanstone, S. (1996). «Handbook of Applied Cryptography». CRC Press.
• Шнайер, Б. (2002). «Прикладная криптография». Триумф.