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

История

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

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

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

и известно разложение числа ${\displaystyle p-1}$ на простые множители:

Необходимо найти число ${\displaystyle x,\;0\leq x<p-1}$ , удовлетворяющее сравнению (1).

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

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

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

${\displaystyle (a^{x})^{(p-1)/{q_{i}^{\alpha _{i}}}}\equiv b^{(p-1)/{q_{i}^{\alpha _{i}}}}{\pmod {p}}}$ .

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

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

Лучшим путём, чтобы разобраться с данным алгоритмом, будет рассмотрение особого случая, в котором ${\displaystyle p=2^{n}+1}$ .

Нам даны ${\displaystyle a}$ , ${\displaystyle p}$ и ${\displaystyle b}$ , при этом ${\displaystyle a}$ есть примитивный элемент ${\displaystyle GF(p)}$ и нужно найти такое ${\displaystyle x}$ , чтобы удовлетворялось ${\displaystyle a^{x}\equiv b{\pmod {p}}}$ .

Принимается, что ${\displaystyle 0\leq x\leq p-2}$ , так как ${\displaystyle x=p-1}$ неотличимо от ${\displaystyle x=0}$ , потому что в нашем случае примитивный элемент ${\displaystyle a}$ по определению имеет степень ${\displaystyle p-1}$ , следовательно:

${\displaystyle a^{p-1}\equiv 1\equiv a^{0}{\pmod {p}}}$ .

Когда ${\displaystyle p=2^{n}+1}$ , легко определить ${\displaystyle x}$ двоичным разложением c коэффициентами ${\displaystyle \{q_{0},q_{1},\dots ,q_{n-1}\}}$ , например:

${\displaystyle x=\sum \limits _{i=0}^{n-1}q_{i}2^{i}=q_{0}+q_{1}2^{1}+\cdots +q_{n-1}2^{n-1}}$

Самый младший бит ${\displaystyle q_{0}}$ определяется путём возведения ${\displaystyle b}$ в степень ${\displaystyle (p-1)/2=2^{n-1}}$ и применением правила

${\displaystyle b^{(p-1)/2}{\pmod {p}}\equiv {\begin{cases}+1,&q_{0}=0\\-1,&q_{0}=1.\end{cases}}}$

Теперь преобразуем известное разложение и введём новую переменную ${\displaystyle z_{1}}$ :

${\displaystyle b\equiv a^{x}\equiv a^{x_{1}+q_{0}}{\pmod {p}}\Rightarrow z_{1}\equiv ba^{-q_{0}}\equiv a^{x_{1}}{\pmod {p}}}$ ,

где

${\displaystyle x_{1}=\sum \limits _{i=1}^{n-1}q_{i}2^{i}=q_{1}2^{1}+q_{2}2^{2}+\cdots +q_{n-1}2^{n-1}}$

Понятно, что ${\displaystyle x_{1}}$ делится на ${\displaystyle 4}$ при ${\displaystyle q_{1}=0}$ , а при ${\displaystyle q_{1}=1}$ делится на ${\displaystyle 2}$ , а на ${\displaystyle 4}$ уже нет.

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

${\displaystyle z_{1}^{(p-1)/4}{\pmod {p}}\equiv {\begin{cases}+1,&q_{1}=0\\-1,&q_{1}=1,\end{cases}}}$

из которого находим ${\displaystyle q_{1}}$ .

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

${\displaystyle m_{i}=(p-1)/2^{i+1}}$

${\displaystyle z_{i}\equiv b\cdot a^{-q_{0}-q_{1}2^{1}-\dots -q_{i-1}2^{i-1}}\equiv a^{x_{i}}{\pmod {p}}}$ ,

где

${\displaystyle x_{i}=\sum \limits _{k=i}^{n-1}q_{k}2^{k}}$ .

Таким образом, возведение ${\displaystyle z_{i}}$ в степень ${\displaystyle m_{i}}$ даёт:

${\displaystyle z_{i}^{m_{i}}\equiv a^{(x_{i}\cdot m_{i})}\equiv \left(a^{(p-1)/2}\right)^{(x_{i}/2^{i})}\equiv (-1)^{x_{i}/2^{i}}\equiv (-1)^{q_{i}}{\pmod {p}}}$ .

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

