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

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

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

((1))

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

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

({{{2}}})

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

({{{2}}})

то есть  раскладывается по факторной базе. Отсюда следует, что

((2))

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

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

({{{2}}})

где  — простые числа «средней» величины, то есть B < pi < B1, где  — также некоторая субэкспоненциальная граница.

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

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

({{{2}}})

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

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