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

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

История

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

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

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

[math]\displaystyle{ a^x\equiv b\pmod{p}, }[/math]

(1)

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

[math]\displaystyle{ p-1=\prod\limits_{i=1}^{k}q_i^{\alpha_i}. }[/math]

(2)

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

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

Суть алгоритма в том, что достаточно найти [math]\displaystyle{ x }[/math] по модулям [math]\displaystyle{ q_i^{\alpha_i} }[/math] для всех [math]\displaystyle{ i }[/math], а затем решение исходного сравнения можно найти с помощью китайской теоремы об остатках.
Чтобы найти [math]\displaystyle{ x }[/math] по каждому из таких модулей, нужно решить сравнение:

[math]\displaystyle{ (a^x)^{(p-1)/{q_i^{\alpha_i}}} \equiv b^{(p-1)/{q_i^{\alpha_i}}} \pmod{p} }[/math].

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

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

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

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

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

[math]\displaystyle{ a^{p-1}\equiv 1\equiv a^{0}\pmod{p} }[/math].

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

[math]\displaystyle{ x = \sum\limits_{i = 0}^{n-1}q_i2^i=q_{0} + q_{1}2^1 + \cdots + q_{n-1}2^{n-1} }[/math]

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

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

Вывод верхнего правила

Рассмотрим ранее полученное сравнение:

[math]\displaystyle{ a^{p-1}\equiv 1\pmod{p}\Rightarrow a^{(p-1)/2}\equiv\pm 1\pmod{p} }[/math],

но [math]\displaystyle{ a }[/math] в степени [math]\displaystyle{ (p-1)/2 \lt p - 1 }[/math] по определению принимает значение, отличное от [math]\displaystyle{ 1 }[/math], поэтому остаётся только одно сравнение:

[math]\displaystyle{ a^{(p-1)/2}\equiv -1\pmod{p} }[/math].

Возведём сравнение (1) в степень [math]\displaystyle{ (p-1)/2 }[/math] и подставим выше полученное сравнение:

[math]\displaystyle{ b^{(p-1)/2}\equiv (a^x)^{(p-1)/2}\equiv(a^{(p-1)/2})^x\equiv(-1)^x\pmod{p} }[/math]

Равенство [math]\displaystyle{ (-1)^x=1 }[/math] верно, если [math]\displaystyle{ x }[/math] чётное, то есть в разложении в виде многочлена свободный член [math]\displaystyle{ q_0 }[/math] равен [math]\displaystyle{ 0 }[/math], следовательно [math]\displaystyle{ (-1)^x = -1 }[/math] верно, когда [math]\displaystyle{ q_0 = 1 }[/math].

Теперь преобразуем известное разложение и введём новую переменную [math]\displaystyle{ z_1 }[/math]:

[math]\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} }[/math],

где

[math]\displaystyle{ x_1 = \sum\limits_{i = 1}^{n-1}q_i2^i=q_{1}2^1 + q_{2}2^2 + \cdots + q_{n-1}2^{n-1} }[/math]

Понятно, что [math]\displaystyle{ x_1 }[/math] делится на [math]\displaystyle{ 4 }[/math] при [math]\displaystyle{ q_1=0 }[/math], а при [math]\displaystyle{ q_1=1 }[/math] делится на [math]\displaystyle{ 2 }[/math], а на [math]\displaystyle{ 4 }[/math] уже нет.

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

[math]\displaystyle{ z_1^{(p-1)/4}\pmod{p}\equiv \begin{cases}+1, & q_1 = 0\\ -1, & q_1 = 1, \end{cases} }[/math]

из которого находим [math]\displaystyle{ q_1 }[/math].

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

[math]\displaystyle{ m_i=(p-1)/2^{i+1} }[/math]

[math]\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} }[/math],

где

[math]\displaystyle{ x_i = \sum\limits_{k = i}^{n-1}q_k2^k }[/math].

Таким образом, возведение [math]\displaystyle{ z_i }[/math] в степень [math]\displaystyle{ m_i }[/math] даёт:

[math]\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} }[/math].

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

[math]\displaystyle{ z_i^{m_i}\pmod{p}\equiv \begin{cases}+1, & q_i = 0\\ -1, & q_i = 1, \end{cases} }[/math]

из которого находим [math]\displaystyle{ q_i }[/math].

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

Пример

Дано:

[math]\displaystyle{ a = 3,\;b = 11,\;p = 17 = 2^4 + 1 }[/math]

Найти:

[math]\displaystyle{ x }[/math]

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

[math]\displaystyle{ x = q_0 + q_{1}2^1 + q_{2}2^2 + q_{3}2^3 }[/math]

Находим [math]\displaystyle{ q_0 }[/math]:

