COS-algoritm

COS-algoritmen (Coppersmith, Odlyzhko, Shreppel) är en subexponentiell diskret logaritmalgoritm i ringen av rester modulo ett primtal. Det föreslogs 1986 .

Inledande data

Låt jämförelsen ges

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

((ett))

Det är nödvändigt att hitta ett naturligt tal x som uppfyller jämförelsen (1).

Beskrivning av algoritmen

Steg 1. Låta

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

Låt oss bilda en uppsättning

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

där q är enkla.

Steg 2. Med hjälp av lite sållning letar vi efter par som , och $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 minsta avdraget beaktas). Samtidigt sedan , då $J=O(p^{{1/2}})$

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

dessutom är detta den absolut minsta restprodukten i denna klass och den har värdet . Därför är sannolikheten för dess jämnhet högre än för godtyckliga tal mindre än p -1. $O(p^{{1/2+\epsilon }})$

Om vi tar logaritmen i basen 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 också anta att a är jämnt, dvs.

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

var

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

Steg 3. Efter att ha skrivit många ekvationer i det andra steget kommer vi att lösa det resulterande systemet med linjära ekvationer och hitta . $\log _{a}{(H+c)},\ \log _{a}q$

Steg 4. För att hitta x introducerar vi en ny jämnhetsgräns . Genom slumpmässig uppräkning finner vi ett värde w som uppfyller 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 är primtal av "genomsnittlig" magnitud.

Steg 5 Med metoder som liknar steg 2 och 3 hittar vi logaritmerna för primtalstalen u som uppstod i steg 4.

Steg 6 Vi hittar 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årighetsgrad

Denna algoritm har komplexiteten hos aritmetiska operationer. Det antas att för siffror är denna algoritm mer effektiv än talfältssilen. $O(\exp {((\log {p}\log {\log {p)))^{{1/2)))})$ $p<10^{{90}}$

Litteratur

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

Joux A., Lercier R. Förbättringar av den allmänna talfältssikten för diskreta logaritmer i primtalsfält. En jämförelse med den gaussiska heltalsmetoden // Math . Comp. : journal. - 2003. - Vol. 72 . - P. 953-967 . - doi : 10.1090/S0025-5718-02-01482-5 .