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; Majkl O. Rabin je modifikovao test tako da dobije bezuslovni probabilistički algoritam.

Koncept

Slič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:

$x^{2}\equiv 1{\pmod {p}}$

$(x-1)(x+1)\equiv 0{\pmod {p}}.$

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 2^s·d, gde su s i d pozitivni celi brojevi(pri čemu je d prost). Za svako a u (Z/nZ)*, važi

$a^{d}\equiv 1{\pmod {n}}$

ili

$a^{2^{r}\cdot d}\equiv -1{\pmod {n}}$

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:

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

Po lemi odozgo, ako nastavimo da uzimamo korene od aⁿ⁻¹, 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

$a^{d}\not \equiv 1{\pmod {n}}$

i

$a^{2^{r}d}\not \equiv -1{\pmod {n}}$

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

Ukoliko bismo hteli da proverimo da li je n = 221 prost broj, prvo bi napisali n − 1 = 220 kao 2²·55, tako da je s = 2 i d = 55. Nasumično izaberemo a tako da 0 < a < n, npr. a = 174. Dalje:

• a^20·d mod n = 174⁵⁵ mod 221 = 47 ≠ 1, n − 1
• a^21·d mod n = 174¹¹⁰ 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:

• a^20·d mod n = 137⁵⁵ mod 221 = 188 ≠ 1, n − 1
• a^21·d mod n = 137¹¹⁰ 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

Algoritam 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 ≡ b^e (mod m)) pomoću algoritma brzog stepenovanja kvadriranjem, vreme izvršavanja ovog algoritma je O(k log³n), 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 log²n log log n log log log n) = Õ(k log²n).

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((a^d mod n) − 1, n) ili (za neko r iz gorenavedenog opsega) NZD((a^2r·d mod n) − 1, n) daje (ne obavezno prost) činilac broja n;videti stranicu 1402. 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 2⁸⁵ 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((2⁸⁵ 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 d2^r (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

$a^{d2^{r}}-1=(a^{d2^{r-1}}-1)(a^{d2^{r-1}}+1)$

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

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

(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

Š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. 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 Y_k, i ako nazovemo događaj toga da je n složen broj X (I obeležimo događaj toga da je n prost ${\overline {X}}$), onda nam gorenaveden opseg daje $P(Y_{k}|X)$, dok sa druge strane nas zanima $P(X|Y_{k})$. Bajesova teorema nam daje način da povežemo ove dve uslovne verovatnoće, naime

$P(X|Y_{k})={\frac {P(Y_{k}|X)P(X)}{P(Y_{k}|X)P(X)+P(Y_{k}|{\overline {X}})P({\overline {X}})}}$.

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

Miler—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)²), što je Miler i sam bio primetio. Erik Bah je smanjio konstantu koja se bila koristila u Veliko O notaciji na 2. 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 $a\in [2,\min(n-1,\lfloor 2(\ln n)^{2}\rfloor )]$:
    if $a^{d}\not \equiv 1{\pmod {n}}{\text{ and }}a^{2^{r}\cdot d}\not \equiv -1{\pmod {n}}{\text{ for all }}r\in [0,s-1]$
    then return composite
return prime

Vreme izvršavanja algoritma je Õ((log n)⁴) (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.

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)²-, jer je poznato da su manji skupovi mogućih svedoka dovoljni. Na primer, Pomerans, Selfridž i Vegstaf i Ješke 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 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)}-. 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).

Spoljašnje veze

• 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