${\displaystyle z_{i}^{m_{i}}{\pmod {p}}\equiv {\begin{cases}+1,&q_{i}=0\\-1,&q_{i}=1,\end{cases}}}$

из которого находим ${\displaystyle q_{i}}$ .

Найдя все биты, получаем требуемое решение ${\displaystyle x}$ .

Пример

Дано:

${\displaystyle a=3,\;b=11,\;p=17=2^{4}+1}$

Найти:

${\displaystyle x}$

Решение:
Получаем ${\displaystyle p-1=2^{4}}$ . Следовательно ${\displaystyle x}$ имеет вид:

${\displaystyle x=q_{0}+q_{1}2^{1}+q_{2}2^{2}+q_{3}2^{3}}$

Находим ${\displaystyle q_{0}}$ :

${\displaystyle b^{(p-1)/2}\equiv 11^{(17-1)/2}\equiv 11^{8}\equiv (-6)^{8}\equiv (36)^{4}\equiv 2^{4}\equiv 16\equiv -1{\pmod {17}}\Rightarrow q_{0}=1}$

Подсчитываем ${\displaystyle z_{1}}$ и ${\displaystyle m_{1}}$ :

${\displaystyle z_{1}\equiv b\cdot a^{-q_{0}}\equiv 11\cdot 3^{-1}\equiv 11\cdot 6\equiv 66\equiv -2{\pmod {17}}}$

${\displaystyle m_{1}=(p-1)/2^{1+1}=(17-1)/2^{2}=4}$

Находим ${\displaystyle q_{1}}$ :

${\displaystyle z_{1}^{m_{1}}\equiv (-2)^{4}\equiv 16\equiv -1{\pmod {17}}\Rightarrow q_{1}=1}$

Подсчитываем ${\displaystyle z_{2}}$ и ${\displaystyle m_{2}}$ :

${\displaystyle z_{2}\equiv z_{1}\cdot a^{-q_{1}2^{1}}\equiv (-2)\cdot 3^{-2}\equiv (-2)\cdot 6^{2}\equiv (-2)\cdot 36\equiv (-2)\cdot 2\equiv -4\equiv 13{\pmod {17}}}$

${\displaystyle m_{2}=(p-1)/2^{2+1}=(17-1)/2^{3}=2}$

Находим ${\displaystyle q_{2}}$ :

${\displaystyle z_{2}^{m_{2}}\equiv 13^{2}\equiv (-4)^{2}\equiv 16\equiv -1{\pmod {17}}\Rightarrow q_{2}=1}$

Подсчитываем ${\displaystyle z_{3}}$ и ${\displaystyle m_{3}}$ :

${\displaystyle z_{3}\equiv z_{2}\cdot a^{-q_{2}\cdot 2^{2}}\equiv 13\cdot 3^{-4}\equiv 13\cdot 9^{-2}\equiv 13\cdot 2^{2}\equiv (-4)\cdot 4\equiv -16\equiv 1{\pmod {17}}}$

${\displaystyle m_{3}=(p-1)/2^{3+1}=(17-1)/2^{4}=1}$

Находим ${\displaystyle q_{3}}$ :

${\displaystyle z_{3}^{m_{3}}\equiv 1^{1}\equiv 1{\pmod {17}}\Rightarrow q_{3}=0}$

Находим искомый ${\displaystyle x}$ :

${\displaystyle x=1+1\cdot 2^{1}+1\cdot 2^{2}+0\cdot 2^{3}\equiv 7}$

Ответ: ${\displaystyle x=7}$

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

Шаг 1 (составление таблицы).
Составить таблицу значений ${\displaystyle \{r_{i,j}\}}$, где
 ${\displaystyle r_{i,j}=a^{j\cdot {\frac {p-1}{q_{i}}}},i\in \{1,\dots ,k\},j\in \{0,\dots ,q_{i}-1\}.}$

