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



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

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 этап. С помощью перебора найти натуральные числа ri такие, что

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 < pi < B1, где B_1 = e^{const\sqrt{\log{p}\log{\log{p}}}} — также некоторая субэкспоненциальная граница.

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

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}.


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


<<< Q-метод Полларда дискретного логарифмирования
Алгоритм быстрого возведения в степень >>>