Алгоритм COS
Алгоритм COS (Копперсмит, Одлыжко, Шреппель) — субэкспоненциальный алгоритм дискретного логарифмирования в кольце вычетов по модулю простого числа. Был предложен в 1986 году.
Исходные данные
Пусть задано сравнение
| [math]\displaystyle{ a^x\equiv b\pmod{p}, }[/math] | ((1)) |
Необходимо найти натуральное число x, удовлетворяющее сравнению (1).
Описание алгоритма
1 этап. Пусть
| [math]\displaystyle{ H:=[p^{1/2}]+1,\ J:=H^2-p\gt 0,\ L=e^{\sqrt{\log{p}\log{\log{p}}}},\ 0\lt \epsilon\lt 1. }[/math] |
Сформируем множество
| [math]\displaystyle{ \{q\mid q\lt L^{1/2}\}\cup\{H+c|0\lt c\lt L^{1/2+\epsilon}\}, }[/math] |
где q — простые.
2 этап. С помощью некоторого просеивания ищем пары [math]\displaystyle{ c_1,\ c_2 }[/math] — такие, что [math]\displaystyle{ 0\lt c_i\lt L^{1/2+\epsilon} }[/math], и
| [math]\displaystyle{ (H+c_1)(H+c_2)\equiv\prod\limits_{q\leq L^{1/2}}q^{\alpha_q(c_1,c_2)}\pmod{p} }[/math] |
(рассматривается абсолютно наименьший вычет). При этом так как [math]\displaystyle{ J=O(p^{1/2}) }[/math], то
| [math]\displaystyle{ (H+c_1)(H+c_2)\equiv J+(c_1+c_2)H+c_1c_2\pmod{p}, }[/math] |
причём это абсолютно наименьший вычет в этом классе и он имеет величину [math]\displaystyle{ O(p^{1/2+\epsilon}) }[/math]. Поэтому вероятность его гладкости выше, чем для произвольных чисел, меньших p-1.
Логарифмируя по основанию a, получим соотношение
| [math]\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_aq\pmod{p-1} }[/math] |
Мы можем также считать, что a является гладким, то есть
| [math]\displaystyle{ a\equiv\prod\limits_{q\leq L^{1/2}}q^{\beta_q}\pmod{p}, }[/math] |
откуда
| [math]\displaystyle{ 1\equiv\sum\limits_{q\leq L^{1/2}}\beta_q\log_aq\pmod{p-1} }[/math] |
3 этап. Набрав на 2-м этапе достаточно много уравнений, мы решим получившуюся систему линейных уравнений и найдём [math]\displaystyle{ \log_a{(H+c)}, \ \log_aq }[/math].
4 этап. Для нахождения x введём новую границу гладкости [math]\displaystyle{ L^2 }[/math]. Случайным перебором находим одно значение w, удовлетворяющее соотношению
| [math]\displaystyle{ a^wb\equiv\prod{q\leq L^{1/2}}q^{\gamma_q}\prod\limits_{L^{1/2}\leq u\lt L^2}u^{h_u}\pmod{p}. }[/math] |
u — простые числа «средней» величины.
5 этап. С помощью методов, аналогичных этапам 2 и 3, мы находим логарифмы простых чисел u, возникших на этапе 4.
6 этап. Находим ответ:
| [math]\displaystyle{ x\equiv\log_ab\equiv-w+\sum{q\leq L^{1/2}}\gamma_q\log_aq + \sum\limits_{L^{1/2}\leq u\lt L^2}h_u\log_au\pmod{p-1}. }[/math] |
Оценка сложности
Данный алгоритм имеет сложность [math]\displaystyle{ O(\exp{((\log{p}\log{\log{p}})^{1/2})}) }[/math] арифметических операций. Предполагается, что для чисел [math]\displaystyle{ p\lt 10^{90} }[/math] данный алгоритм более эффективен, чем решето числового поля.
Литература
- Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 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.