Алгоритм Полига

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

История

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

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

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

$a^x\equiv b\pmod{p},$

(1)

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

$p-1=\prod\limits_{i=1}^{k}q_i^{\alpha_i}.$

(2)

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

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

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

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

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

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

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

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

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

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

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

$x = \sum\limits_{i = 0}^{n-1}q_i2^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}\pmod{p}\equiv \begin{cases}+1, & q_0 = 0\\ -1, & q_0 = 1. \end{cases}$

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

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

$a^{p-1}\equiv 1\pmod{p}\Rightarrow a^{(p-1)/2}\equiv\pm 1\pmod{p}$,

но $a$ в степени $(p-1)/2 < p - 1$ по определению принимает значение, отличное от $1$, поэтому остаётся только одно сравнение:

$a^{(p-1)/2}\equiv -1\pmod{p}$.

Возведём сравнение (1) в степень $(p-1)/2$ и подставим выше полученное сравнение:

$b^{(p-1)/2}\equiv (a^x)^{(p-1)/2}\equiv(a^{(p-1)/2})^x\equiv(-1)^x\pmod{p}$

Равенство $(-1)^x=1$ верно, если $x$ чётное, то есть в разложении в виде многочлена свободный член $q_0$ равен $0$, следовательно $(-1)^x = -1$ верно, когда $q_0 = 1$.

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

$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}$,

где

$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}$

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

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

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

из которого находим $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}\pmod{p}$,

где

$x_i = \sum\limits_{k = i}^{n-1}q_k2^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}\pmod{p}$.

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

$z_i^{m_i}\pmod{p}\equiv \begin{cases}+1, & q_i = 0\\ -1, & q_i = 1, \end{cases}$

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

Найдя все биты, получаем требуемое решение $x$.^[6]

Пример

Дано:

$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 \pmod{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 \pmod{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 \pmod{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 \pmod{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 \pmod{17} \Rightarrow q_2 = 1$

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

$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}$

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

Находим $q_3$:

$z_3^{m_3} \equiv 1 ^ 1 \equiv 1 \pmod{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{b}\;\bmod{q_i^{\alpha_i}}$). 
Для i от 1 до k:
 Пусть
  $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}},$
 где
  $0\leq x_i\leq q_i-1$.
 Тогда верно сравнение:
  $a^{x_0\cdot\frac{p-1}{q_i}} \equiv b^{\frac{p-1}{q_i}} \pmod{p}$

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

Возведём левую и правую части сравнения (1) в степень $(p-1)/q_i$:

$a^{x\cdot \frac{p-1}{q_i}} \equiv b ^ {\frac{p-1}{q_i}} \pmod{p}$

Подставим $x$ и преобразуем сравнение:

$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}$

$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}$

Т.к. $a$ - примитивный элемент, следовательно верны сравнения вида:

$a^{m \cdot (p-1)} \equiv 1 \pmod{p},\;\forall m \in \{0,1, \dots, p-1\}$

Получаем

$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}$

$a^{x_0\cdot\frac{p-1}{q_i}} \equiv b^{\frac{p-1}{q_i}} \pmod{p}$^[4]

 С помощью таблицы, составленной на шаге 1, находим $x_0.$
 Для j от 1 до $\alpha_{i}-1$ 
  Рассматриваем сравнение
   $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}$
  Решение опять же находится по таблице
 Конец цикла по j
Конец цикла по i

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

Пример

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

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

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

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

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

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

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

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

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

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

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

$x\equiv x_{0} + x_{1}q_{1} \pmod{q_{1}^{\alpha_i}} \equiv x_{0} + x_{1}\cdot 2 \pmod{2^2}$

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

$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}$

Из таблицы находим, что при $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 \pmod{37}$

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

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

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

$x \equiv x_{0} + x_{1}\cdot3 \pmod{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 \pmod{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 \pmod{37} \Rightarrow x_{1} = 2$

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

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

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

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

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

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

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

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

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

Ответ: $x = 34$.^[8]

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

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

$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)$, где $0\leq r_{i}\leq1$.

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

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

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

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

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

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

Пример

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

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

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

Применение

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

Замечание

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

Примечания

1. ↑ ^{1 2 3} Василенко, 2003, с. 131
2. ↑ Pohlig et al, 1978
3. ↑ Odlyzko, 1985, с. 7
4. ↑ ^{1 2} Коблиц, 2001, с. 113
5. ↑ Коблиц, 2001, с. 113-114
6. ↑ Pohlig et al, 1978, с. 108
7. ↑ Василенко, 2003, с. 130-131
8. ↑ Коблиц, 2001, с. 114
9. ↑ Odlyzko, 1985, с. 8
10. ↑ Hoffstein et al, 2008, с. 87
11. ↑ Pohlig et al, 1978, с. 109

Литература

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

1. Н. Коблиц Курс теории чисел и криптографии. — М.: Научное издательство ТВП, 2001. — 254 с.
2. О. Н. Василенко Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — 1000 экз. — ISBN 5-94057-103-4

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

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. — Т. 1. — № 24. — С. 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. — С. 224-314. — ISBN 0-387-16076-0.
3. J. Hoffstein, J. Pipher, J. H. Silverman An Introduction to Mathematical Cryptography. — Springer, 2008. — 524 с. — ISBN 978-0-387-77993-5

Эта статья выставлена на рецензию. Пожалуйста, выскажите своё мнение о ней на подстранице рецензии.