COS algoritmus

A COS algoritmus (Coppersmith, Odlyzhko, Shreppel) egy szubexponenciális diszkrét logaritmus algoritmus a maradékok gyűrűjében, prímszám modulo. 1986 -ban javasolták .

Kiinduló adatok

Legyen megadva az összehasonlítás

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

((egy))

Meg kell találni egy x természetes számot , amely kielégíti az (1) összehasonlítást.

Az algoritmus leírása

1. szakasz. Hadd

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

Alkossunk egy halmazt

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

ahol q egyszerű.

2. szakasz. Némi rostálás segítségével olyan párokat keresünk , hogy , ill $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}}

(az abszolút legkisebb levonást vesszük figyelembe). Ugyanakkor azóta is $J=O(p^{{1/2}})$

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

ráadásul ez az abszolút legkisebb maradék ebben az osztályban, és értéke . Ezért a simaságának valószínűsége nagyobb, mint a p -1-nél kisebb tetszőleges számok esetén. $O(p^{{1/2+\epsilon }})$

Ha a logaritmust a bázisban vesszük , megkapjuk a relációt

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

Azt is feltételezhetjük, hogy a sima, azaz

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

ahol

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

3. szakasz. Miután a 2. szakaszban sok egyenletet begépeltünk, megoldjuk a kapott lineáris egyenletrendszert, és megtaláljuk a . $\log _{a}{(H+c)},\ \log _{a}q$

4. szakasz. Az x megtalálásához új simasági határt vezetünk be . Véletlenszerű felsorolással találunk egy w értéket , amely kielégíti az összefüggést $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 "átlagos" nagyságú prímszámok.

5. szakasz A 2. és 3. lépéshez hasonló módszerekkel keressük meg a 4. lépésben felmerült u prímszámok logaritmusát.

6. szakasz Megtaláljuk a választ:

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

Nehézségi fok

Ez az algoritmus az aritmetikai műveletek bonyolultságával rendelkezik. Feltételezzük, hogy számokra ez az algoritmus hatékonyabb, mint a számmezőszita. $O(\exp {((\log {p}\log {\log {p)))^{{1/2)))})$ $p<10^{{90}}$

Irodalom

Vasilenko O.N. Számelméleti algoritmusok a kriptográfiában . - M. : MTSNMO , 2003. - 328 p. — ISBN 5-94057-103-4 .

Joux A., Lercier R. Az általános számmező szita továbbfejlesztései prímmezők diszkrét logaritmusaihoz. Összehasonlítás a Gauss integer módszerrel // Math . Összeg. : folyóirat. - 2003. - 1. évf. 72 . - P. 953-967 . - doi : 10.1090/S0025-5718-02-01482-5 .