COS algoritmus

Algoritmus COS (Coppersmith, Odlyzhko, Shreppel) je subexponenciální diskrétní logaritmický algoritmus v kruhu zbytků modulo prvočíslo. To bylo navrženo v roce 1986 .

Počáteční údaje

Nechť je uvedeno srovnání

a^{x}\equiv b{\pmod {p)),

((jeden))

Je třeba najít přirozené číslo x , které vyhovuje srovnání (1).

Popis algoritmu

Fáze 1. Nechat

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

Vytvořme sadu

\{q\mid q<L^{1/2}}\}\pohár \{H+c|0<c<L^{{1/2+\epsilon }}\},

kde q jsou jednoduché.

Fáze 2. Pomocí nějakého prosévání hledáme páry takové, že , a $c_{1},\ c_{2}$ $0<c_{i}<L^{{1/2+\epsilon }}$

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

(uvažuje se absolutně nejmenší srážka). Zároveň od , tehdy $J=O(p^{{1/2}})$

(H+c_{1})(H+c_{2})\ekviv J+(c_{1}+c_{2})H+c_{1}c_{2}{\pmod {p}},

navíc se jedná o absolutně nejmenší zbytek v této třídě a má hodnotu . Proto je pravděpodobnost jeho hladkosti vyšší než u libovolných čísel menších než p -1. $O(p^{{1/2+\epsilon }})$

Vezmeme-li logaritmus v základu a , dostaneme vztah

\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}}

Můžeme také předpokládat, že a je hladké, tj.

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

kde

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

Fáze 3. Po zadání velkého množství rovnic ve 2. fázi vyřešíme výslednou soustavu lineárních rovnic a najdeme . $\log _{a}{(H+c)},\ \log _{a}q$

Fáze 4. Abychom našli x , zavedeme novou hranici hladkosti . Náhodným výčtem najdeme jednu hodnotu w , která vyhovuje vztahu $L^{2}$

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

u jsou prvočísla "průměrné" velikosti.

Fáze 5 Pomocí metod podobných krokům 2 a 3 najdeme logaritmy prvočísel u , které se objevily v kroku 4.

Fáze 6 Najdeme odpověď:

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

Hodnocení obtížnosti

Tento algoritmus má složitost aritmetických operací. Předpokládá se, že pro čísla je tento algoritmus efektivnější než síto číselného pole. $O(\exp {((\log {p}\log {\log {p)))^{{1/2)))})$ $p<10^{{90}}$

Literatura

Vasilenko O.N. Číselné teoretické algoritmy v kryptografii . - M. : MTSNMO , 2003. - 328 s. — ISBN 5-94057-103-4 .

Joux A., Lercier R. Vylepšení síta obecných číselných polí pro diskrétní logaritmy v prvočíslech. Srovnání s metodou gaussovských celých čísel // Math . Comp. : deník. - 2003. - Sv. 72 . - S. 953-967 . - doi : 10.1090/S0025-5718-02-01482-5 .