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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

История[править | править вики-текст]

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

Исходные данные[править | править вики-текст]

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

(1)

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

(2)

Необходимо найти число , удовлетворяющее сравнению (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.
на английском языке
  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 с. — ISBN 978-0-387-77993-5.