Интернет магазин китайских планшетных компьютеров



Компьютеры - Алгоритм COS

02 июня 2011


Оглавление:
1. Алгоритм COS
2. Оценка сложности



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

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

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

a^x\equiv b\pmod{p}, )

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

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

1 этап. Пусть

H:=+1,\  J:=H^2-p>0,\ L=e^{\sqrt{\log{p}\log{\log{p}}}},\ 0<\epsilon<1.

Сформируем множество

\{q\mid q<L^{1/2}\}\cup\{H+c|0<c<L^{1/2+\epsilon}\},

где q — простые.


2 этап. С помощью некоторого просеивания ищем пары c_1,\ c_2 — такие, что 0 < ci < L, и

\equiv\prod\limits_{q\leq L^{1/2}}q^{\alpha_q}\pmod{p}

. При этом так как J = O, то

\equiv J+H+c_1c_2\pmod{p},

причём это абсолютно наименьший вычет в этом классе и он имеет величину O. Поэтому вероятность его гладкости выше, чем для произвольных чисел, меньших p-1.

Логарифмируя по основанию a, получим соотношение

\log_a{}+\log_a{}\equiv\sum\limits_{q\leq L^{1/2}}\alpha_q\log_aq\pmod{p-1}

Мы можем также считать, что a является гладким, то есть

a\equiv\prod\limits_{q\leq L^{1/2}}q^{\beta_q}\pmod{p},

откуда

1\equiv\sum\limits_{q\leq L^{1/2}}\beta_q\log_aq\pmod{p-1}


3 этап. Набрав на 2-м этапе достаточно много уравнений, мы решим получившуюся систему линейных уравнений и найдём \log_a{}, \ \log_aq.

4 этап. Для нахождения x введём новую границу гладкости L. Случайным перебором нахоим одно значение w, удовлетворяющее соотношению

a^wb\equiv\prod{q\leq L^{1/2}}q^{\gamma_q}\prod\limits_{L^{1/2}\leq u<L^2}u^{h_u}\pmod{p}.

u — простые числа «средней» величины.

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

6 этап. Находим ответ:

x\equiv\log_ab\equiv-w+\sum{q\leq L^{1/2}}\gamma_q\log_aq +  \sum\limits_{L^{1/2}\leq u<L^2}h_u\log_au\pmod{p-1}.


Просмотров: 825


<<< Акшара-санкхья
Алгоритм Диффи Хеллмана >>>