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

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

История


 Данный алгоритм был придуман американским математиком Роландом Сильвером , но впервые был опубликован другими двумя американскими математиками и Мартином Хеллманом в 1978 году в статье «An improved algorithm for computing 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=i=0n1qi2i=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=i=1n1qi2i=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=k=in1qk2k.
  Таким образом, возведение 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)
m3=(p1)/23+1=(171)/24=1
  Находим q3:

zm33111(mod17)q3=0
  Находим искомый x:

x=1+121+122+0237
Ответ: x=7

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


\textttШаг \texttt1 \texttt(составление \textttтаблицы).\\\textttСоставить таблицу значений {ri,j}\texttt, где\\\texttt ri,j=ajp1qi,i{1,,k},j{0,,qi1}.
\textttШаг \texttt2 \texttt(вычисление logabmodqαii\texttt).\texttt \\\textttДля \texttti\texttt от \texttt1\texttt до \textttk\texttt:\\\texttt Пусть\\\texttt  xlogabx0+x1qi+...+xαi1qαi1i(modqαii),\\\texttt где\\\texttt  0xiqi1\texttt.\\\texttt Тогда верно сравнение:\\\texttt  ax0p1qibp1qi(modp)
 \{equiv b \^ \{\{frac\{p-1\}\{q\_i\}\} \{pmod\{p\} Подставим x и преобразуем сравнение:

ax0p1qi+x1(p1)+x2qi(p1)++xαi1qαi2i(p1)bp1qi(modp)
ax0p1qiax1(p1)ax2qi(p1)axαi1qαi2i(p1)bp1qi(modp)
  Т.к. a - примитивный элемент, следовательно верны сравнения вида:

am(p1)1(modp),m{0,1,,p1}
  Получаем

ax0p1qi111bp1qi(modp)
ax0p1qibp1qi(modp)
  \}\}
 \texttt С помощью таблицы, составленной на шаге 1, находим x0.\\\texttt Для \textttj\texttt от 0 до $q_{i-1\texttt \\\texttt  Рассматриваем сравнение\\\texttta^{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Найдя logabmodqαii\texttt для всех \texttti\texttt, находим logabmod(p1)\texttt по китайской теореме об остатках.

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

2x28(mod37).
  Находим разложение φ(37)=371=36=2232.
 Получаем q1=2,α1=2,q2=3,α2=2.
 Составляем таблицу rij:

r102037121(mod37)
r112137122181(mod37)
r202037131(mod37)
r2121371321226(mod37)
r2222371322410(mod37)
  Рассматриваем q1=2. Для x верно:

xx0+x1q1(modqαi1)x0+x12(mod22)
  Находим x0 из сравнения:

ax0p1q1bp1q1(modp)2x0371228371228181(mod37)
  Из таблицы находим, что при x0=0 верно выше полученное сравнение.
 Находим x1 из сравнения:

ax1p1qi(bax0)p1q2i2x13712(2820)37142891(mod37)
  Из таблицы получаем, что при x1=1 верно выше полученное сравнение. Находим x:

x0+122(mod4)
  Теперь рассматриваем q2=3. Для x верно:

xx0+x13(mod32)
  По аналогии находим x0 и x1:

2x03713283713281226(mod37)x0=1
2x13713(2821)3713214410(mod37)x1=2
  Получаем x:

x1+237(mod9)
  Получаем систему:


  \{begin\{cases\}
 \texttt x \{equiv 2 \{pmod\{4\} \{\{\\\texttt x \{equiv 7 \{pmod\{9\} \{\{
 \{end\{cases\} Решим систему. Первое сравнение преобразуем в равенство, которое подставляем во второе сравнение:

x=2+4t2+4t7(mod9)4t5(mod9)
t5(4)15(2)108(mod9)
  Подставляем найденное t и получаем искомое x:

x2+4834(mod36)34(mod37)
  Ответ: x=34.

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


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

O(i=1kαi(log2p+q1rii(1+log2qrii))), где 0ri1.
  При этом необходимо O(log2pi=1k(1+prii)) бит памяти.
 В общем случае сложность алгоритма также можно оценить как

O(i=1kαiqi+logp).
  Если при обработке каждого qi использовать ускоренные методы (например, алгоритм Шенкса), то общая оценка снизится до

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

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


 Когда простые множители {qi}ki=1 малы, то сложность алгоритма можно оценивать как O((log2p)2).
 Алгоритм имеет полиномиальную сложность в общем виде O((logp)c1) в случае, когда все простые множители {qi}ki=1 не превосходят (logp)c2,\\где c1,c2 — положительные постоянные.

agraphПример
 Верно для простых p вида p=2α+1,p=2α13α2+1.

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


 Если имеется простой множитель qi такой, что qipc, где c0.

Применение


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

Замечание


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