Русская Википедия:Алгоритм COS

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

1 этап. Пусть Шаблон:Формула}},\ 0<\epsilon<1.</math>}}

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

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

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

Шаблон:Формулаq^{\alpha_q(c_1,c_2)}\pmod{p}</math>}}

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

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

Логарифмируя по основанию a, получим соотношение Шаблон:Формула\alpha_q(c_1,c_2)\log_aq\pmod{p-1}</math>}}

Мы можем также считать, что a является гладким, то есть Шаблон:Формулаq^{\beta_q}\pmod{p},</math>}} откуда Шаблон:Формула\beta_q\log_aq\pmod{p-1}</math>}}

3 этап. Набрав на 2-м этапе достаточно много уравнений, мы решим получившуюся систему линейных уравнений и найдём <math>\log_a{(H+c)}, \ \log_aq</math>.

4 этап. Для нахождения x введём новую границу гладкости <math>L^2</math>. Случайным перебором находим одно значение w, удовлетворяющее соотношению Шаблон:Формулаq^{\gamma_q}\prod\limits_{L^{1/2}\leq u<L^2}u^{h_u}\pmod{p}.</math>}}

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

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

6 этап. Находим ответ: Шаблон:Формула\gamma_q\log_aq + \sum\limits_{L^{1/2}\leq u<L^2}h_u\log_au\pmod{p-1}.</math>}}

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

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

Литература

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

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