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

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

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

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

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

${\displaystyle p-1=\prod \limits _{i=1}^{k}q_{i}^{\alpha _{i}}.}$

(2)

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

Суть алгоритма в том, что достаточно найти ${\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}}}$.^[5]

Лучшим путём, чтобы разобраться с данным алгоритмом, будет рассмотрение особого случая, в котором ${\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}$.^[6]

Дано:

${\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)}$ по китайской теореме об остатках.[7]

Необходимо найти дискретный логарифм ${\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}$.^[8]

Если известно разложение (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)}$ бит памяти.^[9]

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

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

Если при обработке каждого 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)}$. ^[11]

Алгоритм имеет полиномиальную сложность в общем виде ${\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}}$ — положительные постоянные.^[1]

Верно для простых ${\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}$.^[1]

Алгоритм Полига—Хеллмана крайне эффективен, если ${\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. 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.