Testul Miller-Rabin

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 24 septembrie 2020; verificările necesită 7 modificări .

Testul Miller-Rabin este un test de primalitate polinomială probabilistică . Testul Miller-Rabin, împreună cu testul Fermat și testul Solovay-Strassen , pot determina în mod eficient dacă un anumit număr este compus . Cu toate acestea, nu poate fi folosit pentru a demonstra riguros că un număr este prim . Cu toate acestea, testul Miller-Rabin este adesea folosit în criptografie pentru a genera numere prime aleatorii mari .

Istorie

Algoritmul Miller-Rabin este o modificare a algoritmului Miller dezvoltat de Gary Miller în 1976 . Algoritmul lui Miller este determinist , dar corectitudinea lui se bazează pe ipoteza Riemann extinsă nedovedită [1] . Michael Rabin l-a modificat în 1980 [2] . Algoritmul Miller-Rabin nu depinde de validitatea ipotezei, ci este probabilist.

Aplicație

Deoarece puterea criptografică a multor algoritmi de criptare se bazează pe chei secrete, care necesită numere prime pentru a fi create (de exemplu, așa funcționează cifrul RSA ), atunci când creați astfel de chei, este important să puteți verifica rapid numerele mari pentru primalitate. Testele de primalitate probabilistică, cum ar fi testul Miller-Rabin și testul Solovay-Strassen , arată o eficiență mai mare de utilizare și ușurință de exprimare în comparație cu testele deterministe [3] . Algoritmul Miller-Rabin vă permite să efectuați o verificare într-un timp scurt și, în același timp, să oferiți o probabilitate destul de mică ca numărul să fie de fapt compus. [patru]

Cum funcționează algoritmul

La fel ca testele Fermat și Nightingale-Strassen , testul Miller-Rabin se bazează pe verificarea unei serii de egalități care sunt valabile pentru numerele prime. Dacă cel puțin o astfel de egalitate eșuează, se demonstrează că numărul este compus [5] .

Pentru testul Miller-Rabin, se utilizează următoarea afirmație:

Fie un număr prim și , unde este impar. Atunci pentru oricare dintre cel puțin una dintre următoarele condiții este îndeplinită: $n$ $n-1=2^{s}d$ $d$ $A$ $\mathbb {Z} _{n}$

$a^{d}\equiv 1{\pmod {n)}$
Există un număr întreg astfel încât $r<s$ $a^{2^{r}d}\equiv -1{\pmod {n)}$

Dovada Lema despre rădăcinile pătrate ale unității într-un câmp finit :

\mathbb {Z} _{p}

În câmpul final (pentru prim ) nu există rădăcini pătrate ale unității, cu excepția numerelor 1 , -1 $\mathbb {Z} _{p}$ $p$

Dovada

Lăsa:

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

Apoi:

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

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

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

După lema lui Euclid :

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

După mica teoremă a lui Fermat :

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

Vom extrage rădăcinile pătrate ale numărului . Conform lemei demonstrate mai sus, la fiecare pas vom obține numărul 1 sau -1 modulo . Dacă la un pas obținem -1 , atunci a doua dintre egalități este îndeplinită. În caz contrar, la ultimul pas (pentru că ), adică prima egalitate va fi îndeplinită. $a^{n-1}$ $n$ ${\sqrt[{{2}^{s}}]{a^{n-1}}}=a^{d}$ $n-1=2^{s}d$

Dacă această afirmație (condiția 1 sau 2) este îndeplinită pentru unele numere și (nu neapărat prime), atunci numărul se numește martorul prim al lui Miller , iar numărul însuși se numește prim probabil . (La întâmplare , există o șansă de 25% de a confunda un număr compus cu un prim, dar acest lucru poate fi redus prin verificarea altor .) $A$ $n$ $A$ $n$ $n$ $A$ $A$

În cazul în care este satisfăcută contrapoziția afirmației dovedite, adică dacă există un număr astfel încât: $A$

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

și

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

atunci numărul nu este prim. În acest caz, numărul este numit un martor că numărul este compus. $n$ $A$ $n$

Pentru numerele compuse impare , conform teoremei lui Rabin , nu mai există martori ai simplității, unde este funcția Euler , deci probabilitatea ca un număr ales aleatoriu să fie martor al simplității este mai mică de 1/4 [2] [6] . $n$ $\varphi (n)/4$ $\varphi (n)$ $A$

