Miller-Rabin test

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 september 2020; kontroller kräver 7 redigeringar .

Miller-Rabin-testet är ett probabilistiskt polynom -primalitetstest . Miller-Rabin-testet, tillsammans med Fermat -testet och Solovay-Strassen-testet , kan effektivt avgöra om ett givet tal är sammansatt . Det kan dock inte användas för att noggrant bevisa att ett tal är primtal . Men Miller-Rabin-testet används ofta i kryptografi för att generera stora slumpmässiga primtal .

Historik

Miller-Rabin-algoritmen är en modifiering av Miller-algoritmen utvecklad av Gary Miller 1976 . Millers algoritm är deterministisk , men dess riktighet bygger på den obevisade utökade Riemann-hypotesen [1] . Michael Rabin modifierade den 1980 [2] . Miller-Rabin-algoritmen är inte beroende av hypotesens giltighet, utan är probabilistisk.

Applikation

Eftersom den kryptografiska styrkan hos många krypteringsalgoritmer är baserad på hemliga nycklar, som kräver primtal för att skapa (till exempel så här fungerar RSA- chifferet ), när man skapar sådana nycklar är det viktigt att snabbt kunna kontrollera stora tal för primalitet. Probabilistiska primalitetstester, såsom Miller-Rabin-testet och Solovay-Strassen-testet , visar större effektivitet i användningen och enklare uttryck jämfört med deterministiska tester [3] . Miller-Rabin-algoritmen låter dig utföra en kontroll på kort tid och samtidigt ge en ganska liten sannolikhet att siffran faktiskt är sammansatt. [fyra]

Hur algoritmen fungerar

Precis som Fermat- och Nightingale-Strassen- testerna bygger Miller-Rabin-testet på att kontrollera en serie likheter som gäller för primtal. Om åtminstone en sådan jämställdhet misslyckas, bevisar det att siffran är sammansatt [5] .

För Miller-Rabin-testet används följande påstående:

Låta vara ett primtal och , där är udda. Då är minst ett av följande villkor uppfyllt för något av följande: $n$ $n-1=2^{s}d$ $d$ $a$ $\mathbb {Z} _{n}$

$a^{d}\equiv 1{\pmod {n))$
Det finns ett heltal sådant $r<s$ $a^{2^{r}d}\equiv -1{\pmod {n))$

Bevis Lemma om kvadratrötter av enhet i ett ändligt fält :

\mathbb {Z} _{p}

I det sista fältet (för primtal ) finns inga kvadratrötter av enhet, förutom talen 1 , -1 $\mathbb {Z} _{p}$ $sid$

Bevis

Låta:

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

Sedan:

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

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

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

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

Enligt Fermats lilla teorem :

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

Vi kommer att extrahera kvadratrötterna av talet . Enligt lemmat som bevisats ovan kommer vi vid varje steg att få talet 1 eller -1 modulo . Om vi vid något steg får -1 så är den andra av likheterna uppfylld. Annars, vid det sista steget (eftersom ), d.v.s. den första jämställdheten kommer att uppfyllas. $a^{n-1}$ $n$ ${\sqrt[{{2}^{s}}]{a^{n-1}}}=a^{d}$ $n-1=2^{s}d$

Om detta påstående (villkor 1 eller 2) är uppfyllt för vissa siffror och (inte nödvändigtvis primtal), kallas talet för Millers primvittne och själva talet kallas troligt primtal . (Slumpmässigt finns det en 25 % chans att missförstå ett sammansatt tal för ett primtal, men detta kan minskas genom att kontrollera för andra .) $a$ $n$ $a$ $n$ $n$ $a$ $a$

I det fall då motsatsen till det bevisade påståendet är uppfyllt, det vill säga om det finns ett antal så att: $a$

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

och

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

då är talet inte primtal. I det här fallet kallas numret ett vittne om att numret är sammansatt. $n$ $a$ $n$

