Interested Article - Алгоритм COS

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

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

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

((1))

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

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

1 этап. Пусть

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

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


2 этап. С помощью некоторого просеивания ищем пары — такие, что , и


(рассматривается абсолютно наименьший вычет). При этом так как , то


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

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

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

откуда


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

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

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

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

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

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

Данный алгоритм имеет сложность арифметических операций. Предполагается, что для чисел данный алгоритм более эффективен, чем решето числового поля.

Литература

  • Joux A., Lercier R. (англ.) // (англ.) : journal. — 2003. — Vol. 72 . — P. 953—967 . — doi : .
Источник —

Same as Алгоритм COS