Nightingale-Strassen teszt

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. január 3-án felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

A Nightingale-Strassen teszt egy valószínűségi primalitási teszt , amelyet az 1970-es években Robert Martin Nightingale és Volker Strassen fedezett fel. [1] A teszt mindig helyesen határozza meg, hogy egy prímszám prím, de összetett számokra bizonyos valószínűséggel helytelen választ adhat. A teszt fő előnye, hogy a Fermat-teszttel ellentétben a Carmichael-számokat összetettként ismeri fel .

Történelem

A 17. században Fermat bebizonyította a később Fermat kis tételének nevezett állítást, amely Fermat primalitástesztjének alapjául szolgál :

Ha n prím, és a nem osztható n -nel , akkor .

a^{n-1} \equiv 1\pmod{n}

Ez az ellenőrzés egy adott n -re nem igényel sok számítást, de fordítva nem igaz. Így vannak olyan Carmichael-számok, amelyek összetettek, amelyekre a Fermat-féle kis tételben adott állítás minden adott számmal rendelkező másodlagos egészre érvényes. 1994-ben kimutatták, hogy végtelenül sok ilyen szám létezik. [2] A Fermat-teszt feltárt hiányossága kapcsán aktuálissá vált a valószínűségi tesztek megbízhatóságának növelésének problémája. Lehmann volt az első, aki olyan tesztet javasolt, amely a Carmichael-számokat összetettként szűri ki. Ez a hiányosság a Solovey-Strassen- és Miller-Rabin-tesztekből sem hiányzik, mivel a kimaradási kritérium erősebb, mint Fermat kis tétele. Egymástól függetlenül D. Lemaire 1976-ban és R. Nightingale F. Strassennel 1977-ben bebizonyította, hogy nincs analógja az összetett és egyben Euler-féle álegyszerű Carmichael-számoknak. [3] Ennek alapján javasolták a Solovay-Strassen-féle elsődlegességi tesztet, amely 1977-ben jelent meg, kiegészítései 1978-ban.

Indoklás

A Solovay-Strassen teszt Fermat kis tételén és a Jacobi szimbólum tulajdonságain alapul [4] :

Ha n páratlan összetett szám , akkor azoknak a egész számoknak a száma , amelyek n -nel együtt prímek és n -nél kisebbek , amelyek kielégítik az összehasonlítást , nem haladja meg a -t . $\textstyle a^{{(n-1)/2}}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$ ${\frac {n}{2))$

Az összehasonlítást kielégítő n összetett számokat a bázisban Euler-Jacobi pszeudoprímeknek nevezzük .

Bizonyíték [5]

Bizonyítsuk be, hogy az összehasonlítás szükséges és elegendő ahhoz, hogy az n szám prím legyen. $a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$

A szükségszerűség a Legendre szimbólumra vonatkozó Euler-kritériumból következik . Az elégséges bizonyításhoz az ellentmondásos módszert alkalmazzuk. Tételezzük fel, hogy n összetett, és ezzel egyidejűleg az összehasonlítást végezzük . Ebből azt kapjuk, hogy n egy Carmichael-szám, tehát ahol egy prím i = 1,2, ...k

\forall a\in \mathbf {Z_{n}}

a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}

a^{n-1}=(a^{(n-1)/2})^{2}=\left({\frac {a}{n}}\right)^{2}

\left({\frac {a}{n}}\right)^{2}=1

a^{n-1}=1(modn)

{\displaystyle n=p_{1}p_{2}..p_{k))

{\displaystyle p_{i))

Tekintsük b -t olyannak, hogy Keressünk egy olyan a -t , hogy: Egy ilyen létezik a kínai maradéktétel szerint , és -hez tartozik , mivel n -hez koprím . Innen ered az ellentmondás azzal a ténnyel, hogy tehát hamis az a feltevésünk, hogy n összetett.

\left({\frac {b}{p_{1}}}\right)=-1(modn)

a={\begin{cases}b(mod{p_{1))),&{\mbox{if }}i{\mbox{= 1}}\\1(mod{p_{i}} ),&{\mbox{if }}i{\mbox{ = 2,...,k}}\end{cases}}

Z_{n}