För udda sammansatta tal , enligt Rabins teorem , finns det inga fler vittnen om enkelhet, där är Euler-funktionen , så sannolikheten att ett slumpmässigt valt tal kommer att vara ett vittne om enkelhet är mindre än 1/4 [2] [6] . $n$ $\varphi (n)/4$ $\varphi (n)$ $a$

Tanken med testet är att kontrollera efter slumpmässigt utvalda nummer , om de är vittnen till numrets primahet . Om det finns bevis för att numret är sammansatt, så är numret verkligen sammansatt. Om siffrorna kontrollerades och alla visade sig vara primtal, anses talet vara primtal. För en sådan algoritm kommer sannolikheten att ta ett sammansatt tal för ett primtal vara mindre [7] . $a<n$ $n$ $k$ $(1/4)^{k}$

För att kontrollera stora siffror är det vanligt att välja slumpmässiga tal, eftersom fördelningen av primärvittnen och vittnen till ett sammansatt antal bland talen 1, 2, ..., n − 1 inte är känd i förväg. I synnerhet ger Arnolt [8] ett 397-bitars sammansatt nummer, för vilket alla tal mindre än 307 är bevis på enkelhet. $a$

Exempel

Antag att vi vill bestämma om n = 221 är primtal. Låt oss skriva n − 1 = 220 som 2 2 55, så s = 2 och d = 55. Vi väljer godtyckligt ett tal a så att 0 < a < n , låt oss säga a = 174. Låt oss gå vidare till beräkningarna:

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.

Eftersom 220 ≡ −1 mod n , är 221 antingen primtal, eller 174 är ett falskt vittne om att 221 är primtal. Ta en annan godtycklig a , denna gång genom att välja 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.

Eftersom 137 är ett vittne om att 221 är sammansatt, var siffran 174 faktiskt ett falskt vittne till enkelhet. Observera att algoritmen inte säger oss något om faktorerna 221 (som är 13 och 17). Men i vissa fall hjälper ytterligare beräkningar till att få fram faktorerna för antalet. [9]

Miller-Rabin algoritm

Implementering

Miller-Rabin-algoritmen parametriseras av antalet rundor r . Det rekommenderas att ta r i storleksordningen , där n är talet som ska testas. $\log_2(n)$

För ett givet n finns ett heltal s och ett udda heltal t så att . Ett slumpmässigt tal a väljs , 1 < a < n . Om a inte bevittnar primiteten av talet n , så ges svaret "n är sammansatt" och algoritmen slutar. Annars väljs ett nytt slumpmässigt nummer a och verifieringsproceduren upprepas. Efter att ha hittat r bevis på enkelhet ges svaret "n är förmodligen primtal" , och algoritmen avslutas [5] . $n-1 = 2^st$

Algoritmen kan skrivas i pseudokod enligt följande:

Indata : n > 2, ett udda naturligt tal som ska testas för primalitet; k är antalet omgångar. Output : composite , betyder att n är ett sammansatt tal; troligen primtal betyder att n med stor sannolikhet är primtal. Att representera n − 1 som 2 s · t , där t är udda, kan göras genom att successivt dividera n - 1 med 2. slinga A: upprepa k gånger: Välj ett slumpmässigt heltal a i intervallet [2, n − 2] x ← a t mod n , beräknat med exponentieringsalgoritmen modulo om x = 1 eller x = n − 1, gå sedan till nästa iteration av loop A loop B : upprepa s − 1 gånger x ← x 2 mod n om x = 1, returnera sedan sammansättningen om x = n − 1, gå sedan till nästa iteration av slingan A returnerar sammansättningen returnerar förmodligen primtal

Det följer av Rabins teorem att om k slumpmässigt valda tal var vittnen till numrets n primitet, så överstiger inte sannolikheten att n är sammansatt . $4^{-k}$

Dessutom, för stora värden på n är sannolikheten för att deklarera ett sammansatt tal troligen primtal väsentligt mindre än 4 − k . Damgard, Landrock och Pomerands [10] beräknade några exakta felgränser och föreslog en metod för att välja värdet på k för att erhålla den önskade felgränsen. Sådana gränser kan till exempel användas för att generera troliga primtal. De bör dock inte användas för att testa för primtal av okänt ursprung, eftersom en cracker i kryptografiska system kan försöka ersätta en pseudoprime när en prime krävs. I sådana fall kan man bara lita på felet 4 − k .

