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

Перейти к навигацииПерейти к поиску

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

История

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

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

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

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

Необходимо найти число , удовлетворяющее сравнению (1).[4]

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

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

Чтобы найти по каждому из таких модулей, нужно решить сравнение:

.[5]

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

Упрощённый вариант

Лучшим путём, чтобы разобраться с данным алгоритмом, будет рассмотрение особого случая, в котором .

Нам даны , и , при этом есть примитивный элемент и нужно найти такое , чтобы удовлетворялось .

Принимается, что , так как неотличимо от , потому что в нашем случае примитивный элемент по определению имеет степень , следовательно:

.

Когда , легко определить двоичным разложением c коэффициентами , например:

Самый младший бит определяется путём возведения в степень и применением правила

Теперь преобразуем известное разложение и введём новую переменную :

,

где

Понятно, что делится на при , а при делится на , а на уже нет.

Рассуждая как раньше, получим сравнение:

из которого находим .

Оставшиеся биты получаются похожим способом. Напишем общее решение нахождения с новыми обозначениями:

,

где

.

Таким образом, возведение в степень даёт:

.

Следовательно:

из которого находим .

Найдя все биты, получаем требуемое решение .[6]

Пример

Дано:

Найти:

Решение:
Получаем . Следовательно имеет вид:

Находим :

Подсчитываем и :

Находим :

Подсчитываем и :

Находим :

Подсчитываем и :

Находим :

Находим искомый :

Ответ:

Основное описание

Шаг 1 (составление таблицы).
Составить таблицу значений , где
 
Шаг 2 (вычисление ). 
Для i от 1 до k:
 Пусть
  
 где
  .
 Тогда верно сравнение:
  
 С помощью таблицы, составленной на шаге 1, находим 
 Для j от 0 до  
  Рассматриваем сравнение
   
  Решение опять же находится по таблице
 Конец цикла по j
Конец цикла по i
Шаг 3 (нахождение ответа).
Найдя  для всех i, находим  по китайской теореме об остатках.[7]

Пример

Необходимо найти дискретный логарифм по основанию в , другими словами найти для:

.

Находим разложение .

Получаем .

Составляем таблицу :

Рассматриваем . Для верно:

Находим из сравнения:

Из таблицы находим, что при верно выше полученное сравнение.

Находим из сравнения:

Из таблицы получаем, что при верно выше полученное сравнение. Находим :

Теперь рассматриваем . Для верно:

По аналогии находим и :

Получаем :

Получаем систему:

Решим систему. Первое сравнение преобразуем в равенство, которое подставляем во второе сравнение:

Подставляем найденное и получаем искомое :

Ответ: .[8]

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

Если известно разложение (2), то сложность алгоритма является

, где .

При этом необходимо бит памяти.[9]

В общем случае сложность алгоритма также можно оценить как

.[10]

Если при обработке каждого qi использовать ускоренные методы (например, алгоритм Шенкса), то общая оценка снизится до

.

В указанных оценках подразумевается, что арифметические операции по модулю p выполняются за один шаг. На самом деле это не так — например, сложение по модулю p требует O(log p) элементарных операций. Но поскольку аналогичные уточнения имеют место для любого алгоритма, данный множитель часто отбрасывается.

Полиномиальная сложность

Когда простые множители малы, то сложность алгоритма можно оценивать как . [11]

Алгоритм имеет полиномиальную сложность в общем виде в случае, когда все простые множители не превосходят ,
где  — положительные постоянные.[1]

Пример

Верно для простых вида .

Экспоненциальная сложность

Если имеется простой множитель такой, что , где .[1]

Применение

Алгоритм Полига—Хеллмана крайне эффективен, если раскладывается на небольшие простые множители. Это очень важно учитывать при выборе параметров криптографических схем. Иначе схема будет ненадёжной.

Замечание

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

Примечания

Литература

на русском языке
  1. Н. Коблиц. Курс теории чисел и криптографии. — М.: Научное издательство ТВП, 2001. — 254 с.
  2. О. Н. Василенко. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — 1000 экз. — ISBN 5-94057-103-4. Архивная копия от 27 января 2007 на Wayback Machine
на английском языке
  1. S. C. Pohlig and M. E. Hellman. An Improved Algorithm for Computing Logarithms Over GF(p) and its Cryptographic Significance (англ.) // IEEE Transactions on Information Theory. — 1978. — Vol. 1, no. 24. — P. 106-110.
  2. A. M. Odlyzko. Discrete logarithms in finite fields and their cryptographic significance (англ.) // T.Beth, N.Cot, I.Ingemarsson Proc. of the EUROCRYPT 84 workshop on Advances in cryptology: theory and application of cryptographic techniques. — NY, USA: Springer-Verlag New York, 1985. — P. 224-314. — ISBN 0-387-16076-0. (недоступная ссылка)
  3. J. Hoffstein, J. Pipher, J. H. Silverman. An Introduction to Mathematical Cryptography (англ.). — Springer, 2008. — 524 p. — ISBN 978-0-387-77993-5.