Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

Исходные данныеПравить

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

a^x\equiv b\mod{p}, (1)

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

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

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

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

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

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

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

r_i\equiv\sum\limits_{q\leq B} \alpha_{iq}\log_a{q}\mod{p-1}. (2)

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

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

a^{r}\equiv\prod\limits_{q\leq B} q^{\beta_q}p_1\cdot...\cdot p_k\mod{p},

где </math>p_1,...,p_k\mod{p}</math> - простые числа "средней" величины, то есть B<p_i<B_1, где 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 \sum\limits_{q\leq B} \beta_{q}\log_a{q} + \sum\limits_{i=1}^{k}\log_a{p_i}\mod{p-1}.

Оценка сложностиПравить

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

ЛитератураПравить

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


Викия-сеть

Случайная вики