\left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_ {2}}}\jobbra)....\left({\frac {a}{p_{k}}}\right)=\left({\frac {a}{p_{1}}}\jobbra )=\left({\frac {b}{p_{1}}}\right)=-1

a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}

\left({\frac {a}{n}}\right)=-1

a^{(n-1)/2}\equiv \ -1(modn)

a^{(n-1)/2}\equiv \ -1(modp_{1})

a^{(n-1)/2}\equiv \ -1(modp_{2})

a\equiv \ 1(modp_{i})

Annak bizonyítéka, hogy az ilyen számok száma nem haladja meg az n/2-t, bármelyik számelméleti algoritmus tankönyvben megtalálható. [négy]

A Solovay-Strassen algoritmus

A Solovay-Strassen algoritmust [6] a k körök számával paraméterezzük . Minden körben véletlenszerűen kiválasztunk egy a < n számot . Ha gcd ( a , n ) > 1, akkor n összetett. Ellenkező esetben az összehasonlítás érvényességét ellenőrizzük . Ha nem teljesül, akkor az a döntés születik, hogy n összetett. Ha ez az összehasonlítás igaz, akkor a tanúja az n prímnek . Ezután egy másik véletlen a -t választunk , és az eljárást megismételjük. Miután k körben találtunk k primalitástanút , arra a következtetésre jutunk, hogy n egy valószínűségű prímszám . $\textstyle a^{(n-1)/2}\equiv \left({a \over n}\right){\pmod {n))$ ${\displaystyle \textstyle 1-2^{-k))$

A pszeudokódban az algoritmus a következőképpen írható fel:

Bemenet : > 2, tesztelje a páratlan természetes számot; , a teszt pontosságát meghatározó paraméter. Kimenet : kompozit , pontosan kompozitot jelent; valószínűleg prím azt jelenti, hogy valószínűleg prím.

n

k

n

n

ha i = 1, 2, ..., : = véletlenszerű egész szám 2-től ig , beleértve; ha gcd (a, n) > 1, akkor : print , ami összetett, és stop . if , akkor : összetett kimenet , és stop . _

k

a

n-1

n

a^{(n-1)/2}\not \equiv \left({a \over n}\right){\pmod {n))

n

ellenkező esetben származtassa , ami valószínűséggel prím , és állítsa le .

n

{\displaystyle \textstyle 1-2^{-k))

Példa az algoritmus alkalmazására

Ellenőrizzük az n = 19 számot az egyszerűség kedvéért. A k = 2 pontossági paramétert választjuk.

k = 1 Válasszunk egy véletlen számot a = 11; 2 < a < n - 1 Ellenőrizze a gcd(a,n)>1 feltételt gcd(11,19)=1; majd ellenőrizzük az összehasonlítást , ezt kaptuk, ezért továbblépünk a következő iterációra

\textstyle a^{{(n-1)/2}}\equiv \left({\frac {a}{n}}\right){\pmod {n}}

r=\left({\frac {a}{n}}\right)=\left({\frac {11}{19}}\right)=1

\textstyle s=a^{(n-1)/2}=11^{(19-1)/2}{\pmod {19}}=1

\textstyle r=s

k = 2 Válasszunk egy véletlen számot a = 5; 2 < a < n - 1 Ellenőrizze a gcd(a,n)>1 feltételt gcd(5,19)=1; ezért ellenőrizzük az összehasonlítást , és ez volt az utolsó iteráció, ezért arra a következtetésre jutunk, hogy a 19 egy prímszám, amelynek valószínűsége

\textstyle a^{{(n-1)/2}}\equiv \left({\frac {a}{n}}\right){\pmod {n}}

r=\left({\frac {a}{n}}\right)=\left({\frac {5}{19}}\right)=1

\textstyle s=a^{(n-1)/2}=5^{(19-1)/2}{\pmod {19}}=1

\textstyle r=s

1-2^{-2}

Számítási összetettség és pontosság

Pontosság más valószínűségi primalitási tesztekhez képest (itt k a független körök száma)

teszt neve	valószínűség( hogy a szám összetett ) [7]	jegyzetek
Tanya	${\displaystyle 2^{-k))$	nem ismeri fel a Carmichael-számokat összetettnek
Lehmann	${\displaystyle 2^{-k))$
Nightingale - Strassen	${\displaystyle 2^{-k))$

