COS algoritme

COS-algoritmen (Coppersmith, Odlyzhko, Shreppel) er en subeksponentiel diskret logaritmealgoritme i ringen af rester modulo et primtal. Det blev foreslået i 1986 .

Indledende data

Lad sammenligning gives

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

((en))

Det er nødvendigt at finde et naturligt tal x , der opfylder sammenligningen (1).

Beskrivelse af algoritmen

Scene 1. Lade

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

Lad os danne et sæt

\{q\midt q<L^{{1/2}}\}\kop \{H+c|0<c<L^{{1/2+\epsilon }}\},

hvor q er simple.

Etape 2. Ved hjælp af nogle sigtning leder vi efter par sådan, at , og $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}}

(det absolut mindste fradrag tages i betragtning). På samme tid, siden da $J=O(p^{{1/2}})$

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

desuden er dette den absolut mindste rest i denne klasse, og den har værdien . Derfor er sandsynligheden for dens glathed højere end for vilkårlige tal mindre end p -1. $O(p^{{1/2+\epsilon }})$

Tager vi logaritmen i basis a , får vi relationen

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

Vi kan også antage, at a er glat, dvs.

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

hvor

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

Etape 3. Efter at have skrevet en masse ligninger på 2. trin, vil vi løse det resulterende system af lineære ligninger og finde . $\log _{a}{(H+c)},\ \log _{a}q$

Etape 4. For at finde x introducerer vi en ny glathedsgrænse . Ved tilfældig opregning finder vi én værdi w , der tilfredsstiller relationen $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 er primtal af "gennemsnitlig" størrelse.

Etape 5 Ved at bruge metoder, der ligner trin 2 og 3, finder vi logaritmerne af de primtal u , der opstod i trin 4.

Etape 6 Vi finder svaret:

x\equiv \log _{a}b\equiv -w+\sum {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}}.

Sværhedsgrad

Denne algoritme har kompleksiteten af aritmetiske operationer. Det antages, at for tal er denne algoritme mere effektiv end talfeltsigten. $O(\exp {((\log {p}\log {\log {p)))^{{1/2)))})$ $p<10^{{90}}$

Litteratur

Vasilenko O.N. Talteoretiske algoritmer i kryptografi . - M .: MTSNMO , 2003. - 328 s. — ISBN 5-94057-103-4 .

Joux A., Lercier R. Forbedringer af den generelle talfeltsigte for diskrete logaritmer i primfelter. En sammenligning med den gaussiske heltalsmetode // Math . Comp. : journal. - 2003. - Bd. 72 . - S. 953-967 . - doi : 10.1090/S0025-5718-02-01482-5 .