Miller-Rabinin testi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 24.9.2020 tarkistetusta versiosta . tarkastukset vaativat 7 muokkausta .

Miller-Rabinin testi on todennäköisyyspohjainen polynomiprimaaliteettitesti . Miller-Rabin-testi sekä Fermat -testi ja Solovay-Strassen-testi voivat tehokkaasti määrittää, onko tietty luku yhdistetty . Sitä ei kuitenkaan voida käyttää tiukasti todistamaan , että luku on alkuluku . Miller-Rabin-testiä käytetään kuitenkin usein kryptografiassa suurten satunnaisalkulukujen luomiseen .

Historia

Miller-Rabin-algoritmi on muunnos Gary Millerin vuonna 1976 kehittämään Millerin algoritmiin . Millerin algoritmi on deterministinen , mutta sen oikeellisuus perustuu todentamattomaan laajennettuun Riemannin hypoteesiin [1] . Michael Rabin muokkasi sitä vuonna 1980 [2] . Miller-Rabin-algoritmi ei riipu hypoteesin pätevyydestä, vaan on todennäköisyys.

Sovellus

Koska monien salausalgoritmien kryptografinen vahvuus perustuu salaisiin avaimiin, joiden luomiseen tarvitaan alkulukuja (esimerkiksi näin RSA -salaus toimii ), tällaisia avaimia luotaessa on tärkeää pystyä nopeasti tarkistamaan suuria lukuja. ensisijaisuus. Todennäköisyyspohjaiset primaliteettitestit, kuten Miller-Rabin-testi ja Solovay-Strassen-testi , osoittavat tehokkaampaa käyttöä ja ilmaisun helppoutta deterministisiin testeihin verrattuna [3] . Miller-Rabin-algoritmin avulla voit suorittaa tarkistuksen lyhyessä ajassa ja antaa samalla melko pienen todennäköisyyden, että luku on todella yhdistetty. [neljä]

Miten algoritmi toimii

Kuten Fermat- ja Nightingale-Strassen- testit, Miller-Rabin-testi perustuu alkulukujen pätevien yhtälöiden tarkistamiseen. Jos ainakin yksi tällainen yhtälö epäonnistuu, se osoittaa, että luku on yhdistetty [5] .

Miller-Rabin-testissä käytetään seuraavaa lausetta:

Antaa olla alkuluku ja , Missä on pariton. Sitten vähintään yksi seuraavista ehdoista täyttyy: $n$ $n-1=2^{s}d$ $d$ $a$ $\mathbb {Z} _{n}$

$a^{d}\equiv 1{\pmod {n))$
On olemassa sellainen kokonaisluku $r<s$ $a^{2^{r}d}\equiv -1{\pmod {n))$

Todiste Lemma yksikön neliöjuurista äärellisessä kentässä :

\mathbb {Z} _{p}

Viimeisessä kentässä (alkuluvulle ) ei ole yksikön neliöjuuria lukuun ottamatta numeroita 1 , -1 $\mathbb {Z} _{p}$ $s$

Todiste

Päästää:

{a} \equiv {\sqrt{1} }\pmod{p}

Sitten:

a^{2} \equiv 1\pmod{p}

a^{2} {-1}\equiv 0\pmod{p}

(a + 1)( a - 1) \equiv 0\pmod{p}

Eukleideen lemman mukaan :

