- Алгоритм Адлемана
-
Алгорим Адлемена — первый субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Алгоритм был предложен Адлеманом в 1979 году.
Содержание
Исходные данные
Пусть задано сравнение
((1)) Необходимо найти натуральное число x, удовлетворяющее сравнению (1).
Описание алгоритма
1 этап. Сформировать факторную базу, состоящую из всех простых чисел q:
({{{2}}}) 2 этап. С помощью перебора найти натуральные числа
такие, что
({{{2}}}) то есть
раскладывается по факторной базе. Отсюда следует, что
((2)) 3 этап. Набрав достаточно много соотношений (2), решить получившуюся систему линейных уравнений относительно неизвестных дискретных логарифмов элементов факторной базы (
).
4 этап. С помощью некоторого перебора найти одно начение r, для которого
({{{2}}}) где
— простые числа «средней» величины, то есть
, где
— также некоторая субэкспоненциальная граница.
5 этап. С помощью вычислений, аналогичных этапам 2 и 3 найти дискретные логарифмы
.
6 этап. Определить искомый дискретный логарифм:
({{{2}}}) Оценка сложности
Алгоритм Адлемана имеет эвристическую оценку сложности
арифметических операций, где
некоторая константа. На практике он недостаточно эффективен.
Литература
- Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4
Категория:- Теоретико-числовые алгоритмы
Wikimedia Foundation. 2010.