Русская Википедия:Алгоритм Полига — Хеллмана

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

История

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

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

Пусть задано сравнение Шаблон:Формула и известно разложение числа <math>p-1</math> на простые множители: Шаблон:Формула

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

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

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

<math>(a^x)^{(p-1)/{q_i^{\alpha_i}}} \equiv b^{(p-1)/{q_i^{\alpha_i}}} \pmod{p}</math>.Шаблон:Sfn

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

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

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

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

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

<math>a^{p-1}\equiv 1\equiv a^{0}\pmod{p}</math>.

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

<math>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>q_0</math> определяется путём возведения <math>b</math> в степень <math>(p-1)/2 = 2^{n-1}</math> и применением правила

<math>b^{(p-1)/2}\pmod{p}\equiv

\begin{cases}+1, & q_0 = 0\\ -1, & q_0 = 1. \end{cases}</math>

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

<math>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>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>x_1</math> делится на <math>4</math> при <math>q_1=0</math>, а при <math>q_1=1</math> делится на <math>2</math>, а на <math>4</math> уже нет.

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

<math>z_1^{(p-1)/4}\pmod{p}\equiv

\begin{cases}+1, & q_1 = 0\\ -1, & q_1 = 1, \end{cases}</math> из которого находим <math>q_1</math>.

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

<math>m_i=(p-1)/2^{i+1}</math>

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

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

<math> 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>z_i^{m_i}\pmod{p}\equiv

\begin{cases}+1, & q_i = 0\\ -1, & q_i = 1, \end{cases}</math> из которого находим <math>q_i</math>.

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

Пример

Дано:

<math> a = 3,\;b = 11,\;p = 17 = 2^4 + 1</math>

Найти:

<math>x</math>

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

<math>x = q_0 + q_{1}2^1 + q_{2}2^2 + q_{3}2^3</math>

Находим <math>q_0</math>:

<math>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>z_1</math> и <math>m_1</math>:

<math>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>m_1 = (p-1)/2^{1+1}= (17 - 1)/2^2 = 4</math>

Находим <math>q_1</math>:

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

Подсчитываем <math>z_2</math> и <math>m_2</math>:

<math>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>m_2 = (p-1)/2^{2+1}= (17 - 1)/2^3 = 2</math>

Находим <math>q_2</math>:

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

Подсчитываем <math>z_3</math> и <math>m_3</math>:

<math>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>m_3 = (p-1)/2^{3+1}= (17 - 1)/2^4 = 1</math>

Находим <math>q_3</math>:

<math>z_3^{m_3} \equiv 1 ^ 1 \equiv 1 \pmod{17} \Rightarrow q_3 = 0</math>

Находим искомый <math>x</math>:

<math>x = 1 + 1\cdot 2^1 + 1 \cdot 2^2 + 0 \cdot 2^3 \equiv 7</math>

Ответ: <math>x=7</math>

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

Шаг 1 (составление таблицы).
Составить таблицу значений <math>\{r_{i,j}\}</math>, где
 <math>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>\log_a{b}\;\bmod{q_i^{\alpha_i}}</math>). 
Для i от 1 до k:
 Пусть
  <math>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>0\leq x_i\leq q_i-1</math>.
 Тогда верно сравнение:
  <math>a^{x_0\cdot\frac{p-1}{q_i}} \equiv b^{\frac{p-1}{q_i}} \pmod{p}</math>

Шаблон:Вывод \equiv b ^ {\frac{p-1}{q_i}} \pmod{p}</math> Подставим <math>x</math> и преобразуем сравнение:

<math>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>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>a</math> - примитивный элемент, следовательно верны сравнения вида:

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

Получаем

<math>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>a^{x_0\cdot\frac{p-1}{q_i}} \equiv b^{\frac{p-1}{q_i}} \pmod{p}</math>Шаблон:Sfn

}}

 С помощью таблицы, составленной на шаге 1, находим <math>x_0.</math>
 Для j от 0 до <math>\alpha_{i}-1</math> 
  Рассматриваем сравнение
   <math>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>\log_a{b}\;\bmod{q_i^{\alpha_i}}</math> для всех i, находим <math>\log_a{b}\;\bmod\;(p-1)</math> по китайской теореме об остатках.Шаблон:Sfn

Пример

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

<math>2^x \equiv 28 \pmod{37}</math>.

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

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

Составляем таблицу <math>r_{ij}</math>:

<math>r_{20} \equiv 2^{0\cdot\frac{37-1}{2}} \equiv 1 \pmod{37}</math>

<math>r_{21} \equiv 2^{1\cdot\frac{37-1}{2}} \equiv 2^{18} \equiv -1 \pmod{37}</math>

<math>r_{30} \equiv 2^{0\cdot\frac{37-1}{3}} \equiv 1 \pmod{37}</math>

<math>r_{31} \equiv 2^{1\cdot\frac{37-1}{3}} \equiv 2^{12} \equiv 26 \pmod{37}</math>

<math>r_{32} \equiv 2^{2\cdot\frac{37-1}{3}} \equiv 2^{24} \equiv 10 \pmod{37}</math>

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

<math>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>x_{0}</math> из сравнения:

<math>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>x_{0}=0</math> верно выше полученное сравнение.

Находим <math>x_{1}</math> из сравнения:

<math>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>x_{1} = 1</math> верно выше полученное сравнение. Находим <math>x</math>:

<math>x \equiv 0 + 1 \cdot 2 \equiv 2 \pmod{4}</math>

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

<math>x \equiv x_{0} + x_{1}\cdot3 \pmod{3^2}</math>

По аналогии находим <math>x_{0}</math> и <math>x_1</math>:

<math>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>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>x</math>:

<math>x \equiv 1 + 2 \cdot 3 \equiv 7\pmod{9}</math>

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

<math>

\begin{cases}

 x \equiv 2 \pmod{4} \\
 x \equiv 7 \pmod{9} \\

\end{cases} </math> Решим систему. Первое сравнение преобразуем в равенство, которое подставляем во второе сравнение:

<math>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>t \equiv 5\cdot (4)^{-1} \equiv 5 \cdot (-2) \equiv -10 \equiv 8 \pmod{9}</math>

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

<math> x \equiv 2 + 4 \cdot 8 \equiv 34 \pmod{36} \equiv 34 \pmod{37}</math>

Ответ: <math>x = 34</math>.Шаблон:Sfn

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

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

<math>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>0\leq r_{i}\leq1</math>.

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

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

<math>O\left(\sum\limits_{i=1}^{k}\alpha_i q_i + \log{p}\right)</math>.Шаблон:Sfn

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

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

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

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

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

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

Пример

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

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

Если имеется простой множитель <math>q_i</math> такой, что <math>q_i\geq p^{c}</math>, где <math>c\geq 0</math>.Шаблон:Sfn

Применение

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

Замечание

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

Литература

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

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

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

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