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

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

История


 Данный алгоритм был придуман американским математиком Роландом Сильвером, но впервые был опубликован другими двумя американскими математикамии Мартином Хеллманом в 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=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 на множители. В общем случае задача факторизации — достаточнотрудоёмкая, однако если делители числа — небольшие (в том смысле, окотором сказано выше), то это число можно быстро разложить на множителидаже методом последовательного деления. Таким образом, в том случае,когда эффективен алгоритм Полига-Хеллмана, необходимость факторизации неусложняет задачу.