Алгоритм Полига – Хеллмана - Pohlig–Hellman algorithm

Этапы алгоритма Полига – Хеллмана.

В теория групп, то Алгоритм Полига – Хеллмана, иногда упоминается как Алгоритм Сильвера – Полига – Хеллмана,^[1] это специальный алгоритм для вычислений дискретные логарифмы в конечная абелева группа чей заказ гладкое целое число.

Алгоритм был представлен Роландом Сильвером, но впервые опубликован Стивен Полиг и Мартин Хеллман (независимо от серебра).^{[нужна цитата ]}

Группы порядка простой степени

В качестве важного частного случая, который используется в качестве подпрограммы в общем алгоритме (см. Ниже), алгоритм Полига – Хеллмана применяется к группы чей заказ основная сила. Основная идея этого алгоритма состоит в итеративном вычислении ${\displaystyle p}$-адические цифры логарифма путем многократного «сдвига» всех, кроме одной неизвестной цифры в экспоненте, и вычисления этой цифры элементарными методами.

(Обратите внимание, что для удобства чтения алгоритм заявлен для циклических групп - в общем, ${\displaystyle G}$ необходимо заменить на подгруппу ${\displaystyle \langle g\rangle }$ создано ${\displaystyle g}$, который всегда цикличен.)

Вход. Циклическая группа ${\displaystyle G}$ порядка ${\displaystyle n=p^{e}}$ с генератором ${\displaystyle g}$ и элемент ${\displaystyle h\in G}$.

Выход. Уникальное целое число ${\displaystyle x\in \{0,\dots ,n-1\}}$ такой, что ${\displaystyle g^{x}=h}$.

1. Инициализировать ${\displaystyle x_{0}:=0.}$
2. Вычислить ${\displaystyle \gamma :=g^{p^{e-1}}}$. К Теорема Лагранжа, этот элемент имеет порядок ${\displaystyle p}$.
3. Для всех ${\displaystyle k\in \{0,\dots ,e-1\}}$, делать:
   1. Вычислить ${\displaystyle h_{k}:=(g^{-x_{k}}h)^{p^{e-1-k}}}$. По построению порядок этого элемента должен делить ${\displaystyle p}$, следовательно ${\displaystyle h_{k}\in \langle \gamma \rangle }$.
   2. С использованием алгоритм шага младенца гигантский шаг, вычислить ${\displaystyle d_{k}\in \{0,\dots ,p-1\}}$ такой, что ${\displaystyle \gamma ^{d_{k}}=h_{k}}$. Это требует времени ${\displaystyle O({\sqrt {p}})}$.
   3. Набор ${\displaystyle x_{k+1}:=x_{k}+p^{k}d_{k}}$.
4. Возвращаться ${\displaystyle x_{e}}$.

Предполагая ${\displaystyle e}$ намного меньше, чем ${\displaystyle p}$, алгоритм вычисляет дискретные логарифмы по временной сложности ${\displaystyle O(e{\sqrt {p}})}$, намного лучше, чем алгоритм шага младенца гигантский шаг ${\displaystyle O({\sqrt {p^{e}}})}$.

Общий алгоритм

В этом разделе мы представляем общий случай алгоритма Полига – Хеллмана. Основные ингредиенты - это алгоритм из предыдущего раздела (для вычисления логарифма по модулю каждой степени простого числа в групповом порядке) и Китайская теорема об остатках (чтобы объединить их в логарифм в полной группе).

(Опять же, мы предполагаем, что группа является циклической, с пониманием того, что нециклическая группа должна быть заменена подгруппой, порожденной базовым элементом логарифма.)

Вход. Циклическая группа ${\displaystyle G}$ порядка ${\displaystyle n}$ с генератором ${\displaystyle g}$, элемент ${\displaystyle h\in G}$, и разложение на простые множители ${\textstyle n=\prod _{i=1}^{r}p_{i}^{e_{i}}}$.

Выход. Уникальное целое число ${\displaystyle x\in \{0,\dots ,n-1\}}$ такой, что ${\displaystyle g^{x}=h}$.

1. Для каждого ${\displaystyle i\in \{1,\dots ,r\}}$, делать:
   1. Вычислить ${\displaystyle g_{i}:=g^{n/p_{i}^{e_{i}}}}$. К Теорема Лагранжа, этот элемент имеет порядок ${\displaystyle p_{i}^{e_{i}}}$.
   2. Вычислить ${\displaystyle h_{i}:=h^{n/p_{i}^{e_{i}}}}$. По конструкции, ${\displaystyle h_{i}\in \langle g_{i}\rangle }$.
   3. Используя алгоритм выше в группе ${\displaystyle \langle g_{i}\rangle }$, вычислить ${\displaystyle x_{i}\in \{0,\dots ,p_{i}^{e_{i}}-1\}}$ такой, что ${\displaystyle g_{i}^{x_{i}}=h_{i}}$.
2. Решите одновременное сравнение
   $${\displaystyle x\equiv x_{i}{\pmod {p_{i}^{e_{i}}}}\quad \forall i\in \{1,\dots ,r\}{\text{.}}}$$
   Китайская теорема об остатках гарантирует, что существует единственное решение. ${\displaystyle x\in \{0,\dots ,n-1\}}$.
3. Возвращаться ${\displaystyle x}$.

Правильность этого алгоритма можно проверить с помощью классификация конечных абелевых групп: Повышение ${\displaystyle g}$ и ${\displaystyle h}$ к власти ${\displaystyle n/p_{i}^{e_{i}}}$ можно понимать как проекцию на факторную группу порядка ${\displaystyle p_{i}^{e_{i}}}$.

Сложность

Наихудшим входом для алгоритма Полига – Хеллмана является группа простого порядка: в этом случае он деградирует до алгоритм шага младенца гигантский шаг, следовательно, временная сложность наихудшего случая равна ${\displaystyle {\mathcal {O}}({\sqrt {n}})}$. Однако гораздо эффективнее, если порядок плавный: в частности, если ${\displaystyle \prod _{i}p_{i}^{e_{i}}}$ разложение на простые множители ${\displaystyle n}$, то сложность алгоритма равна

$${\displaystyle {\mathcal {O}}\left(\sum _{i}{e_{i}(\log n+{\sqrt {p_{i}}})}\right)}$$

групповые операции.^[2]

Примечания

1. Моллин 2006, стр. 344
2. Menezes, et. al 1997, стр. 108

Рекомендации

• Моллин, Ричард (18 сентября 2006 г.). Введение в криптографию (2-е изд.). Чепмен и Холл / CRC. п.344. ISBN  978-1-58488-618-1.
• С. Полиг и М. Хеллман (1978). «Улучшенный алгоритм вычисления логарифмов по GF (p) и его криптографическая значимость» (PDF). IEEE Сделки по теории информации (24): 106–110.
• Менезеш, Альфред Дж.; ван Оршот, Пол К.; Ванстон, Скотт А. (1997). "Теоретико-числовые справочные задачи" (PDF). Справочник по прикладной криптографии. CRC Press. стр.107–109. ISBN  0-8493-8523-7.