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

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

История

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

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

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

Шаблон:EF

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

Шаблон:EF

Необходимо найти число $x,0\le x<p-1$, удовлетворяющее сравнению (1).Шаблон:Sfn

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

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

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

$(a^x{)}^{(p-1)/q_i^{{\alpha }_i}}\equiv b^{(p-1)/q_i^{{\alpha }_i}}(\mathrm{mod}p)$.Шаблон:Sfn

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

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

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

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

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

$a^{p-1}\equiv 1\equiv a^0(\mathrm{mod}p)$.

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

$x=\sum _{i=0}^{n-1}{q}_i{2}^i=q_0+q_1{2}^1+\cdots +q_{n-1}{2}^{n-1}$

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

$b^{(p-1)/2}(\mathrm{mod}p)\equiv \{\begin{array}{cc}+1,& q_0=0\\ -1,& q_0=1.\end{array}$

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

$b\equiv a^x\equiv a^{x_1+q_0}(\mathrm{mod}p)\Rightarrow z_1\equiv b{a}^{-q_0}\equiv a^{x_1}(\mathrm{mod}p)$,

где

$x_1=\sum _{i=1}^{n-1}{q}_i{2}^i=q_1{2}^1+q_2{2}^2+\cdots +q_{n-1}{2}^{n-1}$

Понятно, что $x_1$ делится на $4$ при $q_1=0$, а при $q_1=1$ делится на $2$, а на $4$ уже нет.

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

$z_1^{(p-1)/4}(\mathrm{mod}p)\equiv \{\begin{array}{cc}+1,& q_1=0\\ -1,& q_1=1,\end{array}$

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

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

$m_i=(p-1)/2^{i+1}$

$z_i\equiv b\cdot a^{-q_0-q_1{2}^1-\dots -q_{i-1}{2}^{i-1}}\equiv a^{x_i}(\mathrm{mod}p)$,

где

$x_i=\sum _{k=i}^{n-1}{q}_k{2}^k$.

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

$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}(\mathrm{mod}p)$.

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

$z_i^{m_i}(\mathrm{mod}p)\equiv \{\begin{array}{cc}+1,& q_i=0\\ -1,& q_i=1,\end{array}$

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

Найдя все биты, получаем требуемое решение $x$.Шаблон:Sfn

Пример

Дано:

$a=3,b=11,p=17=2^4+1$

Найти:

$x$

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

$x=q_0+q_1{2}^1+q_2{2}^2+q_3{2}^3$

Находим $q_0$:

$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(\mathrm{mod}17)\Rightarrow q_0=1$

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

$z_1\equiv b\cdot a^{-q_0}\equiv 11\cdot 3^{-1}\equiv 11\cdot 6\equiv 66\equiv -2(\mathrm{mod}17)$

$m_1=(p-1)/2^{1+1}=(17-1)/2^2=4$

Находим $q_1$:

$z_1^{m_1}\equiv (-2{)}^4\equiv 16\equiv -1(\mathrm{mod}17)\Rightarrow q_1=1$

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

$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(\mathrm{mod}17)$

$m_2=(p-1)/2^{2+1}=(17-1)/2^3=2$

Находим $q_2$:

$z_2^{m_2}\equiv 13^2\equiv (-4{)}^2\equiv 16\equiv -1(\mathrm{mod}17)\Rightarrow q_2=1$

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

$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(\mathrm{mod}17)$

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

Находим $q_3$:

$z_3^{m_3}\equiv 1^1\equiv 1(\mathrm{mod}17)\Rightarrow q_3=0$

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

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

Ответ: $x=7$

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

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

Шаг 2 (вычисление ${\log }_{a}bmod{q}_i^{{\alpha }_i}$). 
Для i от 1 до k:
 Пусть
  $x\equiv {\log }_{a}b\equiv x_0+x_1{q}_i+\mathrm{...}+x_{{\alpha }_i-1}{q}_i^{{\alpha }_i-1}(\mathrm{mod}{q}_i^{{\alpha }_i}),$
 где
  $0\le x_i\le q_i-1$.
 Тогда верно сравнение:
  $a^{x_0\cdot \frac{p-1}{q_i}}\equiv b^{\frac{p-1}{q_i}}(\mathrm{mod}p)$

 С помощью таблицы, составленной на шаге 1, находим $x_0.$
 Для j от 0 до ${\alpha }_i-1$ 
  Рассматриваем сравнение
   $a^{x_j\cdot \frac{p-1}{q_i}}\equiv (b{a}^{-x_0-x_1{q}_i\mathrm{...}-x_{j-1}{q}_i^{j-1}}{)}^{\frac{p-1}{q_i^{j+1}}}(\mathrm{mod}p)$
  Решение опять же находится по таблице
 Конец цикла по j
Конец цикла по i

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

Пример

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

$2^x\equiv 28(\mathrm{mod}37)$.

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

Получаем $q_1=2,{\alpha }_1=2,q_2=3,{\alpha }_2=2$.

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

$r_{20}\equiv 2^{0\cdot \frac{37-1}{2}}\equiv 1(\mathrm{mod}37)$

$r_{21}\equiv 2^{1\cdot \frac{37-1}{2}}\equiv 2^{18}\equiv -1(\mathrm{mod}37)$

$r_{30}\equiv 2^{0\cdot \frac{37-1}{3}}\equiv 1(\mathrm{mod}37)$

$r_{31}\equiv 2^{1\cdot \frac{37-1}{3}}\equiv 2^{12}\equiv 26(\mathrm{mod}37)$

$r_{32}\equiv 2^{2\cdot \frac{37-1}{3}}\equiv 2^{24}\equiv 10(\mathrm{mod}37)$

Рассматриваем $q_1=2$. Для $x$ верно:

$x\equiv x_0+x_1{q}_1(\mathrm{mod}{q}_1^{{\alpha }_i})\equiv x_0+x_1\cdot 2(\mathrm{mod}{2}^2)$

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

$a^{x_0\cdot \frac{p-1}{q_1}}\equiv b^{\frac{p-1}{q_1}}(\mathrm{mod}p)\Rightarrow 2^{x_0\cdot \frac{37-1}{2}}\equiv 28^{\frac{37-1}{2}}\equiv 28^{18}\equiv 1(\mathrm{mod}37)$

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

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

$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(\mathrm{mod}37)$

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

$x\equiv 0+1\cdot 2\equiv 2(\mathrm{mod}4)$

Теперь рассматриваем $q_2=3$. Для $x$ верно:

$x\equiv x_0+x_1\cdot 3(\mathrm{mod}{3}^2)$

По аналогии находим $x_0$ и $x_1$:

$2^{x_0\cdot \frac{37-1}{3}}\equiv 28^{\frac{37-1}{3}}\equiv 28^{12}\equiv 26(\mathrm{mod}37)\Rightarrow x_0=1$

$2^{x_1\cdot \frac{37-1}{3}}\equiv (28\cdot 2^{-1}{)}^{\frac{37-1}{3^2}}\equiv 14^4\equiv 10(\mathrm{mod}37)\Rightarrow x_1=2$

Получаем $x$:

$x\equiv 1+2\cdot 3\equiv 7(\mathrm{mod}9)$

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

$\{\begin{array}{c}x\equiv 2(\mathrm{mod}4)\\ x\equiv 7(\mathrm{mod}9)\end{array}$

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

$x=2+4\cdot t\Rightarrow 2+4\cdot t\equiv 7(\mathrm{mod}9)\Rightarrow 4\cdot t\equiv 5(\mathrm{mod}9)\Rightarrow$

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

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

$x\equiv 2+4\cdot 8\equiv 34(\mathrm{mod}36)\equiv 34(\mathrm{mod}37)$

Ответ: $x=34$.Шаблон:Sfn

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

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

$O\left(\sum _{i=1}^k{\alpha }_i({\log }_{2}p+q_i^{1-r_i}(1+{\log }_2{q}_i^{r_i}))\right)$, где $0\le r_i\le 1$.

При этом необходимо $O\left({\log }_{2}p\sum _{i=1}^k(1+p_i^{r_i})\right)$ бит памяти.Шаблон:Sfn

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

$O(\sum _{i=1}^k{\alpha }_i{q}_i+\log p)$.Шаблон:Sfn

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

$O(\sum _{i=1}^k{\alpha }_i\sqrt{q_i}+\log p)$.

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

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

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

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

Пример

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

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

Если имеется простой множитель $q_i$ такой, что $q_i\ge p^c$, где $c\ge 0$.Шаблон:Sfn

Применение

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

Замечание

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

Литература

на русском языке

1. Шаблон:Книга
2. Шаблон:Книга Шаблон:Wayback

на английском языке

1. Шаблон:Статья
2. Шаблон:СтатьяШаблон:Недоступная ссылка
3. Шаблон:Книга