Алгоритм COS

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

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


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

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


1 этап. Пусть \}\},\{ 0\textless\{epsilon\textless1.\}\}
 Сформируем множество
 где q — простые.
2 этап. С помощью некоторого просеивания ищем пары c1, c2 — такие, что $0 q\^\{\{alpha\_q(c\_1,c\_2)\}\{pmod\{p\}\}\}
 (рассматривается абсолютно наименьший вычет). При этом так как J=O(p1/2), то
 причём это абсолютно наименьший вычет в этом классе и он имеет величину O(p1/2+ϵ). Поэтому вероятность его гладкости выше, чем для произвольных чисел, меньших p-1.
 Логарифмируя по основанию a, получим соотношение \{alpha\_q(c\_1,c\_2)\{log\_aq\{pmod\{p-1\}\}\}
 Мы можем также считать, что a является гладким, то есть q\^\{\{beta\_q\}\{pmod\{p\},\}\} откуда \{beta\_q\{log\_aq\{pmod\{p-1\}\}\}
3 этап. Набрав на 2-м этапе достаточно много уравнений, мы решим получившуюся систему линейных уравнений и найдём loga(H+c), logaq.
4 этап. Для нахождения x введём новую границу гладкости L2. Случайным перебором находим одно значение w, удовлетворяющее соотношению q\^\{\{gamma\_q\}\{prod\{limits\_\{L\^\{1/2\}\{leq u\}\}
u — простые числа «средней» величины.
5 этап. С помощью методов, аналогичных этапам 2 и 3, мы находим логарифмы простых чисел u, возникших на этапе 4.
6 этап. Находим ответ: \{gamma\_q\{log\_aq + \{sum\{limits\_\{L\^\{1/2\}\{leq u\}\}

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


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