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

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

Когда простые множители ${\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]