Svårighet att arbeta

Om man antar att multiplikationstiden är logaritmisk, med hjälp av snabb modulo multiplikation , är algoritmens komplexitet , där är antalet rundor. Sålunda är algoritmens gångtid polynom. $O(k\log^3n)$ $k$

Men med hjälp av FFT är det möjligt att minska algoritmens körtid till . I det här fallet, om vi tar , där n är talet som ska kontrolleras, då är komplexiteten hos algoritmen lika med . [elva] $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)$

Starkt pseudoprimer

Om talet a är ett vittne till enkelheten hos det sammansatta udda talet n enligt Miller, så sägs talet n i sin tur vara starkt pseudoprimtal i basen a . Om ett tal n är starkt pseudoprime i bas a , då är det också Fermat pseudoprime i bas a och Euler-Jacobi Pseudoprime i bas a . [3]

Till exempel, starkt pseudoprimer i bas 2 bildar sekvensen:

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

och i bas 3, sekvensen:

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

Anteckningar

↑ Miller, 1975 .
↑ 12 Rabin , 1980 .
↑ 1 2 Menezes, Oorschot, Vanstone, 1996 , s. 141.
↑ Kormen, 2015 , sid. 147.
↑ 1 2 Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Algoritmer: konstruktion och analys. - 3. - Moskva: Williams, 2013. - S. 1012-1015. — 1328 sid. - ISBN 978-5-8459-1794-2 .
↑ Schoof, 2008 .
↑ Monier, 1980 .
↑ Arnault, 1995 .
↑ Baillie, Wagstaff, 1980 .
↑ Damgård, Landrock, Pomerance, 1993 .
↑ Bruce Schneier. Tillämpad kryptografi. - Moskva: Triumf, 2013. - S. 298. - 816 sid.

Litteratur

Miller G. Riemann's Hypothesis and Tests for Primality // STOC '75 :of sjunde årliga ACM symposium on Theory of computing - New York, NY, USA : ACM , 1975. - P. 234-239. doi : 10.1145/800116.803773
Rabin M. O. Probabilistisk algoritm för att testa primalitet // J. Number Theor. / 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 (engelska) // 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. Utvärdering och jämförelse av två effektiva probabilistiska primalitetstestningsalgoritmer (engelska) // 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. Average Case Error Estimates for the 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. Konstruerar Carmichael-tal som är starka pseudoprimtal till flera 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 (engelska) - CRC Press , 1996. - 816 sid. — ( Diskret matematik och dess tillämpningar ) — ISBN 978-0-8493-8523-0
Schoof R. Four Primality Testing Algorithms (engelska) // 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 : Introduktionskurs / övers. I. Krasikov - M . : Williams , 2015. - 208 sid. — ISBN 978-5-8459-1868-0 , 978-5-8459-2073-7

Länkar

Yu. V. Nesterenko. Kapitel 4.4. Hur man skiljer ett sammansatt nummer från ett enkelt // Introduktion till kryptografi / Ed. V. V. Jasjtjenko. - Peter, 2001. - 288 sid. - ISBN 5-318-00443-1 . Arkiverad 25 februari 2008 på Wayback Machine
Exempel på implementering av algoritmen i många programmeringsspråk
S. B. Gashkov. Förenklad motivering för det probabilistiska Miller-Rabin-testet för att testa talens primaalitet .
Weisstein, Eric W. Rabin-Miller Strong Pseudoprime Test (engelska) på Wolfram MathWorlds webbplats .
"SPRP-poster"
Crandall, R. och Pomerance, C. Troliga primtal och vittnen // Primtal. - Springer-Verlag, 2001. - ISBN 978-0387252827 .

Ordböcker och uppslagsverk	Britannica (online)

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm