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:
{{millorar ortografia|data=febrer de 2014}}
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'' de d'1 mòdul <math>p</math> (un cas especial es dóna en el cos dels polinomis, on aquest resultat és equivalent a afirmar que el nombre d'arrels d'un polinomi no pot ser més gran que el seu grau). Per a demostrar-ho, se suposa que ''x'' és una arrel quadrada no trivial ded' 1 mòdul ''p''. Llavors:
:<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 de d'1 tal com es volia demostrar.
 
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 basecòpia de calcular repetides arrels quadrades, s'hagin eliminat totes les potenciespotències de 2 i la segona igualtat no s'hagi complert mai, encara queda la primera igualtat que també ha de ser igual a 1 o −1, donsdoncs també és una arrel quadrada. Ara bé, si la segona igualtat no es compleix mai, tampoc es pot haver complert per a ''r'' = 0, ixòaixò significa que
:<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 la l'afirmació anterior. És a dir, si es pot trobar un ''a'' tal que
:<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ò, loel més eficient és aplicar la idea en un lgorismealgorisme que es limiti a detectar possibles nombres: es tria <math>a \in \left(\mathbb{Z}/n\mathbb{Z}\right)</math> aleatòriament, i es comprova si és o no un testimoni de què ''n'' és compost. Si ''n'' és compost, la majoria dels ''a''s en seran testimonis, i el test tindrà una alta probabilitat de detectar ''n'' com a compost. Però sempre hi ha una petita possibilitat que si es té mala sort, es triï un ''a'' que és un ''mentider'' per a ''n''. Aquesta probabilitat d'error es pot reduir a força de repetir la prova amb diverses ''a'' triades de forma aleatòria i independent.
 
==Exemple==
Linha 84 ⟶ 83:
 
Fent servir la [[exponenciació modular]] per elevar al quadrat, el temps d'execució d'aquest algorisme és O(''k'' &times; log<sup>3</sup>&nbsp;''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'' &times; log<sup>2</sup>&nbsp;''n'' log log ''n'' log log log ''n'') = Õ(''k''
&times; log<sup>2</sup>&nbsp;''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 amàxima màxim <math>2^{-k}</math>.
 
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. EspecialemtnEspecialment en aplicacions [[criptografia|criptogràfiques]] un adversari podria provar d'enviar un pseudoprimer en comptes d'un nombre en un lloc on es requereix un nombre primer. Llavors, amb l'estat actual de coneixements, només es pot confiar en la fita de <math>4^{-k}</math>.
 
==Variants deterministes de la prova==
El test de Miller-Rabin es pot transformar en una prova a basecòpia de provar tots els valors possibles de ''a'' per davall de cert límit. El problema en general és establir aquest límit de forma que l'algorisme encara sigui eficient.
 
Si el nombre a provar ''n'' és compost, els ''mentiders'' ''a'' coprimers amb ''n'' es tanestan continguts en un [[subgrup]] propi del grup <math>\left(\mathbb{Z}/n\mathbb{Z}\right)^*</math>, això vol dir que si es proven tots els ''a'' procedents d'un conjunt el qual [[conjunt generador d'un grup|genera]] <math>\left(\mathbb{Z}/n\mathbb{Z}\right)^*</math>, un d'ells ha de ser un testimoni de què ''n'' és compost. Suposant que és certa la [[hipòtesi generalitzada de Riemann]] (GRH), se sap que el grup és generat pels seus elements més petits que O((log&nbsp;''n'')<sup>2</sup>), lofet qualque ja va ser indicat per Miller.<ref name="miller"/> The constant involved in the [[Big O notation]] was reduced to 2 by [[Eric Bach]].<ref>Eric Bach, ''Explicit bounds for primality testing and related problems'', Mathematics of Computation 55 (1990), no. 191, pp. 355–380.</ref> Això porta al següent algorisme de prova de primalitat:
 
{{Algorisme|Test de primalitat de Miller-Rabin (Ordre de complexitat Õ((log&nbsp;''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&nbsp;''n'')<sup>2</sup>, donsdoncs se sap que n'hi ha prou amb conjunts molt petits de testimonis potencials. Per exemple, Jaeschke<ref>Gerhard Jaeschke, ''On strong pseudoprimes to several bases'', Mathematics of Computation 61 (1993), no. 204, pp. 915–926.</ref> ha verificat que
*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.