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

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

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

На самом деле, честь открытия этого алгоритма принадлежит советским криптоаналитикам А.О. Гельфонду (одна из теорем в 1962 году) и В.И.Нечаеву (другая теорема в 1965 году). В 1972 году Василий Ильич Нечаев установил, что среди детерминированных алгоритмов нет лучших. Поскольку задача отыскания оптимального алгоритма вычисления дискретного логарифма принадлежит к числу важнейших в криптографии, не удивительно, что до последних лет истинные первооткрыватели этого метода находились "в тени".
До сих пор продолжаются исследования в отыскании других (не детерминированных) алгоритмов вычисления дискретных логарифмов и уже предложен целый ряд таких алгоритмов, использующих вероятностные соображения. 

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

((1))

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

({{{2}}})

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

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

((2))

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

Шаг 1 (составление таблицы). Составить таблицу значений {ri,j}, где

Шаг 2 (вычисление ).

Для i от 1 до s:

Пусть

где

Тогда из (1) следует, что

С помощью таблицы, составленной на шаге 1, находим x0.

Для j от 1 до α − 1

Рассматриваем сравнение

Решение опять же находится по таблице

Конец цикла по i

Конец цикла по j

Шаг 3 (нахождение ответа). Найдя для всех i, находим по китайской теореме об остатках.

Решение сравнения (1) находится за  арифметических операций.

Можно также сказать, что решение находится за  арифметических операций, где q — наибольший простой делитель p-1.

Если все простые делители qi не превосходят  то А.П.-Х. является полиномиальным и имеет сложность , где c1,2 — некоторые положительные постоянные. 

Как уже было сказано, А.П.-Х. крайне эффективен, если p-1 раскладывается на небольшие простые множители. Например, для чисел вида  и т. д. Если же у p-1 есть большой простой делитель  то алгоритм имеет экспоненциальную сложность. Это очень важно учитывать при выборе параметров криптографических схем. 

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

Лит.: Василенко О.Н. Теоретико-числовые алгоритмы в криптографии — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4. Pohlig S., Hellmann M. (1978). «An improved algorithm for computing logarithms over GF(p) and its cryptographic significance». IEEE Trans. Inform. Theory 24 (1): 106-110. Odlyzko A. M. (1985). «Discrete logarithms in finite fields and their cryptographic significance». Lecture Notes in Computer Science 209: 224—316. DOI:10.1007/3-540-39757-4_20. Нечаев В.И. "ЭЛЕМЕНТЫ КРИПТОГРАФИИ (Основы теории защиты информации)" — М.: "Высшая школа", 1999. — 109 с. — ISBN 5-06-003644-8.