WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

Алгоритм Полига — Хеллмана (также называемый алгоритм Сильвера — Полига — Хеллмана) — детерминированный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Одной из особенностью алгоритма является то, что для простых чисел специального вида можно находить дискретный логарифм за полиномиальное время.^[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_{i}2^{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_{i}2^{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_{k}2^{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}\cdot 2^{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_{1}q_{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 от 0 до  $q_{i}-1$ 
 
  Рассматриваем сравнение
    $a^{x_{j}\cdot {\frac {p-1}{q_{i}}}}\equiv (ba^{-x_{0}-x_{1}q_{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}\cdot 3^{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}\cdot 3{\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}\leq 1

.

При этом необходимо $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}\alpha _{i}q_{i}+\log {p}\right)

.^[10]

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

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)$ . ^[11]

Алгоритм имеет полиномиальную сложность в общем виде $O\left((\log p)^{c_{1}}\right)$ в случае, когда все простые множители $\left\{q_{i}\right\}_{i=1}^{k}$ не превосходят $(\log p)^{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$ на множители. В общем случае задача факторизации — достаточно трудоёмкая, однако если делители числа — небольшие (в том смысле, о котором сказано выше), то это число можно быстро разложить на множители даже методом последовательного деления. Таким образом, в том случае, когда эффективен алгоритм Полига-Хеллмана, необходимость факторизации не усложняет задачу.

Примечания

Литература

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

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

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

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

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

[_77297a1f27db0a6a-1] 1 2 3 Василенко, 2003, с. 131.

[_41ed1d4056c4d0b5-2] Pohlig et al, 1978.

[_4854b7a61c885c97-3] Odlyzko, 1985, с. 7.

[_f7111d3ec4a3add0-4] 1 2 Коблиц, 2001, с. 113.

[_0d4a53bc13ba53dd-5] Коблиц, 2001, с. 113-114.

[_b3357fec6465cea6-6] Pohlig et al, 1978, с. 108.

[_3331d61c5b4e3615-7] Василенко, 2003, с. 130-131.

[_f7111d3ec4a3add7-8] Коблиц, 2001, с. 114.

[_4854b7a61c885c98-9] Odlyzko, 1985, с. 8.

[_cf8788f4a69305aa-10] Hoffstein et al, 2008, с. 87.

[_b3357fec6465cea7-11] Pohlig et al, 1978, с. 109.