A táblázatban szereplő összes teszt számításának elméleti bonyolultságát a következőre becsüljük . [3] $O(\log^3n)$
Az algoritmus műveleteket igényel hosszú egész számokon . [egy] $O(k\log _{2}m)$
Az algoritmus megvalósítása során a számítási bonyolultság csökkentése érdekében az a számokat a 0 < a < c < n intervallumból választjuk ki , ahol c egy processzor regiszterbe illeszkedő természetes szám maximális lehetséges értékével egyenlő konstans. [6]

Alkalmazás

Valószínűségi teszteket használnak a faktorizációs problémán alapuló rendszerekben , mint például az RSA vagy a Rabin-séma . A gyakorlatban azonban a Solovey-Strassen teszt megbízhatósági foka nem elegendő, helyette a Miller-Rabin tesztet használják . Sőt, kombinált algoritmusokkal, mint például a próbaosztás és a Miller-Rabin teszt, a paraméterek megfelelő megválasztásával jobb eredményeket érhet el, mint az egyes teszteket külön-külön. [7]

Javítás tesztelése

2005-ben a Bit+ "Információs Technológiák -2005" Nemzetközi Konferencián A. A. Balabanov, A. F. Agafonov, V. A. Ryku korszerűsített Solovay-Strassen tesztet javasolt. A Nightingale-Strassen teszt a Jacobi-szimbólum kiszámításán alapul, ami a -val egyenértékű időt vesz igénybe . A javítás ötlete az, hogy a Gauss-féle másodfokú reciprocitás tételének megfelelően menjen a Jacobi-szimbólum reciproka értékének kiszámításához, ami egy egyszerűbb eljárás. [8] . $\log _{2}n$ $\left({\frac {n}{a))\right)$

Lásd még

Pseudoprime

Jegyzetek

↑ 1 2 Solovay, Robert M. és Volker Strassen. Gyors Monte-Carlo teszt az elsődlegességért // SIAM Journal on Computing : folyóirat. - 1977, benyújtva 1974-ben . 6 , sz. 1 . - 84-85 . o . - doi : 10.1137/0206006 .
↑ WR Alford, A. Granville, C. Pomerance. Végtelenül sok Carmichael-szám van // Annals of Mathematics : folyóirat . - 1994. - 1. évf. 139 . - P. 703-722 . - doi : 10.2307/2118576 . Archiválva az eredetiből 2012. május 4-én.
↑ 1 2 Cserjomuskin, 2001 , p. 48.
↑ 1 2 Neszterenko, 2011 , p. 82.
↑ N.Yu. Arany . Előadások a számítógépes algebráról. 6. előadás Carmichael tétele Nightingale - Strassen teszt. Archiválva : 2014. november 4. a Wayback Machine -nél
↑ 1 2 Neszterenko, 2011 , p. 84.
↑ 1 2 B. Schneier Alkalmazott kriptográfia - M.: TRIUMPH, 2002. — 11. fejezet.
↑ Balabanov A. A., Agafonov A. F., Ryku V. A. Algoritmus gyors kulcsgeneráláshoz az RSA kriptográfiai rendszerben. 2014. november 5-én kelt archív másolat a Wayback Machine -nél – Tudományos és Műszaki Fejlesztési Közlemény, 2009. 7. szám (23). - S. 11.

Irodalom

Koblitz N. Számelméleti és kriptográfiai tanfolyam . - 2. - M . : TVP Tudományos Kiadó, 2001. - S. 149 - 160. - 254 p. — ISBN 5-94057-103-4 .
Neszterenko A. Bevezetés a modern kriptográfiába Számelméleti algoritmusok . - 2011. - S. 79 - 90. - 190 p. - ISBN 978-5-94506-320-4 .
Cheremushkin AV Előadások a kriptográfiai aritmetikai algoritmusokról . - M. : MTSNMO , 2001. - S. 42 - 59. - 104 p. — ISBN 5-94057-060-7 . Archiválva : 2013. május 31. a Wayback Machine -nél
Salomaa A. Nyilvános kulcsú titkosítás / Per. angolról. I.A. Vihljantsev. - M. : Mir, 1995. - S. 176 - 184. - 318 p. — ISBN 5-03-001991-X . Archiválva : 2011. november 19. a Wayback Machine -nél

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus