Алгоритм COS

Алгоритм COS

24.02.2021


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

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

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

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

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

1 этап. Пусть

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

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


2 этап. С помощью некоторого просеивания ищем пары c 1 ,   c 2 {displaystyle c_{1}, c_{2}} — такие, что 0 < c i < L 1 / 2 + ϵ {displaystyle 0<c_{i}<L^{1/2+epsilon }} , и


(рассматривается абсолютно наименьший вычет). При этом так как J = O ( p 1 / 2 ) {displaystyle J=O(p^{1/2})} , то


причём это абсолютно наименьший вычет в этом классе и он имеет величину O ( p 1 / 2 + ϵ ) {displaystyle O(p^{1/2+epsilon })} . Поэтому вероятность его гладкости выше, чем для произвольных чисел, меньших p-1.

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

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

откуда


3 этап. Набрав на 2-м этапе достаточно много уравнений, мы решим получившуюся систему линейных уравнений и найдём log a ⁡ ( H + c ) ,   log a ⁡ q {displaystyle log _{a}{(H+c)}, log _{a}q} .

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

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

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

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

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

Данный алгоритм имеет сложность O ( exp ⁡ ( ( log ⁡ p log ⁡ log ⁡ p ) 1 / 2 ) ) {displaystyle O(exp {((log {p}log {log {p}})^{1/2})})} арифметических операций. Предполагается, что для чисел p < 10 90 {displaystyle p<10^{90}} данный алгоритм более эффективен, чем решето числового поля.