Алгоритм Адлемана

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

Компьютеры - Алгоритм Адлемана

23 января 2011

Оглавление:
1. Алгоритм Адлемана
2. Оценка сложности

первый субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Алгоритм был предложен Адлеманом в 1979 году.

Исходные данные

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

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

)

Необходимо найти натуральное число x, удовлетворяющее сравнению.

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

1 этап. Сформировать факторную базу, состоящую из всех простых чисел q:

$q\leq B=e^{const\sqrt{\log{p}\log{\log{p}}}}$

2 этап. С помощью перебора найти натуральные числа r_i такие, что

$a^{r_i}\equiv\prod\limits_{q\leq B} q^{\alpha_{iq}}\pmod{p},$

то есть $a^{r_i}\mod{p}$ раскладывается по факторной базе. Отсюда следует, что

$r_i\equiv\sum\limits_{q\leq B} \alpha_{iq}\log_a{q}\pmod{p-1}.$

)

3 этап. Набрав достаточно много соотношений, решить получившуюся систему линейных уравнений относительно неизвестных дискретных логарифмов элементов факторной базы.

4 этап. С помощью некоторого перебора найти одно начение r, для которого

$a^{r}b\equiv\prod\limits_{q\leq B} q^{\beta_q}p_1\cdots p_k\pmod{p},$

где $p_1,\dots,p_k$ — простые числа «средней» величины, то есть B < p_i < B₁, где $B_1 = e^{const\sqrt{\log{p}\log{\log{p}}}}$ — также некоторая субэкспоненциальная граница.

5 этап. С помощью вычислений, аналогичных этапам 2 и 3 найти дискретные логарифмы log_ap_i.

6 этап. Определить искомый дискретный логарифм:

$x \equiv \log_a{b} \equiv -r +\sum\limits_{q\leq B} \beta_{q}\log_a{q} + \sum\limits_{i=1}^{k}\log_a{p_i}\pmod{p-1}.$

<<< Q-метод Полларда дискретного логарифмирования

Алгоритм быстрого возведения в степень >>>

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

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

Человеко-компьютерное взаимодействие