Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

ИсторияПравить

Данный алгоритм был впервые описан американскими математиками Роланом Силвером (Roland Silver), Стефаном Полигом (Stephan Pohlig) и Мартином Хеллманом (Martin Hellman) в 1978 году в статье "An improved algorithm for computing logarithms over GF(p) and its cryptographic significance". Важной особенностью этого метода является то, что для простых чисел специального вида, можно находить дискретный логарифм за полиномиальное время.

Исходные данныеПравить

Пусть задано сравнение

a^x\equiv b\mod{p}, (1)

и известно разложение p-1на простые множители:

p-1=\prod\limits_{i=1}^{s}q_i^{\alpha_i}.

Необходимо найти натуральное число x, удовлетворяющее сравнению (1). Заметим, что на практике всегда рассматривается случай, когда aпервообразный корень по модулю p. В этом случае сравнение (1) имеет решение при любом b, взаимно простом с p.

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

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

(a^{\frac{p-1}{ q_i^{\alpha_i}}})^x\equiv b^{\frac{p-1}{q_i^{\alpha_i}}}\mod{p}. (2)

Данное сравнение решается за полиномиальное время в случае, если q_i - небольшое (то есть, не превосходит (log{p})^c, где c – некоторая константа).

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

1 (составление таблицы). Составить таблицу значений \{r_{i,j}\}, где
 r_{i,j}=a^{j\frac{p-1}{q_i}},
 i\in\{1,...,s\},
 j\in\{1,...,q_i-1\}.

2 (нахождение \log_a{b}\mod{q_i^{\alpha_i}}). 
Для i от 1 до s:
 Пусть
  x\equiv\log_a{b}\mod{q_i^{\alpha_i}}\equiv x_0+x_1q_i+...+x_{\alpha-1}q_i^{\alpha-1}\mod{q_i^{\alpha_i}},
 где
  0\leq x_i\leq q_i-1.
 Тогда из (1) следует, что
  b^{\frac{p-1}{q_i}}\equiv a^{x_0\frac{p-1}{q_i}}\mod{p}
 С помощью таблицы, составленной на шаге 1, находим x_0.
 Для j от 1 до \alpha-1 
  Рассматриваем сравнение
   (ba^{-x_0-...-x_{j-1}})^{\frac{p-1}{q_i^{j+1}}}\equiv a^{x_i\frac{p-1}{q_i}}\mod{p}
  Решение опять же находится по таблице
 Конец цикла по i
Конец цикла по j

3 (нахождение ответа). Найдя \log_a{b}\mod{q_i^{\alpha_i}} для всех i, находим \log_a{b}\mod{p-1} по китайской теореме об остатках.

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

Решение сравнения (1) находится за O(\sum\limits_{i=1}^{s}\alpha_i(\log{p}+q_i)) арифметических операций (см. [1]).

Можно также сказать, что решение находится за O(\sqrt{q}) арифметических операций, где q – наибольший простой делитель p-1 (см. [3]).

Если все простые делители q_i не превосходят (\log{p})^{c_1}, то алгоритм Полига-Хеллмана является полиномиальным и имеет сложность O((\log{p})^{c_2}), где c1,2 – некоторые положительные постоянные.

ПрименениеПравить

Как уже было сказано, алгоритм Полига-Хеллмана крайне эффективен, если p-1 раскладывается на небольшие простые множители. Например, для чисел вида p=2^\alpha+1,\ p=2^\alpha3^\beta+1 и т.д. Если же у p-1 есть большой простой делитель q>p^c,\ 0<c<1, то алгоритм имеет экспоненциальную сложность. Это очень важно учитывать при выборе параметров криптографических схем.

ЗамечаниеПравить

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

ЛитератураПравить

  1. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — Москва: МЦМНО, 2003. — С. 328. ISBN 5-94057-103-4
  2. Pohlig S., Hellmann M. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. — IEEE Trans. Inform. Theory, V.5, 1978. — С. 106-110.
  3. Odlyzko A. M. Discrete logarithms in finite fields and their cryptographic significance // Advances in Crytology: Proceedings of EuroCrypt’84 /Thomas Beth, Norbert Cot, and Igemar Ingemarsson, editors. Berlin: Springer-Verlag, 1984 (Lect. Notes in Computer Science; V. 209). P. 224-316.pl: Redukcja Pohliga-Hellmana

Викия-сеть

Случайная вики