Processing math: 46%

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

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

История


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

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


 Пусть задано сравнение и известно разложение числа p1 на простыемножители:
 Необходимо найти число x,0x<p1, удовлетворяющее сравнению(1).

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


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

(ax)(p1)/qαiib(p1)/qαii(modp).

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


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


 Лучшим путём, чтобы разобраться с данным алгоритмом, будет рассмотрениеособого случая, в котором p=2n+1.
 Нам даны a, p и b, при этом a есть примитивный элемент GF(p) инужно найти такое x, чтобы удовлетворялось axb(modp).
 Принимается, что 0xp2, так как x=p1 неотличимо отx=0, потому что в нашем случае примитивный элемент a по определениюимеет степень p1, следовательно:

ap11a0(modp).
 Когда p=2n+1, легко определить x двоичным разложением cкоэффициентами {q0,q1,,qn1}, например:

x=n1i=0qi2i=q0+q121++qn12n1
 Самый младший бит q0 определяется путём возведения b в степень(p1)/2=2n1 и применением правила

 b\^\{(p-1)/2\}\{pmod\{p\}\{equiv
 \{begin\{cases\}+1, \& q\_0 =0\{\{ -1, \& q\_0 = 1.\{end\{cases\}
 Теперь преобразуем известное разложение и введём новую переменную z1:

baxax1+q0(modp)z1baq0ax1(modp),
 где

x1=n1i=1qi2i=q121+q222++qn12n1
 Понятно, что x1 делится на 4 при q1=0, а при q1=1 делится на2, а на 4 уже нет.
 Рассуждая как раньше, получим сравнение:

 z\_1\^\{(p-1)/4\}\{pmod\{p\}\{equiv
 \{begin\{cases\}+1, \& q\_1 =0\{\{ -1, \& q\_1 = 1,\{end\{cases\} из которого находим q1.
 Оставшиеся биты получаются похожим способом. Напишем общее решениенахождения qi с новыми обозначениями:

mi=(p1)/2i+1
zibaq0q121qi12i1axi(modp),
 где

xi=n1k=iqk2k.
 Таким образом, возведение zi в степень mi даёт:

zmiia(ximi)(a(p1)/2)(xi/2i)(1)xi/2i(1)qi(modp).
 Следовательно:

 z\_i\^\{m\_i\}\{pmod\{p\}\{equiv
 \{begin\{cases\}+1, \& q\_i =0\{\{ -1, \& q\_i = 1,\{end\{cases\} из которого находим qi.
 Найдя все биты, получаем требуемое решение x.

agraphПример
Дано:

a=3,b=11,p=17=24+1\\
Найти:
x Решение:\\Получаем p1=24. Следовательно x имеетвид:

x=q0+q121+q222+q323
 Находим q0:

b(p1)/211(171)/2118(6)8(36)424161(mod17)q0=1
 Подсчитываем z1 и m1:

z1baq01131116662(mod17)
m1=(p1)/21+1=(171)/22=4
 Находим q1:

zm11(2)4161(mod17)q1=1
 Подсчитываем z2 и m2:

z2z1aq121(2)32(2)62(2)36(2)2413(mod17)
m2=(p1)/22+1=(171)/23=2
 Находим q2:

zm22132(4)2161(mod17)q2=1
 Подсчитываем z3 и m3:

z3z2aq222133413921322(4)4161(mod17)
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

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


\textttШаг \texttt1 \texttt(составление\textttтаблицы).\\\textttСоставить таблицу значений \{r_{i,j}\}\texttt, где\\\texttt r_{i,j}=a^{j\cdot\frac{p-1}{q_i}}, i\in\{1,\dots,k\}, j\in\{0,\dots,q_i-1\}.
\textttШаг \texttt2 \texttt(вычисление\log_a{b}\;\bmod{q_i^{\alpha_i}}\texttt).\texttt \\\textttДля \texttti\texttt от \texttt1\texttt до \textttk\texttt:\\\texttt Пусть\\\texttt  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}},\\\texttt где\\\texttt  0\leq x_i\leq q_i-1\texttt.\\\texttt Тогда верно сравнение:\\\texttt  a^{x_0\cdot\frac{p-1}{q_i}} \equiv b^{\frac{p-1}{q_i}} \pmod{p}
 \{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}
 \}\}
 \texttt С помощью таблицы, составленной на шаге 1, находим x_0.\\\texttt Для \textttj\texttt от 0 до $q_{i-1\texttt \\\texttt  Рассматриваем сравнение\\\texttt   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}$\\\texttt  Решение опять же находится по таблице\\\texttt Конец цикла по \textttj\\\textttКонец цикла по \texttti
\textttШаг \texttt3 \texttt(нахождение\textttответа).\\\textttНайдя \log_a{b}\;\bmod{q_i^{\alpha_i}}\texttt для всех \texttti\texttt, находим \log_a{b}\;\bmod\;(p-1)\texttt по китайской теореме об остатках.

agraphПример
 Необходимо найти дискретный логарифм 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\}
 \texttt x \{equiv 2 \{pmod\{4\} \{\{\\\texttt 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.

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


 Если известно разложение (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)бит памяти.
 В общем случае сложность алгоритма также можно оценить как

O\left(\sum\limits_{i=1}^{k}\alpha_i q_i + \log{p}\right).
 Если при обработке каждого qi использоватьускоренные методы (например, алгоритм Шенкса), то общая оценка снизитсядо

O\left(\sum\limits_{i=1}^{k}\alpha_i \sqrt{q_i} + \log{p}\right).
 В указанных оценках подразумевается, что арифметические операции помодулю p выполняются за один шаг. На самом деле это не так —например, сложение по модулю p требует O(log p)элементарных операций. Но поскольку аналогичные уточнения имеют местодля любого алгоритма, данный множитель часто отбрасывается.

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


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

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

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


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

Применение


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

Замечание


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