Шаг 2 (вычисление ${\displaystyle \log _{a}{b}\;{\bmod {q_{i}^{\alpha _{i}}}}}$). 
Для i от 1 до k:
 Пусть
  ${\displaystyle x\equiv \log _{a}{b}\equiv x_{0}+x_{1}q_{i}+...+x_{\alpha _{i}-1}q_{i}^{\alpha _{i}-1}{\pmod {q_{i}^{\alpha _{i}}}},}$
 где
  ${\displaystyle 0\leq x_{i}\leq q_{i}-1}$.
 Тогда верно сравнение:
  ${\displaystyle a^{x_{0}\cdot {\frac {p-1}{q_{i}}}}\equiv b^{\frac {p-1}{q_{i}}}{\pmod {p}}}$

 С помощью таблицы, составленной на шаге 1, находим ${\displaystyle x_{0}.}$
 Для j от 0 до ${\displaystyle \alpha _{i}-1}$ 
  Рассматриваем сравнение
   ${\displaystyle a^{x_{j}\cdot {\frac {p-1}{q_{i}}}}\equiv (ba^{-x_{0}-x_{1}q_{i}...-x_{j-1}q_{i}^{j-1}})^{\frac {p-1}{q_{i}^{j+1}}}{\pmod {p}}}$
  Решение опять же находится по таблице
 Конец цикла по j
Конец цикла по i

Шаг 3 (нахождение ответа).
Найдя ${\displaystyle \log _{a}{b}\;{\bmod {q_{i}^{\alpha _{i}}}}}$ для всех i, находим ${\displaystyle \log _{a}{b}\;{\bmod {\;}}(p-1)}$ по китайской теореме об остатках.

Пример

Необходимо найти дискретный логарифм ${\displaystyle 28}$ по основанию ${\displaystyle 2}$ в ${\displaystyle GF(37)}$ , другими словами найти ${\displaystyle x}$ для:

${\displaystyle 2^{x}\equiv 28{\pmod {37}}}$ .

Находим разложение ${\displaystyle \varphi (37)=37-1=36=2^{2}\cdot 3^{2}}$ .

Получаем ${\displaystyle q_{1}=2,\alpha _{1}=2,q_{2}=3,\alpha _{2}=2}$ .

Составляем таблицу ${\displaystyle r_{ij}}$ :

${\displaystyle r_{20}\equiv 2^{0\cdot {\frac {37-1}{2}}}\equiv 1{\pmod {37}}}$

${\displaystyle r_{21}\equiv 2^{1\cdot {\frac {37-1}{2}}}\equiv 2^{18}\equiv -1{\pmod {37}}}$

${\displaystyle r_{30}\equiv 2^{0\cdot {\frac {37-1}{3}}}\equiv 1{\pmod {37}}}$

${\displaystyle r_{31}\equiv 2^{1\cdot {\frac {37-1}{3}}}\equiv 2^{12}\equiv 26{\pmod {37}}}$

${\displaystyle r_{32}\equiv 2^{2\cdot {\frac {37-1}{3}}}\equiv 2^{24}\equiv 10{\pmod {37}}}$

Рассматриваем ${\displaystyle q_{1}=2}$ . Для ${\displaystyle x}$ верно:

${\displaystyle x\equiv x_{0}+x_{1}q_{1}{\pmod {q_{1}^{\alpha _{i}}}}\equiv x_{0}+x_{1}\cdot 2{\pmod {2^{2}}}}$

Находим ${\displaystyle x_{0}}$ из сравнения:

${\displaystyle a^{x_{0}\cdot {\frac {p-1}{q_{1}}}}\equiv b^{\frac {p-1}{q_{1}}}{\pmod {p}}\Rightarrow 2^{x_{0}\cdot {\frac {37-1}{2}}}\equiv 28^{\frac {37-1}{2}}\equiv 28^{18}\equiv 1{\pmod {37}}}$

Из таблицы находим, что при ${\displaystyle x_{0}=0}$ верно выше полученное сравнение.

Находим ${\displaystyle x_{1}}$ из сравнения:

${\displaystyle a^{x_{1}\cdot {\frac {p-1}{q_{i}}}}\equiv (b\cdot a^{-x_{0}})^{\frac {p-1}{q_{i}^{2}}}\Rightarrow 2^{x_{1}\cdot {\frac {37-1}{2}}}\equiv (28\cdot 2^{-0})^{\frac {37-1}{4}}\equiv 28^{9}\equiv -1{\pmod {37}}}$

Из таблицы получаем, что при ${\displaystyle x_{1}=1}$ верно выше полученное сравнение. Находим ${\displaystyle x}$ :

