Алгоритм 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\}\{lequ\}\}
u — простые числа «средней» величины.
5 этап. С помощью методов, аналогичных этапам 2 и 3, мы находимлогарифмы простых чисел u, возникших на этапе 4.
6 этап. Находим ответ:\{gamma\_q\{log\_aq +\{sum\{limits\_\{L\^\{1/2\}\{lequ\}\}

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


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