COS-algoritmi

COS-algoritmi (Coppersmith, Odlyzhko, Shreppel) on subeksponentiaalinen diskreetti logaritmi -algoritmi jäännösrenkaassa , joka modulo alkulukua. Sitä ehdotettiin vuonna 1986 .

Alkutiedot

Esitetään vertailu

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

((yksi))

On tarpeen löytää luonnollinen luku x , joka tyydyttää vertailun (1).

Algoritmin kuvaus

Vaihe 1. Päästää

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

Muodostetaan setti

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

missä q ovat yksinkertaisia.

Vaihe 2. Seulonnan avulla etsimme sellaisia pareja , että , ja $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}}

(absoluuttinen pienin vähennys otetaan huomioon). Samaan aikaan, siitä lähtien $J=O(p^{{1/2}})$

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

lisäksi tämä on ehdottomasti pienin jäännös tässä luokassa ja sen arvo on . Siksi sen tasaisuuden todennäköisyys on suurempi kuin mielivaltaisilla luvuilla, jotka ovat pienempiä kuin p -1. $O(p^{{1/2+\epsilon }})$

Ottamalla logaritmin kannassa a saadaan relaatio

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

Voimme myös olettaa, että a on sileä, eli

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

missä

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

Vaihe 3. Kun olet kirjoittanut paljon yhtälöitä toisessa vaiheessa, ratkaisemme tuloksena olevan lineaariyhtälöjärjestelmän ja löydämme . $\log _{a}{(H+c)},\ \log _{a}q$

Vaihe 4. Löytääksemme x : n otamme käyttöön uuden sileysrajan . Satunnaislaskennan avulla löydämme yhden arvon w , joka tyydyttää suhteen $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 ovat "keskimääräisen" suuruuden alkulukuja.

Vaihe 5 Käyttämällä vaiheiden 2 ja 3 kaltaisia menetelmiä löydämme vaiheessa 4 syntyneiden alkulukujen u logaritmit.

Vaihe 6 Löydämme vastauksen:

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

Vaikeusaste

Tällä algoritmilla on aritmeettisten operaatioiden monimutkaisuus. Oletetaan, että numeroille tämä algoritmi on tehokkaampi kuin lukukenttäseula. $O(\exp {((\log {p}\log {\log {p)))^{{1/2)))})$ $p<10^{{90}}$

Kirjallisuus

Vasilenko O.N. Numeroteoreettiset algoritmit kryptografiassa . - M .: MTSNMO , 2003. - 328 s. — ISBN 5-94057-103-4 .

Joux A., Lercier R. Parannuksia yleislukukentän seulaan diskreeteille logaritmeille alkukentissä. Vertailu Gaussin kokonaislukumenetelmään // Math . Comp. : päiväkirja. - 2003. - Voi. 72 . - s. 953-967 . - doi : 10.1090/S0025-5718-02-01482-5 .