${\displaystyle x\equiv 0+1\cdot 2\equiv 2{\pmod {4}}}$

Теперь рассматриваем ${\displaystyle q_{2}=3}$ . Для ${\displaystyle x}$ верно:

${\displaystyle x\equiv x_{0}+x_{1}\cdot 3{\pmod {3^{2}}}}$

По аналогии находим ${\displaystyle x_{0}}$ и ${\displaystyle x_{1}}$ :

${\displaystyle 2^{x_{0}\cdot {\frac {37-1}{3}}}\equiv 28^{\frac {37-1}{3}}\equiv 28^{12}\equiv 26{\pmod {37}}\Rightarrow x_{0}=1}$

${\displaystyle 2^{x_{1}\cdot {\frac {37-1}{3}}}\equiv (28\cdot 2^{-1})^{\frac {37-1}{3^{2}}}\equiv 14^{4}\equiv 10{\pmod {37}}\Rightarrow x_{1}=2}$

Получаем ${\displaystyle x}$ :

${\displaystyle x\equiv 1+2\cdot 3\equiv 7{\pmod {9}}}$

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

${\displaystyle {\begin{cases}x\equiv 2{\pmod {4}}\\x\equiv 7{\pmod {9}}\\\end{cases}}}$

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

${\displaystyle x=2+4\cdot t\Rightarrow 2+4\cdot t\equiv 7{\pmod {9}}\Rightarrow 4\cdot t\equiv 5{\pmod {9}}\Rightarrow }$

${\displaystyle t\equiv 5\cdot (4)^{-1}\equiv 5\cdot (-2)\equiv -10\equiv 8{\pmod {9}}}$

Подставляем найденное ${\displaystyle t}$ и получаем искомое ${\displaystyle x}$ :

${\displaystyle x\equiv 2+4\cdot 8\equiv 34{\pmod {36}}\equiv 34{\pmod {37}}}$

Ответ: ${\displaystyle x=34}$ .

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

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

${\displaystyle O\left(\sum \limits _{i=1}^{k}\alpha _{i}\left(\log _{2}{p}+q_{i}^{1-r_{i}}(1+\log _{2}{q_{i}^{r_{i}}})\right)\right)}$ , где ${\displaystyle 0\leq r_{i}\leq 1}$ .

При этом необходимо ${\displaystyle O\left(\log _{2}{p}\sum \limits _{i=1}^{k}\left(1+p_{i}^{r_{i}}\right)\right)}$ бит памяти.

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

${\displaystyle O\left(\sum \limits _{i=1}^{k}\alpha _{i}q_{i}+\log {p}\right)}$ .

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

${\displaystyle O\left(\sum \limits _{i=1}^{k}\alpha _{i}{\sqrt {q_{i}}}+\log {p}\right)}$ .

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

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

Когда простые множители ${\displaystyle \left\{q_{i}\right\}_{i=1}^{k}}$ малы, то сложность алгоритма можно оценивать как ${\displaystyle O\left((\log _{2}p)^{2}\right)}$ .

Алгоритм имеет полиномиальную сложность в общем виде ${\displaystyle O\left((\log p)^{c_{1}}\right)}$ в случае, когда все простые множители ${\displaystyle \left\{q_{i}\right\}_{i=1}^{k}}$ не превосходят ${\displaystyle (\log p)^{c_{2}}}$ ,
где ${\displaystyle c_{1},c_{2}}$ — положительные постоянные.

Пример

Верно для простых ${\displaystyle p}$ вида ${\displaystyle p=2^{\alpha }+1,\;p=2^{\alpha _{1}}3^{\alpha _{2}}+1}$ .

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

Если имеется простой множитель ${\displaystyle q_{i}}$ такой, что ${\displaystyle q_{i}\geq p^{c}}$ , где ${\displaystyle c\geq 0}$ .

Применение

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

Замечание

Для применения алгоритма Полига-Хеллмана необходимо знать разложение ${\displaystyle p-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. (англ.) // IEEE Transactions on Information Theory. — 1978. — Vol. 1 , no. 24 . — P. 106-110 .
2. A. M. Odlyzko. (англ.) // 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. (англ.) . — Springer, 2008. — 524 p. — ISBN 978-0-387-77993-5 .