Test de primalitat de Miller-Rabin

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

Conceptes

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 d'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 d' 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 d'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\leq r\leq s-1$

Per veure que un dels dos casos 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 a^{n − 1}, s'obté o bé 1 o bé −1. Si en algun moment s'obté −1 llavors es compleix la segona igualtat i ja està.

En el cas que a còpia de calcular repetides arrels quadrades, s'hagin eliminat totes les potè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, perquè també és una arrel quadrada. Ara bé, si la segona igualtat no es compleix mai, tampoc es pot haver complert per a r = 0, això 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 la contraposada de l'afirmació anterior. És a dir, si es pot trobar un a tal que

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

i

$a^{2^{r}d}\not \equiv -1{\pmod {n}}$ for all $0\leq r\leq 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ò, el més eficient és aplicar la idea en un algorisme 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

Suposeu que es vol determinar si n = 221 és primer. S'escriu n − 1 = 220 com a 2²·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:

• a^d mod n = 174⁵⁵ mod 221 = 47 ≠ 1
• a^20·d mod n = 174⁵⁵ mod 221 = 47 ≠ n−1
• a^2¹·d mod n = 174¹¹⁰ 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:

• a^d mod n = 137⁵⁵ mod 221 = 188 ≠ 1
• a^20·d mod n = 137⁵⁵ mod 221 = 188 ≠ n−1
• a^2¹·d mod n = 137¹¹⁰ 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ó

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. Fer per a $j\,\!$ des de $1\,\!$ fins $k\,\!$ : $a\gets$ Funció Genera_nombre_aleatori_en_interval$(1,n-1]\,\!$ $x\gets$ (a/n) 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: Retorna COMPOST Retorna POSSIBLE PRIMER

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

Exactitud del test

Com més bases a es proven, millor é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. 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 a mà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 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. Especialment 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

El test de Miller-Rabin es pot transformar en una prova a cò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 estan 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)²), fet que ja va ser indicat per Miller. The constant involved in the Big O notation was reduced to 2 by Eric Bach. 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. escriure n − 1 com a $2^{s}\cdot d$ factoritzant en potències de 2 a partir de n − 1 Fer per a tot a en l'interval $[2,\min(n-1,\lfloor 2(\ln n)^{2}\rfloor )]$ : 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: Retorna COMPOST Retorna PRIMER

El temps d'execució de l'algorisme és Õ((log n)⁴). 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.

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)², doncs se sap que n'hi ha prou amb conjunts molt petits de testimonis potencials. Per exemple, Jaeschke 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 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)$.

Bibliografia

• 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.