Ideea testului este de a verifica numerele selectate aleatoriu , dacă acestea sunt martori ai primului numărului . Dacă există dovezi că numărul este compus, atunci numărul este într-adevăr compus. Dacă numerele au fost verificate și toate s-au dovedit a fi prime, atunci numărul este considerat prim. Pentru un astfel de algoritm, probabilitatea de a lua un număr compus pentru un număr prim va fi mai mică [7] . $a<n$ $n$ $k$ $(1/4)^{k}$

Pentru a verifica numerele mari, se obișnuiește să se aleagă numere aleatoare, deoarece distribuția martorilor de primalitate și a martorilor unui număr compus între numerele 1, 2, ..., n − 1 nu este cunoscută dinainte. În special, Arnolt [8] oferă un număr compus de 397 de biți, pentru care toate numerele mai mici de 307 sunt dovezi ale simplității. $A$

Exemplu

Să presupunem că vrem să determinăm dacă n = 221 este prim. Să scriem n − 1 = 220 ca 2 2 55, deci s = 2 și d = 55. Alegem în mod arbitrar un număr a astfel încât 0 < a < n , să spunem a = 174. Să trecem la calcule:

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.

Deoarece 220 ≡ −1 mod n , 221 este fie prim, fie 174 este un martor fals că 221 este prim. Luați un alt a arbitrar , de data aceasta alegând 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.

Deoarece 137 este un martor că 221 este compus, numărul 174 a fost de fapt un martor fals al simplității. Rețineți că algoritmul nu ne spune nimic despre factorii lui 221 (care sunt 13 și 17). Cu toate acestea, în unele cazuri, calculele suplimentare ajută la obținerea factorilor numărului. [9]

Algoritmul Miller-Rabin

Implementare

Algoritmul Miller-Rabin este parametrizat de numărul de runde r . Se recomandă să luăm r de ordinul mărimii , unde n este numărul de verificat. $\log_2(n)$

Pentru un n dat , există un număr întreg s și un număr întreg impar t astfel încât . Se alege un număr aleatoriu a , 1 < a < n . Dacă a nu este martor la primă a numărului n , atunci răspunsul „n este compus” este dat , iar algoritmul se termină. În caz contrar, se selectează un nou număr aleator a și se repetă procedura de verificare. După găsirea r dovezi de simplitate, se dă răspunsul „n este probabil prim” , iar algoritmul se termină [5] . $n-1 = 2^st$

Algoritmul poate fi scris în pseudocod după cum urmează:

Intrare : n > 2, un număr natural impar de testat pentru primalitate; k este numărul de runde. Ieșire : compus , înseamnă că n este un număr compus; probabil prim înseamnă că n este foarte probabil să fie prim. Reprezentarea n − 1 ca 2 s · t , unde t este impar, se poate face împărțind succesiv n - 1 la 2. bucla A: repetați de k ori: Alegeți un număr întreg aleatoriu a în intervalul [2, n − 2] x ← a t mod n , calculat folosind algoritmul de exponențiere modulo dacă x = 1 sau x = n − 1, apoi treceți la următoarea iterație a buclei A buclei B : repetă s − 1 ori x ← x 2 mod n dacă x = 1, apoi returnează compusul dacă x = n − 1, apoi mergi la următoarea iterație a buclei A returnează compusul returnează probabil prim

Din teorema lui Rabin rezultă că, dacă k numere alese aleatoriu au fost martori ale primului numărului n , atunci probabilitatea ca n să fie compus nu depășește . $4^{-k}$

De asemenea, pentru valori mari ale lui n , probabilitatea de a declara un număr compus probabil prim este substanțial mai mică decât 4 - k . Damgard, Landrock și Pomerands [10] au calculat niște limite precise de eroare și au propus o metodă de alegere a valorii lui k pentru a obține limita de eroare dorită. Astfel de limite pot fi utilizate, de exemplu, pentru a genera numere prime probabile. Cu toate acestea, ele nu ar trebui utilizate pentru a testa numerele prime de origine necunoscută, deoarece în sistemele criptografice un cracker poate încerca să înlocuiască un pseudoprim atunci când este necesar un prim. În astfel de cazuri, se poate baza doar pe eroarea 4 − k .

Dificultatea muncii

Presupunând că timpul de înmulțire este logaritmic, utilizând înmulțirea rapidă modulo , complexitatea algoritmului este , unde este numărul de runde. Astfel, timpul de rulare al algoritmului este polinom. $O(k\log^3n)$ $k$

Cu toate acestea, folosind FFT , este posibil să se reducă timpul de rulare al algoritmului la . În acest caz, dacă luăm , unde n este numărul de verificat, atunci complexitatea algoritmului este egală cu . [unsprezece] $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)$

