Алгоритм COS

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

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

Пусть задано сравнение Шаблон:Формула

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

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

1 этап. Пусть Шаблон:Формула

Сформируем множество Шаблон:Формула

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

2 этап. С помощью некоторого просеивания ищем пары $c_1,c_2$ — такие, что $0<c_i<L^{1/2+ϵ}$, и

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

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

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

Мы можем также считать, что a является гладким, то есть Шаблон:Формула откуда Шаблон:Формула

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

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

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

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

6 этап. Находим ответ: Шаблон:Формула

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

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

Литература

• Шаблон:Книга

• Шаблон:Статья