Интернет магазин китайских планшетных компьютеров


Компьютеры - Алгоритм Полига Хеллмана - Исходные данные

23 января 2011


Оглавление:
1. Алгоритм Полига Хеллмана
2. Исходные данные
3. Сложность алгоритма



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

a^x\equiv b\pmod{p}, )

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

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

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

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

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

^x\equiv b^{\frac{p-1}{q_i^{\alpha_i}}}\pmod{p}. )

Данное сравнение решается за полиномиальное время в случае, если qi — небольшое, где c — некоторая константа).

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

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

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

Шаг 3. Найдя \log_a{b}\;\bmod{q_i^{\alpha_i}} для всех i, находим \log_a{b}\;\bmod\; по китайской теореме об остатках.


Просмотров: 4041


<<< Алгоритм Диффи Хеллмана
Алгоритм создания цепочек >>>


Компьютерное аппаратное обеспечение   
Вычислительные комплексы   
Компьютерные данные   
Компьютерные журналы   
Классы компьютеров   
Компьютеры   
Программное обеспечение   
Производители компьютеров   
Профессии в ИТ   
Системное администрирование   
Компьютерный сленг   
Списки компьютерных терминов   
Человеко-компьютерное взаимодействие