Miller-Rabin test

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 24. september 2020; checks kræver 7 redigeringer .

Miller-Rabin-testen er en probabilistisk polynomiel primalitetstest . Miller-Rabin-testen kan sammen med Fermat -testen og Solovay-Strassen-testen effektivt afgøre, om et givet tal er sammensat . Det kan dog ikke bruges til strengt at bevise , at et tal er primtal . Miller-Rabin-testen bruges dog ofte i kryptografi til at generere store tilfældige primtal .

Historie

Miller-Rabin-algoritmen er en modifikation af Miller-algoritmen udviklet af Gary Miller i 1976 . Millers algoritme er deterministisk , men dens korrekthed er afhængig af den ubeviste udvidede Riemann-hypotese [1] . Michael Rabin modificerede det i 1980 [2] . Miller-Rabin-algoritmen afhænger ikke af hypotesens gyldighed, men er sandsynlig.

Ansøgning

Da den kryptografiske styrke af mange krypteringsalgoritmer er baseret på hemmelige nøgler, som kræver primtal for at skabe (f.eks. er det sådan RSA -krypteringen fungerer ), når man opretter sådanne nøgler, er det vigtigt hurtigt at kunne tjekke store tal for primalitet. Probabilistiske primalitetstests, såsom Miller-Rabin-testen og Solovay-Strassen-testen , viser større effektivitet i brugen og nem udtryk sammenlignet med deterministiske tests [3] . Miller-Rabin-algoritmen giver dig mulighed for at udføre et tjek på kort tid og samtidig give en ret lille sandsynlighed for, at tallet faktisk er sammensat. [fire]

Sådan fungerer algoritmen

Ligesom Fermat- og Nightingale-Strassen- testene er Miller-Rabin-testen afhængig af at kontrollere en række ligheder, der gælder for primtal. Hvis mindst en sådan lighed fejler, beviser det, at tallet er sammensat [5] .

Til Miller-Rabin-testen bruges følgende udsagn:

Lade være et primtal og , hvor er ulige. Derefter er mindst én af følgende betingelser opfyldt : $n$ $n-1=2^{s}d$ $d$ $-en$ $\mathbb {Z} _{n}$

$a^{d}\equiv 1{\pmod {n))$
Der er et heltal sådan $r<s$ $a^{2^{r}d}\equiv -1{\pmod {n))$

Bevis Lemma om kvadratrødder af enhed i et begrænset felt :

\mathbb {Z} _{p}

I det sidste felt (for primtal ) er der ingen kvadratrødder af enhed, bortset fra tallene 1 , -1 $\mathbb {Z} _{p}$ $s$

Bevis

Lade:

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

Derefter:

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

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

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

Efter Euklids lemma :

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

Ved Fermats lille sætning :

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

Vi vil udtrække kvadratrødderne af tallet . Ifølge lemmaet, der er bevist ovenfor, vil vi ved hvert trin få tallet 1 eller -1 modulo . Hvis vi på et eller andet trin får -1 , så er den anden af lighederne opfyldt. Ellers vil den første ligestilling være opfyldt på det sidste trin (fordi ), dvs. $a^{n-1}$ $n$ ${\sqrt[{{2}^{s}}]{a^{n-1}}}=a^{d}$ $n-1=2^{s}d$

Hvis denne erklæring (betingelse 1 eller 2) er opfyldt for nogle tal og (ikke nødvendigvis primtal), så kaldes tallet Millers prime vidne , og selve tallet kaldes sandsynligt primtal . (Tilfældigt er der 25 % chance for at forveksle et sammensat tal for et primtal, men dette kan reduceres ved at kontrollere for andre .) $-en$ $n$ $-en$ $n$ $n$ $-en$ $-en$

I det tilfælde, hvor modsætningen af den beviste erklæring er opfyldt, det vil sige, hvis der er et tal , således at: $-en$

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

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

så er tallet ikke primtal. I dette tilfælde kaldes nummeret et vidne om, at nummeret er sammensat. $n$ $-en$ $n$

For ulige sammensatte tal er der ifølge Rabins sætning ikke flere vidner om enkelhed, hvor er Euler-funktionen , så sandsynligheden for at et tilfældigt valgt tal vil være et vidne om enkelhed er mindre end 1/4 [2] [6] . $n$ $\varphi (n)/4$ $\varphi (n)$ $-en$

