Test de primalitat de Miller-Rabin: diferència entre les revisions
Contingut suprimit Contingut afegit
m Robot: Reemplaçament automàtic de text (-[[ +, - +]]) |
Correccions a nivell ortogràfic, gramatical i tipogràfic. |
||
Línia 1:
El '''test de primalitat de Miller-Rabin''' o '''test de primalitat de Rabin-Miller''' és un [[test de primalitat]], és a dir un [[algorisme]] que determina si un nombre donat és un [[nombre primer probable]],
De forma similar al [[test de primalitat de Fermat]] i el [[test de primalitat de Solovay-Strassen]]. En la seva versió original, deguda a Gary L. Miller, era un [[algorisme determinista]], però el determinisme es basa en la [[hipòtesi generalitzada de Riemann]] que no està demostrada;<ref name="miller">Gary L. Miller, ''Riemann's Hypothesis and Tests for Primality'', Journal of Computer and System Sciences 13 (1976), no. 3, pp. 300–317.</ref> En [[Michael O. Rabin]] el va modificar per a obtenir un [[algorisme aleatori]].<ref name="rabin">Michael O. Rabin, ''Probabilistic algorithm for testing primality'', Journal of Number Theory 12 (1980), no. 1, pp. 128–138. {{doi-inline|10.1016/0022-314X(80)90084-0}}</ref>
Linha 6 ⟶ 5:
Igual que en els tests de Fermat i de Solovay-Strassen, el test de Miller-Rabin, es basa en una igualtat o conjunt d'igualtats que són certes per als nombres primers, llavors es mira si es compleixen o no per al nombre del qual es vol saber si és primer.
Per començar, un [[Lema (matemàtiques)|lema]] sobre les arrels quadrades de la unitat en el [[cos finit]] <math>\mathbb{Z}/p\mathbb{Z}</math>, on ''p'' és primer i <math>p > 2</math>. Certament, 1 i -1 donen sempre 1 en elevar-los al quadrat mòdul ''p''; d'aquestes se'n diu arrels quadrades ''trivials'' d'1. No hi ha arrels quadrades ''no trivials''
:<math>
x^{2} \equiv 1\pmod{p}
Linha 13 ⟶ 12:
\left (x - 1 \right ) \left ( x + 1 \right ) \equiv 0\pmod{p}
</math>
Com que ''x'' no és ni 1 ni -1 mòdul ''p'', tots dos <math>x-1</math> i <math>x+1</math> són co-primers amb <math>p</math>. Per tant, ni <math>x-1</math> ni <math>x+1</math> són divisibles per ''p''. Però això contradiu el [[lema d'Euclides]] que diu que si un nombre primer divideix un producte i no divideix un dels factors ha de dividir l'altre. Per tant no hi pot haver arrels quadrades no trivials
A continuació, sia ''n'' un nombre primer senar. Llavors es pot escriure ''n'' − 1 com <math>2^s \cdot d</math>, on ''s'' és un enter positiu i ''d'' és senar. Per a tot <math>a\in \left(\mathbb{Z}/n\mathbb{Z}\right)^*</math>, o bé
Linha 31 ⟶ 30:
Pel lema anterior, si es calcula repetidament l'arrel quadrada de ''a''<sup>''n'' − 1</sup>, s'obté o bé 1 o bé −1. Si en algún moment s'obté −1 llavors es compleix la segona igualtat i ja està.
En el cas que a
:<math>
a^{2^0 \cdot d} = a^d \not\equiv -1\pmod{n}
Linha 38 ⟶ 37:
Per tant en el cas que la segona igualtat no es compleixi, s'ha de complir la primera.
El test de primalitat de Miller-Rabin es basa en el la [[contraposada]] de
:<math>
a^{d} \not\equiv 1\pmod{n}
Linha 48 ⟶ 47:
llavors ''a'' és un testimoni que ''n'' és compost. Altrament ''n'' és [[probable nombre primer]] respecte a la base ''a''.
Per a cada nombre compost senar ''n'', hi ha molts testimonis ''a''. Però no es coneix cap camí senzill per a generar-los. Per això,
==Exemple==
Linha 84 ⟶ 83:
Fent servir la [[exponenciació modular]] per elevar al quadrat, el temps d'execució d'aquest algorisme és O(''k'' × log<sup>3</sup> ''n''), on ''k''
És el nombre de valors diferents de ''a'' que es proven; per tant aquest és un algorisme eficient de temps polinomis. Si la multiplicació es fa emprant la [[Transformada ràpida de Fourier]], es pot reduir el temps d'execució a O(''k'' × log<sup>2</sup> ''n'' log log ''n'' log log log ''n'') = Õ(''k''
× log<sup>2</sup> ''n'').
==Exactitud del test==
Com més bases ''a'' es proven, miller és l'exactitud del test. Es pot demostrar que per a qualsevol nombre senar compost ''n'', com a mínim 3/4 de les bases ''a'' són testimonis que ''n'' és compost.<ref name="rabin"/><ref name="schoof">René Schoof, ''Four primality testing algorithms'', to appear in: Surveys in algorithmic number theory, Cambridge University Press.[http://www.mat.uniroma2.it/~schoof/millerrabinpom.pdf PDF] ISBN 0521808545</ref> El test de Miller-Rabin és estrictament més fort que el [[test de primalitat de Solovay-Strassen]] en el sentit que per a cada compost ''n'', el conjunt de mentiders per a ''n'' és un subconjunt de conjunt de Euler mentiders de ''n'', i per a molts nombres ''n'', el subconjunt és propi. Si ''n'' és compost, llavors el test de primalitat de Miller-Rabin primality declara que ''n'' és un nombre primer probable amb una probabilitat com a màxim de <math>4^{-k}</math>. Per altra banda, el test de primalitat de Solovay-Strassen declara que ''n'' és un probable primer amb una probabilitat de com
La probabilitat mitjana que un nombre compost sigui declarat un probable primer és significativament més petita que <math>4^{-k}</math>. [[Ivan Damgård|Damgård]], Landrock i [[Pomerance]]<ref>I. Damgård, P. Landrock, and C. Pomerance (1993), ''Average case error estimates for the strong probable prime test'', Math. Comp. 61 (203) p. 177–194.</ref> calculen algunes fites explícites. Aquestes fites es poden fer servir per exemple per a ''generar'' nombres primers, però no s'han de fer servir per a ''verificar'' primes amb origen desconegut.
==Variants deterministes de la prova==
El test de Miller-Rabin es pot transformar en una prova a
Si el nombre a provar ''n'' és compost, els ''mentiders'' ''a'' coprimers amb ''n''
{{Algorisme|Test de primalitat de Miller-Rabin (Ordre de complexitat Õ((log ''n'')<sup>4</sup>))|
Linha 115 ⟶ 114:
Aquest algorisme no es fa servir a la pràctica perquè és molt més lent que el test de Miller-Rabin. Amb finalitats teòriques, ha estat superat per la [[prova de primalitat AKS]], que no descansa en suposicions no demostrades.
Quan el nombre ''n'' que es vol provar és petit, no cal provar tots els ''a'' < 2(ln ''n'')<sup>2</sup>,
*si ''n'' < 9,080,191, n'hi ha prou amb provar ''a'' = 31 i 73.
*si ''n'' < 4,759,123,141, n'hi ha prou amb provar ''a'' = 2, 7, i 61.
|