[math]\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 }[/math]

Подсчитываем [math]\displaystyle{ z_1 }[/math] и [math]\displaystyle{ m_1 }[/math]:

[math]\displaystyle{ z_1 \equiv b\cdot a^{-q_0} \equiv 11\cdot 3 ^{-1} \equiv 11 \cdot 6 \equiv 66 \equiv -2 \pmod{17} }[/math]

[math]\displaystyle{ m_1 = (p-1)/2^{1+1}= (17 - 1)/2^2 = 4 }[/math]

Находим [math]\displaystyle{ q_1 }[/math]:

[math]\displaystyle{ z_1^{m_1} \equiv (-2)^4 \equiv 16 \equiv -1 \pmod{17} \Rightarrow q_1 = 1 }[/math]

Подсчитываем [math]\displaystyle{ z_2 }[/math] и [math]\displaystyle{ m_2 }[/math]:

[math]\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} }[/math]

[math]\displaystyle{ m_2 = (p-1)/2^{2+1}= (17 - 1)/2^3 = 2 }[/math]

Находим [math]\displaystyle{ q_2 }[/math]:

[math]\displaystyle{ z_2^{m_2} \equiv 13 ^ 2 \equiv (-4) ^ 2 \equiv 16 \equiv -1 \pmod{17} \Rightarrow q_2 = 1 }[/math]

Подсчитываем [math]\displaystyle{ z_3 }[/math] и [math]\displaystyle{ m_3 }[/math]:

[math]\displaystyle{ z_3 \equiv z_2 \cdot a^{-q_{2}\cdot2^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} }[/math]

[math]\displaystyle{ m_3 = (p-1)/2^{3+1}= (17 - 1)/2^4 = 1 }[/math]

Находим [math]\displaystyle{ q_3 }[/math]:

[math]\displaystyle{ z_3^{m_3} \equiv 1 ^ 1 \equiv 1 \pmod{17} \Rightarrow q_3 = 0 }[/math]

Находим искомый [math]\displaystyle{ x }[/math]:

[math]\displaystyle{ x = 1 + 1\cdot 2^1 + 1 \cdot 2^2 + 0 \cdot 2^3 \equiv 7 }[/math]

Ответ: [math]\displaystyle{ x=7 }[/math]

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

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

Шаг 2 (вычисление [math]\displaystyle{ \log_a{b}\;\bmod{q_i^{\alpha_i}} }[/math]). 
Для i от 1 до k:
 Пусть
  [math]\displaystyle{ x\equiv\log_a{b}\equiv x_0+x_1q_i+...+x_{\alpha_{i}-1}q_i^{\alpha_{i}-1}\pmod{q_i^{\alpha_i}}, }[/math]
 где
  [math]\displaystyle{ 0\leq x_i\leq q_i-1 }[/math].
 Тогда верно сравнение:
  [math]\displaystyle{ a^{x_0\cdot\frac{p-1}{q_i}} \equiv b^{\frac{p-1}{q_i}} \pmod{p} }[/math]

Вывод верхнего сравнения

Возведём левую и правую части сравнения (1) в степень [math]\displaystyle{ (p-1)/q_i }[/math]:

[math]\displaystyle{ a^{x\cdot \frac{p-1}{q_i}} \equiv b ^ {\frac{p-1}{q_i}} \pmod{p} }[/math]

Подставим [math]\displaystyle{ x }[/math] и преобразуем сравнение:

[math]\displaystyle{ a^{x_0 \cdot \frac{p-1}{q_i} + x_1\cdot(p-1) + x_2\cdot q_i \cdot(p-1) + \dots + x_{\alpha_i - 1} \cdot q_i^{\alpha_i - 2} \cdot (p-1)} \equiv b ^ {\frac{p-1}{q_i}} \pmod{p} }[/math]

[math]\displaystyle{ a^{x_0 \cdot \frac{p-1}{q_i}}\cdot a^{x_1\cdot(p-1)} \cdot a^{x_2\cdot q_i \cdot(p-1)} \cdot \dots \cdot a^{x_{\alpha_i - 1} \cdot q_i^{\alpha_i - 2} \cdot (p-1)} \equiv b ^ {\frac{p-1}{q_i}} \pmod{p} }[/math]

Т.к. [math]\displaystyle{ a }[/math] - примитивный элемент, следовательно верны сравнения вида:

[math]\displaystyle{ a^{m \cdot (p-1)} \equiv 1 \pmod{p},\;\forall m \in \{0,1, \dots, p-1\} }[/math]

Получаем

[math]\displaystyle{ a^{x_0 \cdot \frac{p-1}{q_i}}\cdot 1 \cdot 1 \cdot \dots \cdot 1 \equiv b ^ {\frac{p-1}{q_i}} \pmod{p} }[/math]

