Test de primalitat de Miller-Rabin

De Viquipèdia
Dreceres ràpides: navegació, cerca

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;[1] En Michael O. Rabin el va modificar per a obtenir un algorisme aleatori.[2]

Conceptes[modifica | modifica el codi]

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 sobre les arrels quadrades de la unitat en el cos finit \mathbb{Z}/p\mathbb{Z}, on p és primer i p > 2. 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 1 mòdul p (un cas especial es dona 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 de 1 mòdul p. Llavors:


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

\left (x - 1 \right ) \left ( x + 1 \right ) \equiv 0\pmod{p}

Com que x no és ni 1 ni -1 mòdul p, tots dos x-1 i x+1 són co-primers amb p. Per tant, ni x-1 ni x+1 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 1 tal com es volia demostrar.

A continuació, sia n un nombre primer senar. Llavors es pot escriure n − 1 com 2^s \cdot d, on s és un enter positiu i d és senar. Per a tot a\in \left(\mathbb{Z}/n\mathbb{Z}\right)^*, o bé


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

O bé


a^{2^r\cdot d} \equiv -1\pmod{n} per algun 0 \le r \le s-1

Per veure que un dels dos cassos ha de ser cert, recordant el petit teorema de Fermat (que només s'aplica per a mòdul nombre primer):


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

Pel lema anterior, si es calcula repetidament l'arrel quadrada de an − 1, 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 base de calcular repetides arrels quadrades, s'hagin eliminat totes les potencies 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, dons 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ò significa que


a^{2^0 \cdot d} = a^d \not\equiv -1\pmod{n}

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 afirmació anterior. És a dir, si es pot trobar un a tal que


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

i


a^{2^rd} \not\equiv -1\pmod{n} for all 0 \le r \le s-1

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ò lo més eficient és aplicar la idea en un lgorisme que es limiti a detectar possibles nombres: es tria a \in \left(\mathbb{Z}/n\mathbb{Z}\right) aleatòriament, i es comprova si és o no un testimoni de què n és compost. Si n és compost, la majoria dels as 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[modifica | modifica el codi]

Suposeu que es vol determinar si n = 221 és primer. S'escriu n − 1 = 220 com a 22·55, de forma que es té s = 2 i d = 55. Aleatòriament es tria un a < n, per exemple 174. Es passa a fer els càlculs:

  • ad mod n = 17455 mod 221 = 47 ≠ 1
  • a20·d mod n = 17455 mod 221 = 47 ≠ n−1
  • a21·d mod n = 174110 mod 221 = 220 = n−1.

Com que 220 ≡ -1 mod n, o bé 221 és primer, o 174 és un mentider per a 221. Es tria un altre a aleatòriament, aquest cop es tria a=137:

  • ad mod n = 13755 mod 221 = 188 ≠ 1
  • a20·d mod n = 13755 mod 221 = 188 ≠ n−1
  • a21·d mod n = 137110 mod 221 = 205 ≠ n−1.

Ara 137 és un testimoni de què 221 és compost, i 174 era en efecte un mentider. Fixeu-vos que això no diu res dels factors de 221, que són 13 i 17.

Algorisme i temps d'execució[modifica | modifica el codi]

L'algorisme es pot escriure tal com segueix:

Algorisme Test de primalitat de Miller-Rabin (Ordre de complexitat \mathcal O(k \times \log^3 n))

Entrada: Un nombre natural n>1, el nombre k de cops que s'executa el test i que determina la seva fiabilitat.

Sortida: COMPOST si n és compost y POSSIBLE PRIMER si n és un nombre primer probable.

  1. Fer per a j\,\! des de 1\,\! fins k\,\! :
    1. a \gets Funció Genera_nombre_aleatori_en_interval(1,n-1]\,\!
    2. x \gets (a/n)
    3. Si a^d \not\equiv 1\ \bmod\ n i a^{{2^r}d}\not\equiv -1\ \bmod\ n per a tot r en l'interval [0,s - 1] llavors:
      1. Retorna COMPOST
  2. Retorna POSSIBLE PRIMER

Fent servir la exponenciació modular per elevar al quadrat, el temps d'execució d'aquest algorisme és O(k × log3 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 × log2 n log log n log log log n) = Õ(k × log2 n).

Exactitud del test[modifica | modifica el codi]

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.[2][3] 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 4^{-k}. Per altra banda, el test de primalitat de Solovay-Strassen declara que n és un probable primer amb una probabilitat de com amàxim 2^{-k}.

La probabilitat mitjana que un nombre compost sigui declarat un probable primer és significativament més petita que 4^{-k}. Damgård, Landrock i Pomerance[4] 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. Especialemtn en aplicacions 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 4^{-k}.

Variants deterministes de la prova[modifica | modifica el codi]

El test de Miller-Rabin es pot transformar en una prova a base 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 tan continguts en un subgrup propi del grup \left(\mathbb{Z}/n\mathbb{Z}\right)^*, això vol dir que si es proven tots els a procedents d'un conjunt el qual genera \left(\mathbb{Z}/n\mathbb{Z}\right)^*, 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 n)2), lo qual ja va ser indicat per Miller.[1] The constant involved in the Big O notation was reduced to 2 by Eric Bach.[5] Això porta al següent algorisme de prova de primalitat:

Algorisme Test de primalitat de Miller-Rabin (Ordre de complexitat Õ((log n)4))

Entrada: Un nombre natural senar n>1.

Sortida: COMPOST si n és compost y PRIMER si n és un nombre primer.

  1. escriure n − 1 com a 2^s \cdot d factoritzant en potències de 2 a partir de n − 1
  1. Fer per a tot a en l'interval [2,\min(n-1,\lfloor2(\ln n)^2\rfloor)] :
    1. Si ad mod n ≠ 1 i a^{d \cdot 2^r} mod n ≠ −1 per a tot r en l'interval [0, s − 1] llavors:
      1. Retorna COMPOST
  2. Retorna PRIMER

El temps d'execució de l'algorisme és Õ((log n)4). Per a garantir l'exactitud de la prova no cal tota la potència de la hipòtesi generalitzada de Riemann: com que s'està tractant amb subgrups d'índex parell, n'hi ha prou de suposar la validesa de la hipòtesi generalitzada de Riemann per a caràcter de Dirichlet quadràtics.[3]

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)2, dons se sap que n'hi ha prou amb conjunts molt petits de testimonis potencials. Per exemple, Jaeschke[6] 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.
  • si n < 2,152,302,898,747, n'hi ha prou amb provar a = 2, 3, 5, 7, i 11.
  • si n < 3,474,749,660,383, n'hi ha prou amb provar a = 2, 3, 5, 7, 11, i 13.
  • si n < 341,550,071,728,321, n'hi ha prou amb provar a = 2, 3, 5, 7, 11, 13, i 17.

(Només s'han de provar bases a < n.) Vegeu [2], [3] per a criteris d'aquesta mena. Aquests resultats donen proves de primalitat molt ràpides per a nombres de l'abast adequat, sense cap mena de suposicions.

Com que BPP està contingut en P/poly, hi ha una llista tan petita de potencials testimonis per a cada possible mida d'entrada (com a màxim n valors per a nombres de n bits). Ara bé, no hi ha cap base finita suficient per a tots els nombres compostos. Alford, Granville, i Pomerance[7] han demostrat que existeix una quantitat infinita de nombres compostos n tals que els seus testimonis més petits són com a mínim (\ln n)^{1/(3\ln\ln\ln n)}\;. També argumenten heurísticament que el nombre més petit w tal que cada nombre compost inferior a n té un testimoni de què és compost més petit que w ha de ser de l'ordre de \Theta(\log n\,\log\log n).

Referències[modifica | modifica el codi]

  1. 1,0 1,1 Gary L. Miller, Riemann's Hypothesis and Tests for Primality, Journal of Computer and System Sciences 13 (1976), no. 3, pp. 300–317.
  2. 2,0 2,1 Michael O. Rabin, Probabilistic algorithm for testing primality, Journal of Number Theory 12 (1980), no. 1, pp. 128–138. [1]
  3. 3,0 3,1 René Schoof, Four primality testing algorithms, to appear in: Surveys in algorithmic number theory, Cambridge University Press.PDF ISBN 0521808545
  4. 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.
  5. Eric Bach, Explicit bounds for primality testing and related problems, Mathematics of Computation 55 (1990), no. 191, pp. 355–380.
  6. Gerhard Jaeschke, On strong pseudoprimes to several bases, Mathematics of Computation 61 (1993), no. 204, pp. 915–926.
  7. W. R. Alford, A. Granville, and C. Pomerance, On the difficulty of finding reliable witnesses, in: Algorithmic Number Theory, First International Symposium, Proceedings (L. M. Adleman, M.-D. Huang, eds.), LNCS 877, Springer-Verlag, 1994, pp. 1–16.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 890–896 of section 31.8, Primality testing.

Enllaços externs[modifica | modifica el codi]