Puternic pseudoprime

Dacă numărul a este un martor al simplității numărului impar compus n conform lui Miller, atunci numărul n , la rândul său, se spune că este puternic pseudo -prim în baza a . Dacă un număr n este puternic pseudoprim în baza a , atunci este și pseudoprim Fermat în baza a și Euler-Jacobi pseudoprim în baza a . [3]

De exemplu, pseudoprimele puternice în baza 2 formează secvența:

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, … ( secvența OEIS A001262 )

iar în baza 3, secvența:

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, … ( secvența OEIS A020229 )

Note

↑ Miller, 1975 .
↑ 12 Rabin , 1980 .
↑ 1 2 Menezes, Oorschot, Vanstone, 1996 , pp. 141.
↑ Kormen, 2015 , p. 147.
↑ 1 2 Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Algoritmi: construcție și analiză. - 3. - Moscova: Williams, 2013. - S. 1012-1015. — 1328 p. - ISBN 978-5-8459-1794-2 .
↑ Schoof, 2008 .
↑ Monier, 1980 .
↑ Arnault, 1995 .
↑ Baillie, Wagstaff, 1980 .
↑ Damgård, Landrock, Pomerance, 1993 .
↑ Bruce Schneier. Criptografie aplicată. - Moscova: Triumful, 2013. - S. 298. - 816 p.

Literatură

Miller G. Riemann's Hypothesis and Tests for Primality // STOC '75 :of seventh annual ACM symposium on Theory of computing - New York, NY, USA : ACM , 1975. - P. 234-239. doi : 10.1145/800116.803773
Rabin M. O. Algoritm probabilistic pentru testarea primalităţii // J. Number Theor. / D. Goss - Elsevier BV , 1980. - Vol. 12, Iss. 1. - P. 128-138. — ISSN 0022-314X ; 1096-1658 - doi:10.1016/0022-314X(80)90084-0
Baillie R. , Samuel S. Wagstaff, Jr. Lucas Pseudoprime (engleză) // Matematică. 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. Evaluarea și compararea a doi algoritmi de testare probabilistică eficientă a primalității (engleză) // Informatică teoretică - Elsevier BV , 1980. - Vol. 12, Iss. 1. - P. 97-108. — ISSN 0304-3975 ; 1879-2294 - doi:10.1016/0304-3975(80)90007-9
Damgård I. , Landrock P. , Pomerance C. Estimări ale erorilor medii de caz pentru testul Strong Probable Prime // Math . Comp. - AMS , 1993. - Vol. 61, Iss. 203. - P. 177-194. — ISSN 0025-5718 ; 1088-6842 - doi:10.2307/2152945
Arnault F. Construirea numerelor Carmichael care sunt pseudoprime puternice la mai multe baze // Journal of Symbolic Computation - Elsevier BV , 1995. - Vol. 20, Iss. 2. - P. 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 (engleză) - CRC Press , 1996. - 816 p. — ( Matematică discretă și aplicațiile sale ) — ISBN 978-0-8493-8523-0
Schoof R. Four Primality Testing Algorithms (engleză) // Teoria algoritmică a numerelor : Lattices, Number Fields, Curves and Cryptography / J. P. Buhler , P. Stevenhagen - Cambridge : Cambridge University Press , 2008. - P. 69-81. - ( Publicații Institutului de Cercetare în Științe Matematice ; Vol. 44) - ISBN 978-0-521-80854-5
Kormen T. H. Algoritmi : Curs introductiv / transl. I. Krasikov - M . : Williams , 2015. - 208 p. — ISBN 978-5-8459-1868-0 , 978-5-8459-2073-7

Link -uri

Iu V. Nesterenko. Capitolul 4.4. Cum să distingem un număr compus de unul simplu // Introducere în criptografie / Ed. V. V. Iascenko. - Petru, 2001. - 288 p. - ISBN 5-318-00443-1 . Arhivat pe 25 februarie 2008 la Wayback Machine
Exemple de implementare a algoritmului în multe limbaje de programare
S. B. Gashkov. Rațiune simplificată pentru testul probabilistic Miller-Rabin pentru testarea primarității numerelor .
Weisstein, Eric W. Rabin-Miller Strong Pseudoprime Test (engleză) pe site-ul Wolfram MathWorld .
„Înregistrări SPRP”
Crandall, R. și Pomerance, C. Prime probabile și martori // Numere prime. - Springer-Verlag, 2001. - ISBN 978-0387252827 .

Dicționare și enciclopedii	Britannica (online)

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin