04-07-2023
Алгорим Адлемена — первый субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Алгоритм был предложен Адлеманом в 1979 году.
Содержание |
Пусть задано сравнение
| ((1)) |
Необходимо найти натуральное число x, удовлетворяющее сравнению (1).
1 этап. Сформировать факторную базу, состоящую из всех простых чисел q:
| ({{{2}}}) |
2 этап. С помощью перебора найти натуральные числа такие, что
| ({{{2}}}) |
то есть раскладывается по факторной базе. Отсюда следует, что
| ((2)) |
3 этап. Набрав достаточно много соотношений (2), решить получившуюся систему линейных уравнений относительно неизвестных дискретных логарифмов элементов факторной базы ().
4 этап. С помощью некоторого перебора найти одно начение r, для которого
| ({{{2}}}) |
где — простые числа «средней» величины, то есть , где — также некоторая субэкспоненциальная граница.
5 этап. С помощью вычислений, аналогичных этапам 2 и 3 найти дискретные логарифмы .
6 этап. Определить искомый дискретный логарифм:
| ({{{2}}}) |
Алгоритм Адлемана имеет эвристическую оценку сложности арифметических операций, где некоторая константа. На практике он недостаточно эффективен.
| Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её. |
Алгоритм Адлемана.