Алгоритм COS

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

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

${\displaystyle a^{x}\equiv b{\pmod {p}},}$

((1))

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

1 этап. Пусть

${\displaystyle H:=[p^{1/2}]+1,\ J:=H^{2}-p>0,\ L=e^{\sqrt {\log {p}\log {\log {p}}}},\ 0<\epsilon <1.}$

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

${\displaystyle \{q\mid q<L^{1/2}\}\cup \{H+c|0<c<L^{1/2+\epsilon }\},}$

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

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

${\displaystyle (H+c_{1})(H+c_{2})\equiv \prod \limits _{q\leq L^{1/2}}q^{\alpha _{q}(c_{1},c_{2})}{\pmod {p}}}$

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

${\displaystyle (H+c_{1})(H+c_{2})\equiv J+(c_{1}+c_{2})H+c_{1}c_{2}{\pmod {p}},}$

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

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

${\displaystyle \log _{a}{(H+c_{1})}+\log _{a}{(H+c_{2})}\equiv \sum \limits _{q\leq L^{1/2}}\alpha _{q}(c_{1},c_{2})\log _{a}q{\pmod {p-1}}}$

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

${\displaystyle a\equiv \prod \limits _{q\leq L^{1/2}}q^{\beta _{q}}{\pmod {p}},}$

откуда

${\displaystyle 1\equiv \sum \limits _{q\leq L^{1/2}}\beta _{q}\log _{a}q{\pmod {p-1}}}$

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

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

${\displaystyle a^{w}b\equiv \prod \limits _{q\leq L^{1/2}}q^{\gamma _{q}}\prod \limits _{L^{1/2}\leq u<L^{2}}u^{h_{u}}{\pmod {p}}.}$

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

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

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

${\displaystyle x\equiv \log _{a}b\equiv -w+\sum \limits _{q\leq L^{1/2}}\gamma _{q}\log _{a}q+\sum \limits _{L^{1/2}\leq u<L^{2}}h_{u}\log _{a}u{\pmod {p-1}}.}$

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

• Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4.

• Joux A., Lercier R. Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method (англ.) // Math. Comp.^[англ.] : journal. — 2003. — Vol. 72. — P. 953—967. — doi:10.1090/S0025-5718-02-01482-5.