Miler—Rabinov test
Miler—Rabinov test je test koji proverava da li je dati broj prost, slično Fermaovom testu za proste brojeve i Solovej—Štrasenovom testu. Originalna verzija testa, koji je osmislio Gari Miler, determinističkog je tipa, ali se determinizam zasniva na opštijoj Rimanovoj hipotezi;[1] Majkl O. Rabin je modifikovao test tako da dobije bezuslovni probabilistički algoritam.[2]
Koncept
urediSlično kao kod Fermaovog i Solovej—Štrasenovog testa, Miler—Rabinov test se zasniva na odrećenim svojstvima koja važe za proste brojeve i proverom da li dati broj ispunjava neki od tih svojstava.
Najpre, lemma o Moavrovim brojevima u konačnom polju Z/pZ, gde je p prost broj i p > 2. Naravno 1 i -1 uvek daju 1 kad se korenuju po modulu p i zovu se trivijalni koreni jedinice. Ne postoje ne trivijalni koreni jedinice. Da bi dokazali ovo pretpostavimo suportno, neka je x koren jedinice po modulu p. Onda:
Drugim rečima, prost broj p deli proizvod (x − 1)(x + 1). Po Euklidovoj lemi on deli i faktore od x − 1 ili odx + 1,, dakle x je kongurentno sa 1 ili 1 po modulup.
Neka je n prost broj i neka je n > 2. Sledi da n − 1 je paran i da možemo ga napisati kao 2s·d, gde su s i d pozitivni celi brojevi(pri čemu je d prost). Za svako a u (Z/nZ)*, važi
ili
za neko 0 ≤ r ≤ s − 1.
Da bi pokazali da je ovo tačno koristićemo malu Fermaovu teoremu, koja kaže da za prost broj n važi:
Po lemi odozgo, ako nastavimo da uzimamo korene od an−1, dobiće se ili 1 ili −1. Ako se dobije −1 onda druga jednakost važi i tu je kraj. Inače, ako nikad ne dobijemo −1, onda smo uzeli sve stepene 2 i ostala nam je prva jednakost.
Miler—Rabinov test se zasniva na kontrapoziciji tvrćenja iznad. To jest, ako možemo da nađemo a takvo da važi
i
za sve 0 ≤ r ≤ s − 1, onda n nije prost broj. Takvo a zovemo svedokom složenosti od n. Inače a se zovejakim lažovom, i n je snažan verovatan prost broj u bazi a. Naziv "jak lažov" se odnosi na slučaj gde je nsložen broj, ali svejedeno jednakosti(svojstva) važe kao i da je prost.
Svaki neparan složen broj n ima mnogo svedoka a, ali nije naćen lak način za nalaženje takvoga. Rešenje je da test bude probabilistički: biramo slučjno a, koje je različito od nule, u Z/nZ i proveravamo da li je ili nije svedok za složenost broja n. Ako je n složen, većina slučajnih izbora zaa će biti takvo da je a svedok, i test će otkriti da je n složen sa veoma velikom verovatnoćom. Ipak postoji mala šansa da za broj a bude izabran jak lažov zan. Može se smanjiti verovatnoću takve greške tako što će se test ponavljati za nekoliko nezavisno izabranih a.
Za testiranje velikih brojeva, uobičajno je da se izabere slučajna baza a, a priori, mi ne znamo raspodelu svedoka i lažova kod brojeva 1, 2, ..., n − 1. Naručito, Arno[3] je dao složen broj od 397 cifara za koji sve baze od a koje su manje od 307 cifara su jaki lažovi. Kao i očekivano, ovaj broj je prijavljen kao prost od strane Maple isprime()
funkcije, koja implementira Miler—Rabinov test proveravajući specifične baze 2, 3, 5,7 i 11. No, odabir nekoliko specifičnih baza može zagarantovati proveru složenih brojeva za n manjih od maksimuma odrećenog tim bazama. Ovaj maksimum je obično dosta velik u odnosu na baze. Kako slučajne baze nemaju takav determinizam za malo n, specifične baze su bolje u nekim uslovima.
Primeri
urediUkoliko bismo hteli da proverimo da li je n = 221 prost broj, prvo bi napisali n − 1 = 220 kao 22·55, tako da je s = 2 i d = 55. Nasumično izaberemo a tako da 0 < a < n, npr. a = 174. Dalje:
- a20·d mod n = 17455 mod 221 = 47 ≠ 1, n − 1
- a21·d mod n = 174110 mod 221 = 220 = n − 1.
Pošto je 220 ≡ −1 mod n, onda je 221 prost, ili 174 je jak lažov za 221. Probamo sa još jednim nasumično izabranim a, ovaj put npr. a = 137:
- a20·d mod n = 13755 mod 221 = 188 ≠ 1, n − 1
- a21·d mod n = 137110 mod 221 = 205 ≠ n − 1.
Stoga 137 je svedok za složenost broja 221, i 174 je zapravo bio jak lažov. Primetimo da nam ovo ne govori ništa o faktorima 221 (tačnije o 13 i 17). No, primer sa 341 u sledećem odeljku pokazuje da ova izračunavanja nekad mogu da nađu faktore od n.
Algoritam i vreme izvršavanja
urediAlgoritam može da se zapiše u sledećem pseudokodu:
Input: n > 3, an odd integer to be tested for primality; Input: k, a parameter that determines the accuracy of the test Output: composite if n is composite, otherwise probably prime write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1 WitnessLoop: repeat k times: pick a random integer a in the range [2, n − 2] x ← ad mod n if x = 1 or x = n − 1 then do next WitnessLoop repeat s − 1 times: x ← x2 mod n if x = 1 then return composite if x = n − 1 then do next WitnessLoop return composite return probably prime
Koristeći modularno stepenovanje (c ≡ be (mod m)) pomoću algoritma brzog stepenovanja kvadriranjem, vreme izvršavanja ovog algoritma je O(k log3n), gde je k broj različih vrednosti broja a kojeg testiramo; tako da je ovo jedan efikasan algoritam koji radi u polinomijalnom vremenu. Koristeći množenje ѕasnovano na brzim Furijeovim transofrmacijama vreme izvršavanja se skraćuje na O(k log2n log log n log log log n) = Õ(k log2n).
Ako ubacimo izračunavanje najvećeg zajedničkog delioca (NZD) u gorenavedeni algoritam, možemo ponekad da dobijemo i činioce broja n nego da samo utvrdimo da li je n složen. Posebno, ako je n verovatan prost za osnovu a ali ne i jak verovatan prost za osnovu a, ili NZD((ad mod n) − 1, n) ili (za neko r iz gorenavedenog opsega) NZD((a2r·d mod n) − 1, n) daje (ne obavezno prost) činilac broja n;videti stranicu 1402.[4] Ako je faktorisanje cilj, onda se ova NZD izračunavanja mogu ubaciti u algoritam po bez prevelikih gubitaka brzine izračunavanja.
Na primer, recimo da je n = 341. Dalje je n − 1 = 85·4.. Zatim 285 mod 341 = 32. Ovo nam govori da n nije jak verovatan prost broj osnove 2, pa znamo da je n složen. Ako primeni NZD u ovom koraku, dobijamo činilac od 341: NZD((285 mod 341) − 1, 341) = 31. Ovo je ispravno jer 341 je pseudo prost u osnovi 2, ali nije i jak pseudoprost u osnovi 2.
U slučaju da algoritam vrati „složen“ jer x = 1, ujedno je i otkriveno da je d2r (neparan umnožak) [Red (teorija grupa)|reda]] broja a -činjenica koja može (kao i uŠorovom algoritmu) da se iskoristi da se n faktoriše, jer n onda deli
ali ne i svaki faktor sam po sebi. Razlog zbog kog Miler—Rabinov test ne daje probabilistički algoritam za [[Rastavljanje na faktore|faktorizaciju]] je to što ako
(drugim rečima, n nije pseudoprost za osnovu a), onda nikakava informacija tog tipa nije dobijena o periodičnosti broja a, i onda algoritam bira drugi „return composite“ izlaz.
Tačnost testa
urediŠto više baza a testiramo, veća je tačnost testa. Može se pokazati da će za svaki neparan složen broj n bar 3/4 baza a biti svedoci za složenost od n.[2][5] Miler—Rabinov test je strogo jači od Solovej—Štrasenovog testa primalnosti u smislu da je za svaki složeni broj n, skup jakih lažova za n podskup skupa Ojlerovih lažova za broj n, i za mnoge n taj potskup je sadržan u celini. Ako je n složeno onda Miler—Rabinov test tvrdi da je n prost sa verovatnoćom od najviše 4−k. Sa druge strane, Solovej—Štrasenov test primalnosti tvrdi da je n prost sa verovatnoćom od najviše 2−k.
Bitno je primetiti da mnogim uobičajenim primenama ovog algoritma, nas ne zanima opseg greške koji je ovde gorenaveden. Taj opseg greške predstavlja verovatnoću da se složen broj proglasi za moguć prost broj posle k krugova testiranja. Umesto toga, često nas zanima verovatnoća da li je, prošavši k krugova testiranja, broj koji ispitujemo zapravo složen. Formalno, ako mi nazovemo događaj proglašavanja n za moguć prost broj posle k krugova Miler—Rabina nazovemo Yk, i ako nazovemo događaj toga da je n složen broj X (I obeležimo događaj toga da je n prost ), onda nam gorenaveden opseg daje , dok sa druge strane nas zanima . Bajesova teorema nam daje način da povežemo ove dve uslovne verovatnoće, naime
- .
Ovo nam govori da verovatnoća koja nas često zanima nije vezana samo za opseg od 4−k, ali i za veravatnoće koje su vezane za gustinu prostih brojeva u okolini broja n.
Dodatno, za velike vrednosti broja n, verovatnoća da je složen broj proglašen kao verovatno prost je u proseku znatno manja od 4−k. Damgord, Lendrok i Pomerans[6] su izračunali neke eksplicitne opsege i pružaju metod za razuman izbor broja k da bi se dobio željeni opseg greške. Takvi opsezi mogu, na primer, da se iskoriste da generišu verovatne proste brojeve; ipak, ne bi se trebalo koristiti da potvrđuju proste brojeve nepoznatog porekla, jer u kriptografskoj primeni neprijatelj može da pokuša da vam pošalje pseudoporst broj tamo gde je potreban prost broj. u takvim slučajevima, može se osloniti samo na opseg greške od 4−k.
Determinističke varijante testa
urediMiler—Rabinov test se može učiniti determinističkim tako što se proba za svako moguće a ispod određene granice. Problem je uglavno da se odredi granica tako da je test još uvek pouzdan.
Ako je broj n koji se testira složen, jaki lažovi a koji su uzajamno prosti sa n se sadrže u strogo manjoj podgrupi grupe (Z/nZ)*, što znači da ako mi testiramo svako a iz skupa koji generiše (Z/nZ)*,, jedan od njih mora biti svedok složenosti broja n. Pretpostavljajući tačnost uopštene Rimanove hipoteze, zna se da grupu generišu njeni elementi manji od O((log n)2), što je Miler i sam bio primetio.[1] Erik Bah je smanjio konstantu koja se bila koristila u Veliko O notaciji na 2[7]. To nas dovodi do sledećeg algoritma za testiranje uslovne primalnosti:
Input: n > 1, an odd integer to test for primality. Output: composite if n is composite, otherwise prime write n−1 as 2s·d by factoring powers of 2 from n−1 repeat for all : if then return composite return prime
Vreme izvršavanja algoritma je Õ((log n)4) (sa množenjem zasnovanim na brzim Furijeovim transofrmacijama). Nisu potrebne sve stavke uopštene Rimanove hipoteze da bi se osigurala tačnost testa. Pošto radimo sa podgrupama parnog indeksa, dovoljno je pretpostaviti tačnost kvadratnih Dirihleovih karaktera.[5]
Milerov test (gore prikazan algoritam) se ne koristi u praksi. U većini slučajeva, korišćenje probabilističkog Miler—Rabinovog testa ili [[Bejli-PSW test primalnosti|Bejli-PSW testa primalnosti]], daje dovoljnu tačnost radeći mnogo brže. Takođe je sporiji u praksi nego uobičajno korišćeni metodi dokazivanja kao što su Ejdlman-Pomerans-Ramlijev test primalnosti, i dokazivanje primalnosti eliptičkom krivom koji daju rezultate koji se ne oslanjaju na nedokazane pretpostavke.
Kada je broj n koji testiramo dovoljno mali, nije potrebno isprobati svako a za koje važi -a < 2(ln n)2-, jer je poznato da su manji skupovi mogućih svedoka dovoljni. Na primer, Pomerans, Selfridž i Vegstaf[8] i Ješke[9] su potvrdili da
- Ako je n < 2.047, dovoljno je da se isproba a = 2;
- Ako je n < 1.373.653, dovoljno je da se isproba a = 2 i 3;
- Ako je n < 9.080.191, dovoljno je da se isproba a = 31 i 73;
- Ako je n < 25.326.001, dovoljno je da se isproba a = 2, 3 i 5;
- Ako je n < 4.759.123.141, dovoljno je da se isproba a = 2, 7 i 61;
- Ako je n < 1.122.004.669.633, dovoljno je da se isproba a = 2, 13, 23 i 1.662.803;
- Ako je n < 2.152.302.898.747, dovoljno je da se isproba a = 2, 3, 5, 7 i 11;
- Ako je n < 3.474.749.660.383, dovoljno je da se isproba a = 2, 3, 5, 7, 11 i 13;
- Ako je n < 341.550.071.728.321, dovoljno je da se isproba a = 2, 3, 5, 7, 11, 13 i 17;
- Ako je n < 3.852.123.056.546.413.051, dovoljno je da se isproba a = 2, 3, 5, 7, 11, 13, 17, 19 i 23;
Treba napomenuti da se Miler—Rabinovi pseudoprosti brojevi nazivaju Snažni pseudoprosti brojevi.
Drugi kriterijumi ov vrste postoje[10][11][12][13] i ovi rezultati daju veoma brze determinističke testove primalnosti za brojeve i prhvatljivom opsegu, a bez ikakvih pretpostavki.
Postoji mala lista mogućih svedoka za svaku moguću veličinu unosa (najviše n vrednosti za n-to bitne brojeve). Ipak, nijedan konačan skup baza nije dovoljan za sve složene brojeve. Alford, Grenvil i Pomerans su pokazali da postoji beskonačno mnogo složenih brojeva n čiji je najmanji svedok složenosti veličine bar -(ln n)1/(3ln ln ln n)-.[14] Oni takođe heurističkim metodama argumentuju da bi najmanji broj w takav da svaki složen broj manji od n ima svedoka složenosti manjeg od w trebalo da bude reda veličine Θ(log n log log n).
Reference
uredi- ^ a b Miller, Gary L. (1976), „Riemann's Hypothesis and Tests for Primality”, Journal of Computer and System Sciences, 13 (3): 300—317, doi:10.1145/800116.803773
- ^ a b Rabin, Michael O. (1980), „Probabilistic algorithm for testing primality”, Journal of Number Theory, 12 (1): 128—138, doi:10.1016/0022-314X(80)90084-0
- ^ F. Arnault (avgust 1995). „Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases”. Journal of Symbolic Computation. 20 (2): 151—161. doi:10.1006/jsco.1995.1042.
- ^ Baillie, Robert; Samuel S. Wagstaff, Jr. (oktobar 1980). „Lucas Pseudoprimes” (PDF). Mathematics of Computation. 35 (152): 1391—1417. MR 583518. doi:10.1090/S0025-5718-1980-0583518-6.
- ^ a b Schoof, René (2004), „Four primality testing algorithms”, Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography (PDF), Cambridge University Press, ISBN 978-0-521-80854-5
- ^ Damgård, I.; Landrock, P. & Pomerance, C. (1993), „Average case error estimates for the strong probable prime test” (PDF), Mathematics of Computation, 61 (203): 177—194, doi:10.2307/2152945
- ^ Bach, Eric (1990), „Explicit bounds for primality testing and related problems”, Mathematics of Computation, 55 (191): 355—380, doi:10.2307/2008811
- ^ Pomerance, Carl; John L. Selfridge, Samuel S. Wagstaff, Jr. (jul 1980). „The pseudoprimes to 25·109” (PDF). Mathematics of Computation. 35 (151): 1003—1026. doi:10.1090/S0025-5718-1980-0572872-7.
- ^ Jaeschke, Gerhard (1993), „On strong pseudoprimes to several bases”, Mathematics of Computation, 61 (204): 915—926, doi:10.2307/2153262
- ^ The Primes Page
- ^ Zhang, Zhenxiang & Tang, Min (2003), „Finding strong pseudoprimes to several bases. II”, Mathematics of Computation, 72 (44): 2085—2097, doi:10.1090/S0025-5718-03-01545-X
- ^ Šablon:SloanesRef
- ^ SPRP Records
- ^ {{Citation |last=Alford|first=W. R. |last2=Granville |first2=A. |last3=Pomerance |first3=C. |lastauthoramp= |year=1994 |title=On the difficulty of finding reliable witnesses |journal=Lecture Notes in Computer Science |volume=877 |publisher=Springer-Verlag |url=http://www.math.dartmouth.edu/~carlp/PDF/reliable.pdf |doi=10.1007/3-540-58691-1_36 |id=}
Spoljašnje veze
uredi- Weisstein, Eric W. „Rabin-Miller Strong Pseudoprime Test”. MathWorld.
- Interaktivna onlajn implementacija determinističke varijante (Korak po korak prikaz rada algortima)
- Aplet(Nemački)
- Miler—Rabinov test primalnosti u C#
- Miler—Rabinov test primalnosti u Javaskriptu koristeći aritmetiku arbitrarne preciznosti