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

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

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

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

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

((1))

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

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

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

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

({{{2}}})

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

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

({{{2}}})

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

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

((2))

3 этап. Набрав достаточно много соотношений (2), решить получившуюся систему линейных уравнений относительно неизвестных дискретных логарифмов элементов факторной базы ($\log_a{q}$).

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

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

({{{2}}})

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

5 этап. С помощью вычислений, аналогичных этапам 2 и 3 найти дискретные логарифмы $\log_a{p_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}.$

({{{2}}})

Оценка сложности

Алгоритм Адлемана имеет эвристическую оценку сложности $O(\exp{(c(\log{p}\log{\log{p}})^{1/2})})$ арифметических операций, где $c$ некоторая константа. На практике он недостаточно эффективен.

Литература

• Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4