[math]\displaystyle{ a^{x_0\cdot\frac{p-1}{q_i}} \equiv b^{\frac{p-1}{q_i}} \pmod{p} }[/math]

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

Шаг 3 (нахождение ответа).
Найдя [math]\displaystyle{ \log_a{b}\;\bmod{q_i^{\alpha_i}} }[/math] для всех i, находим [math]\displaystyle{ \log_a{b}\;\bmod\;(p-1) }[/math] по китайской теореме об остатках.

Пример

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

[math]\displaystyle{ 2^x \equiv 28 \pmod{37} }[/math].

Находим разложение [math]\displaystyle{ \varphi(37) = 37 - 1 = 36 = 2^{2}\cdot3^{2} }[/math].

Получаем [math]\displaystyle{ q_{1} = 2, \alpha_{1} = 2, q_{2} = 3, \alpha_{2} = 2 }[/math].

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

[math]\displaystyle{ r_{20} \equiv 2^{0\cdot\frac{37-1}{2}} \equiv 1 \pmod{37} }[/math]

[math]\displaystyle{ r_{21} \equiv 2^{1\cdot\frac{37-1}{2}} \equiv 2^{18} \equiv -1 \pmod{37} }[/math]

[math]\displaystyle{ r_{30} \equiv 2^{0\cdot\frac{37-1}{3}} \equiv 1 \pmod{37} }[/math]

[math]\displaystyle{ r_{31} \equiv 2^{1\cdot\frac{37-1}{3}} \equiv 2^{12} \equiv 26 \pmod{37} }[/math]

[math]\displaystyle{ r_{32} \equiv 2^{2\cdot\frac{37-1}{3}} \equiv 2^{24} \equiv 10 \pmod{37} }[/math]

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

[math]\displaystyle{ x\equiv x_{0} + x_{1}q_{1} \pmod{q_{1}^{\alpha_i}} \equiv x_{0} + x_{1}\cdot 2 \pmod{2^2} }[/math]

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

[math]\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} }[/math]

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

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

[math]\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} }[/math]

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

[math]\displaystyle{ x \equiv 0 + 1 \cdot 2 \equiv 2 \pmod{4} }[/math]

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

[math]\displaystyle{ x \equiv x_{0} + x_{1}\cdot3 \pmod{3^2} }[/math]

По аналогии находим [math]\displaystyle{ x_{0} }[/math] и [math]\displaystyle{ x_1 }[/math]:

[math]\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 }[/math]

[math]\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 }[/math]

Получаем [math]\displaystyle{ x }[/math]:

[math]\displaystyle{ x \equiv 1 + 2 \cdot 3 \equiv 7\pmod{9} }[/math]

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

[math]\displaystyle{ \begin{cases} x \equiv 2 \pmod{4} \\ x \equiv 7 \pmod{9} \\ \end{cases} }[/math]

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

[math]\displaystyle{ x = 2 + 4 \cdot t \Rightarrow 2 + 4\cdot t \equiv 7 \pmod{9} \Rightarrow 4\cdot t \equiv 5 \pmod{9} \Rightarrow }[/math]

[math]\displaystyle{ t \equiv 5\cdot (4)^{-1} \equiv 5 \cdot (-2) \equiv -10 \equiv 8 \pmod{9} }[/math]

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

[math]\displaystyle{ x \equiv 2 + 4 \cdot 8 \equiv 34 \pmod{36} \equiv 34 \pmod{37} }[/math]

Ответ: [math]\displaystyle{ x = 34 }[/math].

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

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

[math]\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) }[/math], где [math]\displaystyle{ 0\leq r_{i}\leq1 }[/math].

При этом необходимо [math]\displaystyle{ O\left(\log_2{p}\sum\limits_{i=1}^{k}\left(1 + p_i^{r_i}\right)\right) }[/math] бит памяти.

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

[math]\displaystyle{ O\left(\sum\limits_{i=1}^{k}\alpha_i q_i + \log{p}\right) }[/math].

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

[math]\displaystyle{ O\left(\sum\limits_{i=1}^{k}\alpha_i \sqrt{q_i} + \log{p}\right) }[/math].

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

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

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

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

Пример

Верно для простых [math]\displaystyle{ p }[/math] вида [math]\displaystyle{ p=2^{\alpha} + 1,\;p=2^{\alpha_1}3^{\alpha_2} + 1 }[/math].

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

Если имеется простой множитель [math]\displaystyle{ q_i }[/math] такой, что [math]\displaystyle{ q_i\geq p^{c} }[/math], где [math]\displaystyle{ c\geq 0 }[/math].

Применение

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

Замечание

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

Литература

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

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.