Ideen med testen er at tjekke for tilfældigt udvalgte tal , om de er vidner til tallets primeness . Hvis der er bevis for, at tallet er sammensat, så er tallet faktisk sammensat. Hvis tallene blev kontrolleret, og alle viste sig at være primtal, betragtes tallet som primtal. For en sådan algoritme vil sandsynligheden for at tage et sammensat tal for et primtal være mindre [7] . $a<n$ $n$ $k$ $(1/4)^{k}$

For at kontrollere store tal er det sædvanligt at vælge tilfældige tal, da fordelingen af vidner om primalitet og vidner om et sammensat tal blandt tallene 1, 2, ..., n − 1 ikke er kendt på forhånd. Især giver Arnolt [8] et 397-bit sammensat tal, for hvilket alle tal mindre end 307 er bevis på enkelhed. $-en$

Eksempel

Antag, at vi ønsker at bestemme, om n = 221 er primtal. Lad os skrive n − 1 = 220 som 2 2 55, så s = 2 og d = 55. Vi vælger vilkårligt et tal a , således at 0 < a < n , lad os sige a = 174. Lad os gå videre til beregningerne:

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.

Da 220 ≡ −1 mod n , er 221 enten primtal, eller 174 er et falsk vidne om, at 221 er primtal. Tag en anden vilkårlig a , denne gang ved at vælge 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.

Da 137 er et vidne om, at 221 er sammensat, var tallet 174 faktisk et falsk vidne om enkelhed. Bemærk, at algoritmen ikke fortæller os noget om faktorerne 221 (som er 13 og 17). Men i nogle tilfælde hjælper yderligere beregninger med at få talets faktorer. [9]

Miller-Rabin algoritme

Implementering

Miller-Rabin-algoritmen parametreres af antallet af runder r . Det anbefales at tage r af størrelsesordenen , hvor n er det tal, der skal testes. $\log_2(n)$

For et givet n er der et heltal s og et ulige heltal t , således at . Der vælges et tilfældigt tal a , 1 < a < n . Hvis a ikke er vidne til primiteten af tallet n , så er svaret "n er sammensat" givet , og algoritmen slutter. Ellers vælges et nyt tilfældigt tal a , og verifikationsproceduren gentages. Efter at have fundet r bevis på enkelhed, gives svaret "n er sandsynligvis prime" , og algoritmen afsluttes [5] . $n-1 = 2^st$

Algoritmen kan skrives i pseudokode som følger:

Input : n > 2, et ulige naturligt tal, der skal testes for primalitet; k er antallet af runder. Output : composite , betyder at n er et sammensat tal; sandsynligvis prime betyder, at n med stor sandsynlighed er prime. At repræsentere n − 1 som 2 s · t , hvor t er ulige, kan gøres ved successivt at dividere n - 1 med 2. sløjfe A: gentag k gange: Vælg et tilfældigt heltal a i intervallet [2, n − 2] x ← a t mod n , beregnet ved hjælp af eksponentieringsalgoritmen modulo hvis x = 1 eller x = n − 1, og gå derefter til næste iteration af sløjfe A sløjfe B : gentag s − 1 gange x ← x 2 mod n hvis x = 1, returner derefter forbindelsen hvis x = n − 1, og gå derefter til næste iteration af sløjfen A returnerer den sammensatte returnering sandsynligvis prime

Det følger af Rabins sætning, at hvis k tilfældigt udvalgte tal var vidner til primiteten af tallet n , så overstiger sandsynligheden for, at n er sammensat ikke . $4^{-k}$

For store værdier af n er sandsynligheden for at erklære et sammensat tal sandsynligvis primtal væsentligt mindre end 4 − k . Damgard, Landrock og Pomerands [10] beregnede nogle præcise fejlgrænser og foreslog en metode til at vælge værdien af k for at opnå den ønskede fejlgrænse. Sådanne grænser kan for eksempel bruges til at generere sandsynlige primtal. De bør dog ikke bruges til at teste for primtal af ukendt oprindelse, da en cracker i kryptografiske systemer kan forsøge at erstatte en pseudoprime, når en prime er påkrævet. I sådanne tilfælde kan man kun stole på fejlen 4 − k .