\bigg [ \begin{matrix} {a - 1} \equiv {0}\pmod{p} \\ {a + 1} \equiv {0}\pmod{p} \end{matrix}

\bigg [ \begin{matrix} {a}\equiv {1}\pmod{p} \\ {a}\equiv {-1}\pmod{p} \end{matrix}

Fermatin pienen lauseen mukaan :

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

Poimimme luvun neliöjuuret . Yllä todistetun lemman mukaan jokaisessa vaiheessa saamme luvun 1 tai -1 modulo . Jos jossain vaiheessa saamme -1 , niin toinen yhtälöistä täyttyy. Muuten viimeisessä vaiheessa (koska ), eli ensimmäinen yhtäläisyys täyttyy. $a^{n-1}$ $n$ ${\sqrt[{{2}^{s}}]{a^{n-1}}}=a^{d}$ $n-1=2^{s}d$

Jos tämä lause (ehto 1 tai 2) täyttyy joillekin luvuille ja (ei välttämättä alkuluku), niin lukua kutsutaan Millerin alkuluvuksi ja itse lukua kutsutaan todennäköiseksi alkuluvuksi . (Satunnaisesti on 25 %:n mahdollisuus sekoittaa yhdistelmäluku alkuluvuksi, mutta tätä voidaan pienentää tarkistamalla muita lukuja .) $a$ $n$ $a$ $n$ $n$ $a$ $a$

Siinä tapauksessa , että todistetun väitteen ristiriitaisuus täyttyy, eli jos on luku , joka: $a$

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

\forall r:\ 0\le r\le s-1:\ a^{2^rd} \not\equiv -1\pmod{n},

silloin luku ei ole alkuluku. Tässä tapauksessa numeroa kutsutaan todistajaksi, että numero on yhdistetty. $n$ $a$ $n$

Parittomille yhdistelmäluvuille Rabinin lauseen mukaan ei ole enää yksinkertaisuuden todistajia, missä on Euler-funktio , joten todennäköisyys, että satunnaisesti valittu luku on yksinkertaisuuden todistaja, on pienempi kuin 1/4 [2] [6] . $n$ $\varphi (n)/4$ $\varphi (n)$ $a$

Testin ideana on tarkistaa satunnaisesti valitut luvut , ovatko ne todistajia luvun ensimäisyydestä . Jos on näyttöä siitä, että luku on yhdistelmä, luku on todellakin yhdistelmä. Jos luvut tarkistettiin ja ne kaikki osoittautuivat alkuluvuiksi, lukua pidetään alkulukuna. Tällaisella algoritmilla todennäköisyys ottaa yhdistelmäluku alkuluvulle on pienempi [7] . $a<n$ $n$ $k$ $(1/4)^{k}$

Suurten lukujen tarkistamiseksi on tapana valita satunnaisia lukuja, koska primaalisuuden todistajien ja yhdistelmäluvun todistajien jakautumista lukujen 1, 2, ..., n − 1 kesken ei tiedetä etukäteen. Erityisesti Arnolt [8] antaa 397-bittisen yhdistelmäluvun, jolle kaikki alle 307:n luvut ovat todisteita yksinkertaisuudesta. $a$

Esimerkki

Oletetaan, että haluamme määrittää, onko n = 221 alkuluku. Kirjoitetaan n − 1 = 220 arvoksi 2 2 55, joten s = 2 ja d = 55. Valitsemme mielivaltaisesti luvun a siten, että 0 < a < n , oletetaan a = 174. Jatketaan laskutoimituksia:

a 2 0 d mod n = 174 55 mod 221 = 47 ≠ 1, n − 1
a 2 1 d mod n = 174 110 mod 221 = 220 = n − 1.

Koska 220 ≡ −1 mod n , 221 on joko alkuluku tai 174 on väärä todistus siitä, että 221 on alkuluku. Otetaan toinen mielivaltainen a , tällä kertaa valitsemalla a = 137:

a 2 0 d mod n = 137 55 mod 221 = 188 ≠ 1, n − 1
a 2 1 d mod n = 137 110 mod 221 = 205 ≠ n − 1.

Koska 137 on todiste siitä, että 221 on yhdistetty, luku 174 oli itse asiassa väärä todistus yksinkertaisuudesta. Huomaa, että algoritmi ei kerro meille mitään 221:n tekijöistä (jotka ovat 13 ja 17). Joissakin tapauksissa lisälaskelmat auttavat kuitenkin saamaan luvun tekijät. [9]

Miller-Rabin-algoritmi

Toteutus

Miller-Rabin-algoritmi parametroidaan kierrosten lukumäärällä r . On suositeltavaa ottaa r suuruusluokkaa , jossa n on testattava luku. $\log_2(n)$

Tietylle n :lle on olemassa kokonaisluku s ja pariton kokonaisluku t siten, että . Valitaan satunnaisluku a , 1 < a < n . Jos a ei todista luvun n alkuvoimaa, annetaan vastaus "n on yhdistetty" ja algoritmi päättyy. Muussa tapauksessa valitaan uusi satunnaisluku a ja varmennusmenettely toistetaan. Kun on löydetty r todisteita yksinkertaisuudesta, annetaan vastaus "n on luultavasti alkuluku" ja algoritmi päättyy [5] . $n-1 = 2^st$

Algoritmi voidaan kirjoittaa pseudokoodilla seuraavasti:

Syöte : n > 2, pariton luonnollinen luku, joka testataan primaalisuuden suhteen; k on kierrosten lukumäärä. Tulos : komposiitti tarkoittaa, että n on yhdistelmäluku; luultavasti alkuluku tarkoittaa, että n on erittäin todennäköisesti alkuluku. Arvon n − 1 esittäminen muodossa 2 s · t , jossa t on pariton, voidaan tehdä jakamalla n - 1 peräkkäin kahdella. Silmukka A: toista k kertaa: Valitse satunnainen kokonaisluku a väliltä [2, n − 2] x ← a t mod n , joka lasketaan eksponentiointialgoritmilla modulo , jos x = 1 tai x = n − 1, ja siirry sitten silmukan A silmukan B seuraavaan iteraatioon : toista s − 1 kertaa x ← x 2 mod n jos x = 1, sitten palauttaa yhdisteen , jos x = n − 1, sitten siirry silmukan seuraavaan iteraatioon A palauttaa yhdisteen palauttaa luultavasti alkuluvun

Rabinin lauseesta seuraa, että jos k satunnaisesti valittua lukua todistaisivat luvun n alkuvoimaa , niin todennäköisyys, että n on yhdistetty, ei ylitä . $4^{-k}$

Myös suurilla n :n arvoilla todennäköisyys julistaa yhdistelmäluku todennäköisesti alkuluvuksi on olennaisesti pienempi kuin 4 − k . Damgard, Landrock ja Pomerands [10] laskivat tarkkoja virherajoja ja ehdottivat menetelmää k:n arvon valitsemiseksi halutun virherajan saamiseksi. Tällaisia rajoja voidaan käyttää esimerkiksi todennäköisten alkulukujen muodostamiseen. Niitä ei kuitenkaan tule käyttää tuntemattoman alkuperän alkulukujen testaamiseen, koska salausjärjestelmissä krakkausyksikkö voi yrittää korvata pseudoalkuluvun, kun alkulukua vaaditaan. Tällaisissa tapauksissa voidaan luottaa vain virheeseen 4 − k .

Työn vaikeus

Olettaen, että kertolaskuaika on logaritminen, käyttämällä nopeaa modulo kertolaskua , algoritmin monimutkaisuus on , missä on kierrosten lukumäärä. Siten algoritmin ajoaika on polynomi. $O(k\log^3n)$ $k$

FFT : tä käyttämällä on kuitenkin mahdollista lyhentää algoritmin ajoaikaa . Tässä tapauksessa, jos otamme , jossa n on tarkistettava luku, niin algoritmin monimutkaisuus on yhtä suuri kuin . [yksitoista] $O(k\log ^{2}(n)\log(\log(n))\log(\log(\log(n))))={\widetilde {O))(k\log ^{2}(n))$ $k = \log_2(n)$ ${\widetilde {O}}(\log ^{3}n)$

Voimakkaasti pseudoalkumerkit

Jos luku a todistaa Millerin mukaan yhdistelmäparittoman luvun n yksinkertaisuuden , niin luvun n puolestaan sanotaan olevan vahvasti pseudo -alkuluku kannassa a . Jos luku n on vahvasti pseudoalkuluku kannassa a , niin se on myös Fermatin pseudoalkuluku emäksessä a ja Euler-Jacobin pseudoalkuluku emäksessä a . [3]

Esimerkiksi vahvasti pseudoalkuluvut emäksessä 2 muodostavat sekvenssin:

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, … ( OEIS - sekvenssi A001262 )

ja kannassa 3 järjestys:

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, … ( OEIS - sekvenssi A020229 )

Muistiinpanot

↑ Miller, 1975 .
↑ 12 Rabin , 1980 .
↑ 1 2 Menezes, Oorschot, Vanstone, 1996 , s. 141.
↑ Kormen, 2015 , s. 147.
↑ 1 2 Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Algoritmit: rakentaminen ja analyysi. - 3. - Moskova: Williams, 2013. - S. 1012-1015. — 1328 s. - ISBN 978-5-8459-1794-2 .
↑ Schoof, 2008 .
↑ Monier, 1980 .
↑ Arnault, 1995 .
↑ Baillie, Wagstaff, 1980 .
↑ Damgård, Landrock, Pomerance, 1993 .
↑ Bruce Schneier. Sovellettu kryptografia. - Moskova: Triumph, 2013. - S. 298. - 816 s.

Kirjallisuus

Miller G. Riemannin hypoteesi ja primaalisuuden testit // STOC '75 : Seitsemännen vuotuisen ACM-symposiumin julkaisut tietojenkäsittelyteoriasta - New York, NY, USA : ACM , 1975. - P. 234-239. doi : 10.1145/800116.803773
Rabin M. O. Probabilistinen algoritmi primaalisuuden testaamiseen // J. Number Theor. / D. Goss - Elsevier BV , 1980. - Voi. 12, Iss. 1. - s. 128-138. — ISSN 0022-314X ; 1096-1658 - doi:10.1016/0022-314X(80)90084-0
Baillie R. , Samuel S. Wagstaff, Jr. Lucas Pseudoprimes (englanniksi) // Math. Comp. - AMS , 1980. - Voi. 35, Iss. 152. - P. 1391-1417. — ISSN 0025-5718 ; 1088-6842 - doi:10.1090/S0025-5718-1980-0583518-6
Monier L. Kahden tehokkaan todennäköisyyspohjaisen primaalisuuden testausalgoritmin arviointi ja vertailu (englanniksi) // Theoretical Computer Science - Elsevier BV , 1980. - Voi. 12, Iss. 1. - s. 97-108. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/0304-3975(80)90007-9
Damgård I. , Landrock P. , Pomerance C. Keskimääräiset tapausvirhearviot vahvalle todennäköiselle alkutestille // Math . Comp. - AMS , 1993. - Voi. 61, Iss. 203. - s. 177-194. — ISSN 0025-5718 ; 1088-6842 - doi: 10.2307/2152945
Arnault F. Carmichael-lukujen rakentaminen, jotka ovat vahvoja pseudoalkulukuja useille emäksille // Journal of Symbolic Computation - Elsevier BV , 1995. - Voi. 20, Iss. 2. - s. 151-161. — ISSN 0747-7171 ; 1095-855X - doi:10.1006/JSCO.1995.1042
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Handbook of Applied Cryptography (englanti) - CRC Press , 1996. - 816 s. — ( Diskreetti matematiikka ja sen sovellukset ) — ISBN 978-0-8493-8523-0
Schoof R. Four Primality Testing Algorithms (englanti) // Algorithmic Number Theory : Lattices, Number Fields, Curves and Cryptography / J. P. Buhler , P. Stevenhagen - Cambridge : Cambridge University Press , 2008. - P. 69-81. - ( Mathematical Sciences Research Institute Publications ; Vol. 44) - ISBN 978-0-521-80854-5
Kormen T. H. Algoritmit : Alkukurssi / käännös. I. Krasikov - M. : Williams , 2015. - 208 s. — ISBN 978-5-8459-1868-0 , 978-5-8459-2073-7

Linkit

Yu. V. Nesterenko. Luku 4.4. Kuinka erottaa yhdistelmänumero yksinkertaisesta // Johdanto kryptografiaan / Toim. V. V. Jaštšenko. - Peter, 2001. - 288 s. - ISBN 5-318-00443-1 . Arkistoitu 25. helmikuuta 2008 Wayback Machinessa
Esimerkkejä algoritmin toteutuksesta monilla ohjelmointikielillä
S. B. Gashkov. Yksinkertaistettu perustelu todennäköisyyspohjaiselle Miller-Rabin-testille lukujen primaalisuuden testaamiseksi .
Weisstein, Eric W. Rabin-Miller Strong Pseudoprime Test (englanniksi) Wolfram MathWorld -verkkosivustolla .
"SPRP-tietueet"
Crandall, R. ja Pomerance, C. Todennäköiset alkuluvut ja todistajat // Alkuluvut. - Springer-Verlag, 2001. - ISBN 978-0387252827 .

Sanakirjat ja tietosanakirjat	Britannica (verkossa)

Lukuteoreettiset algoritmit
Yksinkertaisuustestit	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saksi Nightingale - Strassen
Alkulukujen löytäminen	Iterointi jakajien yli Eratosthenesin seula Atkinin seula Seula Sundarama
Faktorisointi	Iterointi jakajien yli Fermat menetelmä p −1 Pollardin menetelmä Pollardin ρ-algoritmi Lehmannin menetelmä Elliptisen käyrän menetelmä (Lenstran algoritmi) Dixonin algoritmi Neliömäinen seula
Diskreetti logaritmi	Gelfond-Shanks -algoritmi Polig-Hellman-algoritmi Pollardin ρ-menetelmä Pollardin kenguru-algoritmi Adlemanin algoritmi COS-algoritmi
GCD:n löytäminen	Eukleideen algoritmi Kehittynyt algoritmi Binäärinen algoritmi
Modulo-aritmetiikka	Montgomeryn algoritmi Kiinan jäännöslause
Lukujen kerto- ja jakolasku	Karatsuba-algoritmi Toom-Cook-algoritmi Schönhage-Strassen-algoritmi Fuhrer-algoritmi Harvey-van der Hoeven-algoritmi Burnickel-Ziegler-algoritmi
Neliöjuuren laskeminen	Tonelli-Shanks-algoritmi Berlekamp-Rabin-algoritmi