Ver el código de «Test de primalidad de Miller-Rabin»

El '''test de primalidad de Miller-Rabin''' es un [[test de primalidad]], es decir, un [[algoritmo]] para determinar si un número dado es [[número primo|primo]], similar al [[test de primalidad de Fermat]]. Su versión original fue propuesta por G. L. Miller, se trataba de un [[algoritmo determinista]], pero basado en la no demostrada [[hipótesis generalizada de Riemann]];<ref>{{cita publicación |apellidos= Miller |nombre= Gary |año= 1975 |título= Riemann's Hypothesis and tests for primality|publicación= Journal of Computer and System Sciences|volumen= 13|número= 3|páginas= 300-317|doi= 10.1016/S0022-0000(76)80043-8|url= |fechaacceso=13 de febrero de 2016}}</ref> [[Michael Oser Rabin]] modificó la propuesta de Miller para obtener un [[algoritmo probabilístico]] que no utiliza resultados no probados.<ref>{{cita publicación |apellidos= Rabin |nombre= Michael|año= 1980 |título= Probabilistic algorithm for testing primality|publicación= Journal of Number Theory|volumen= 12|número= 1|páginas= 128-138|doi= 10.1016/0022-314X(80)90084-0 |fechaacceso=13 de febrero de 2016}}</ref>

== Conceptos matemáticos ==

De forma similar a las pruebas Fermat y Solovay-Strassen, la prueba de primalidad de Miller-Rabin comprueba si una propiedad específica, que se sabe que es verdadera para los números primos, se satisface para el número a prueba.

=== Probables primos fuertes ===

Dado  un entero  impar {{nowrap|''n'' > 2}}, escribimos ''n'' como {{nowrap|2<sup>''s''</sup>⋅''d'' + 1}} donde ''s'' y ''d'' son enteros positivos y ''d'' es impar. 
Sea ''a'' un [[número entero]] tal que   {{nowrap|0 < ''a'' < ''n''}}.
Entonces, diremos que ''n'' es  '''[[probable primo]] fuerte para la base ''a''''' si se cumple alguna de las siguientes [[aritmética modular|relaciones de congruencia]]:

* <math>a^{d} \equiv 1 \pmod{n}</math>;
* <math>a^{2^r\cdot d} \equiv -1 \pmod{n}</math>  para algún {{nowrap|0 ≤ r < ''s''}}.

La idea detrás del test de Miller-Rabín es que cuando  ''n'' es un primo impar, pasa el test debido a dos resultados: 
* por el [[pequeño teorema de Fermat]], <math>a^{n-1} \equiv 1 \pmod{n}</math> (esta propiedad por sí sola es una noción más débil ''probable primo débil para la base a'', sobre la cual está basado el test de primalidad de Fermat);
* las únicas raíces cuadradas del 1 módulo ''n'' son 1 y −1.

Por contraposición,  si ''n'' no es un probable primo fuerte para alguna base ''a'', entonces ''n'' es compuesto y  ''a'' es llamado un  '''testigo''' de la propiedad de que ''n'' es compuesto.

Sin embargo, esta propiedad no es una caracterización exacta de los números primos. Si ''n'' es compuesto, puede haber una base ''a'' para la cual  ''n'' sea probable primo fuerte, en cuyo caso se llama un '''pseudoprimo fuerte''' y ''a'' se lo denomina un  '''mentiroso fuerte'''.

El test probabilístico de Miller-Rabin se basa en la comprobación para diferentes bases de que un número dado es probable primo fuerte.

=== Elección de bases ===

Afortunadamente, ningún [[número compuesto]] es un pseudoprimo fuerte para todas las bases al mismo tiempo. Sin embargo, no se conoce una forma sencilla de encontrar un testigo. Una solución ingenua es probar todas las bases posibles, lo que produce un algoritmo determinista ineficiente. La prueba de Miller determinista es una variante más eficiente de esto.

Otra solución es elegir una base al azar. Esto produce una rápida prueba probabilística. Cuando ''n'' es compuesto, la mayoría de las bases son testigos, por lo que la prueba detectará ''n'' como compuesto con una probabilidad razonablemente alta, mayor que 0.75. Podemos reducir rápidamente la probabilidad de un [[Errores de tipo I y de tipo II|falso positivo]] a una tasa arbitrariamente pequeña, combinando el resultado de tantas bases elegidas independientemente como sea necesario para lograr dicha tasa. En esto consiste el test probabilístico de Miller-Rabin. El número de bases a probar no depende de ''n''.

Para hacer el test a un '' n '' arbitrariamente grande, elegir bases al azar es esencial, ya que no conocemos la distribución de testigos y mentirosos fuertes entre los números  1, 2, …, {{nowrap|''n''−1}}.{{efn|
Por ejemplo, en 1995, Arnault da un número compuesto de 397 dígitos para el cual todas las bases menores a 307 son mentirosas fuertes; se informó que este número es primo por la función [[Maple (software)| Maple]] <code> isprime () </code>, porque implementó la prueba de Miller-Rabin con las bases específicas 2, 3, 5, 7 y 11.<ref name = "Arnault397Digit"> {{cite journal | title = Construyendo números de Carmichael que son fuertes pseudoprimes en varias bases | journal = Journal of Symbolic Computation | fecha = agosto de 1995 | volumen = 20 | número = 2 | páginas = 151–161 | autor = F. Arnault | doi = 10.1006/jsco.1995.1042}} </ref>
}}


=== Demostraciones ===

Aquí una demostración de que cuando ''n'' es un primo impar, las únicas raíces cuadradas de 1 módulo ''n'' son 1 y −1.

{{Demostración|plegada=no|1= Sea ''x'' tal que <math>x^2 \equiv 1 \pmod{n}</math>, luego <math>x^2 - 1 \equiv 0 \pmod{n}</math>, como <math>x^2 -1 = (x-1)(x+1)</math>, obtenemos  <math>(x-1)(x+1) \equiv 0 \pmod{n}</math>. Esto quiere decir  que <math>n|  (x-1)(x+1)</math>. Como ''n''  es primo, <math>n | x -1</math> o <math>n| x +1</math>, es decir <math>x  \equiv 1 \pmod{n}</math>  o <math>x  \equiv -1 \pmod{n}</math>.}}

Aquí una demostración de que  si ''n'' es un primo impar, entonces ''n'' es probable primo fuerte para cualquier base  ''a''.

{{Demostración|plegada=no|1= Consideremos la sucesión <math>a^{2^s \cdot d}, a^{2^{s-1} \cdot d}, \dots, a^{2d}, a^d</math> y  observemos que cada término de la sucesión es el cuadrado del siguiente.
* Por el teorema de Fermat  <math>a^{2^s \cdot d} = a^{n-1} \equiv 1 \pmod{n}</math>. Luego <math>(a^{2^{s-1} \cdot d})^2 \equiv 1 \pmod{n}</math> y por lo tanto <math>a^{2^{s-1} \cdot d}</math> es una raíz cuadrada de 1 módulo ''n''. Por  lo anterior obtenemos  que  <math>a^{2^{s-1} \cdot d} \equiv \pm 1 \pmod{n}</math>.
* Si  <math>a^{2^{s-1} \cdot d} \equiv - 1 \pmod{n}</math>, obtenemos el resultado.  En caso contrario  <math>a^{2^{s-1} \cdot d} \equiv 1 \pmod{n}</math>,  luego <math>(a^{2^{s-2} \cdot d})^2 \equiv 1 \pmod{n}</math> y por lo tanto <math>a^{2^{s-2} \cdot d}</math> es una raíz cuadrada de 1 módulo ''n'' y en consecuencia  <math>a^{2^{s-2} \cdot d} \equiv \pm 1 \pmod{n}</math>.
* Iterando el razonamiento anterior concluimos que alguno de los términos de la sucesión <math> a^{2^{r} \cdot d}</math>  es congruente   a -1 módulo ''n'' o bien todos los términos son congruentes a 1,  en particular <math>a^{d} \equiv 1 \pmod{n}</math>, con lo cual ''n'' resulta ser probable primo fuerte.}}

== Test de Miller–Rabin ==

El algoritmo se puede escribir en [[pseudocódigo]] de la siguiente manera. El parámetro ''k'' determina la precisión de la prueba. Cuanto mayor sea el número de rondas (''k'' es el número de rondas), mayor precisión tendrá el resultado. 

Pseudocódigo estilo [[Python]]:
<!-- javascript syntax color works well for pseudocode -->
<syntaxhighlight lang="python">
def test_Miller_Rabin(n: int, k: int) -> bool:
    s, d = satisfacen n = 2**s * d + 1, d impar
    repetir k veces:
        a = entero al azar entre 2 y n-1
        fpp = False # fuertemente primo en base a
        if 1 == a**d % n:
            fpp = True
        else:
            r = 0
            while r  <= s and fpp == False:
                if n - 1 == a**(2**r * d) % n:
                    fpp = True
         if fpp == False: # si no pasa la prueba
            return False
    # si pasó las k pruebas
    return True
</syntaxhighlight>

== Complejidad ==
El [[tiempo de ejecución]] de este algoritmo es <math> O(k\ln^3 n)</math>, donde ''n'' es el número testeado y ''k'' es el número de rondas realizadas; por lo tanto, este es un algoritmo eficiente, de tiempo polinomial respecto a la cantidad de dígitos de ''n''. La multiplicación basada en [[transformada rápida de Fourier]] puede reducir el tiempo de ejecución a <math> O(k\ln^2(n)\ln(n)\ln(\ln \ln n))</math>.

== Fiabilidad del test ==
Debido a su baja probabilidad de fallo, es el test más utilizado en la práctica, a la hora de aplicaciones en [[criptografía de clave pública]].<ref>{{cita libro|apellido= Menezes|nombre= Alfred|apellido2= van Oorschot|nombre2= Paul|apellido3= Vanstone|nombre3= Scott|título= Handbook of applied cryptography|url= https://archive.org/details/handbookofapplie0000mene/page/138|fechaacceso= 14 de febrero de 2016|idioma= inglés|edición= quinta|año= 2001|editor= CRC|isbn= 0-8493-8523-7|capítulo= Public-Key Parameters|página= [https://archive.org/details/handbookofapplie0000mene/page/138 138]}}</ref>

Se puede demostrar que un número que pasa una prueba de ser probable primo fuerte tiene una probabilidad de 3/4 de ser primo. Luego, que la probabilidad de que un número compuesto pase ''h'' iteraciones del test con bases escogidas al azar es menor a <math>\tfrac 1 {4^h}</math>. En la práctica, la probabilidad parece ser mucho menor, según un artículo de Damgård, Landrock y Pomerance.<ref>{{cita publicación |apellido=Damgård |nombre=Ivan |apellido2=Landrock |nombre2=Peter |apellido3=Pomerance |nombre3=Carl |año=1993 |título=Average case error estimates for the strong probable prime test |publicación=Mathematics of Computation |volumen=61 |número=203 |páginas=177–194 |url=http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf |doi=10.2307/2152945|idioma=inglés}}</ref>

Asumiendo correcta la hipótesis generalizada de Riemann, se puede demostrar que, ''n'' es probable primo fuerte para ''a'' tal que <math> 0 \le a \le  2 \ln^2 n</math> entonces ''n'' es un número primo. Con esto se tiene un test determinístico de primalidad de costo  <math> O(\ln^4 n)</math>.

== Referencias ==
{{listaref}}

== Enlaces externos ==
{{wikilibros
| nombre = Implementación de algoritmos de teoría de números/Test de primalidad de Miller-Rabin
| etiqueta = implementaciones del test de primalidad de Miller-Rabin
| objeto = un libro o manual sobre
| preposición = 
| idioma = 
}}
* {{MathWorld|Rabin-MillerStrongPseudoprimeTest|Rabin-Miller Strong Pseudoprime Test}} 
* [http://stackoverflow.com/questions/4236673/sample-code-for-fast-primality-testing-in-c-sharp/4236870#4236870 Código del test en C]

{{Control de autoridades}}
[[Categoría:Tests de primalidad]]
[[Categoría:Epónimos relacionados con las matemáticas|Miller-Rabin, test]]