Svært arbejde

Forudsat at multiplikationstiden er logaritmisk, ved hjælp af hurtig modulo multiplikation , er kompleksiteten af algoritmen , hvor er antallet af runder. Algoritmens køretid er således polynomiel. $O(k\log^3n)$ $k$

Ved at bruge FFT er det dog muligt at reducere algoritmens køretid til . I dette tilfælde, hvis vi tager , hvor n er det tal, der skal kontrolleres, så er kompleksiteten af algoritmen lig med . [elleve] $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)$

Stærkt pseudoprimer

Hvis tallet a er et vidnesbyrd om enkeltheden af det sammensatte ulige tal n ifølge Miller, så siges tallet n til gengæld at være stærkt pseudo -primtal i basis a . Hvis et tal n er stærkt pseudoprime i base a , så er det også Fermat pseudoprime i base a og Euler-Jacobi Pseudoprime i base a . [3]

For eksempel danner stærkt pseudoprimer i base 2 sekvensen:

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

og i base 3, sekvensen:

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

Noter

↑ 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. Algoritmer: konstruktion og analyse. - 3. - Moskva: 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. Anvendt kryptografi. - Moskva: Triumf, 2013. - S. 298. - 816 s.

Litteratur

Miller G. Riemann's Hypothesis and Tests for Primality // STOC '75 :of syvende årlige ACM symposium on Theory of computing - New York, NY, USA : ACM , 1975. - S. 234-239. doi : 10.1145/800116.803773
Rabin M. O. Probabilistisk algoritme til test af primalitet // J. Talteor. / D. Goss - Elsevier BV , 1980. - Vol. 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 (engelsk) // Math. Comp. - AMS , 1980. - Vol. 35, Iss. 152. - P. 1391-1417. — ISSN 0025-5718 ; 1088-6842 - doi:10.1090/S0025-5718-1980-0583518-6
Monier L. Evaluering og sammenligning af to effektive probabilistiske primalitetstestalgoritmer (engelsk) // Theoretical Computer Science - Elsevier BV , 1980. - Vol. 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. Gennemsnitlige kasusfejlestimater for Strong Probable Prime Test // Math . Comp. - AMS , 1993. - Vol. 61, Iss. 203. - S. 177-194. — ISSN 0025-5718 ; 1088-6842 - doi:10.2307/2152945
Arnault F. Konstruerer Carmichael-tal, som er stærke pseudoprimtal til flere baser // Journal of Symbolic Computation - Elsevier BV , 1995. - Vol. 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 (engelsk) - CRC Press , 1996. - 816 s. — ( Diskret matematik og dens anvendelser ) — ISBN 978-0-8493-8523-0
Schoof R. Four Primality Testing Algorithms (engelsk) // Algorithmic Number Theory : Lattices, Number Fields, Curves and Cryptography / J. P. Buhler , P. Stevenhagen - Cambridge : Cambridge University Press , 2008. - S. 69-81. - ( Mathematical Sciences Research Institute Publications ; Vol. 44) - ISBN 978-0-521-80854-5
Kormen T. H. Algoritmer : Introduktionskursus / overs. I. Krasikov - M . : Williams , 2015. - 208 s. — ISBN 978-5-8459-1868-0 , 978-5-8459-2073-7

Links

Yu. V. Nesterenko. Kapitel 4.4. Sådan skelnes et sammensat tal fra et simpelt // Introduktion til kryptografi / Red. V. V. Yashchenko. - Peter, 2001. - 288 s. - ISBN 5-318-00443-1 . Arkiveret 25. februar 2008 på Wayback Machine
Eksempler på implementering af algoritmen i mange programmeringssprog
S. B. Gashkov. Forenklet begrundelse for den probabilistiske Miller-Rabin-test til at teste tallenes primalitet .
Weisstein, Eric W. Rabin-Miller Strong Pseudoprime Test (engelsk) på Wolfram MathWorld -webstedet .
"SPRP records"
Crandall, R. og Pomerance, C. Sandsynlige primtal og vidner // Primtal. - Springer-Verlag, 2001. - ISBN 978-0387252827 .

Ordbøger og encyklopædier	Britannica (online)

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme