Математика
Регистрация
Advertisement

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

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

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

(1)

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

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

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

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

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

(2)

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

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

где </math>p_1,...,p_k\mod{p}</math> - простые числа "средней" величины, то есть , где - также некоторая субэкспоненциальная граница,

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

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

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

Данный алгоритм имеет эвристическую оценку сложности арифметических операций, где некоторая константа. На практике он недостаточно эффективен.

Литература[]

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


Advertisement