Алгоритм COS

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

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

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

$a^x\equiv b(\mathrm{mod}p),$

((1))

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

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

1 этап. Пусть

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

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

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

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

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

$(H+c_1)(H+c_2)\equiv \prod _{q\le L^{1/2}}{q}^{{\alpha }_q(c_1,c_2)}(\mathrm{mod}p)$

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

$(H+c_1)(H+c_2)\equiv J+(c_1+c_2)H+c_1{c}_2(\mathrm{mod}p),$

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

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

${\log }_a(H+c_1)+{\log }_a(H+c_2)\equiv \sum _{q\le L^{1/2}}{\alpha }_q(c_1,c_2){\log }_{a}q(\mathrm{mod}p-1)$

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

$a\equiv \prod _{q\le L^{1/2}}{q}^{{\beta }_q}(\mathrm{mod}p),$

откуда

$1\equiv \sum _{q\le L^{1/2}}{\beta }_q{\log }_{a}q(\mathrm{mod}p-1)$

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

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

$a^{w}b\equiv \prod q\le L^{1/2}{q}^{{\gamma }_q}\prod _{L^{1/2}\le u<L^2}{u}^{h_u}(\mathrm{mod}p).$

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

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

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

$x\equiv {\log }_{a}b\equiv -w+\sum q\le L^{1/2}{\gamma }_q{\log }_{a}q+\sum _{L^{1/2}\le u<L^2}{h}_u{\log }_{a}u(\mathrm{mod}p-1).$

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

Данный алгоритм имеет сложность $O(\exp ((\log p\log \log p{)}^{1/2}))$ арифметических операций. Предполагается, что для чисел $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.