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 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; Michael Oser Rabin modificó la propuesta de Miller para obtener un algoritmo probabilístico que no utiliza resultados no probados.
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.
Dado un entero impar n > 2, escribimos n como 2s⋅d + 1 donde s y d son enteros positivos y d es impar. Sea a un número entero tal que 0 < a < n. Entonces, diremos que n es probable primo fuerte para la base a si se cumple alguna de las siguientes relaciones de congruencia:
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 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.
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 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, …, n−1.
Aquí una demostración de que cuando n es un primo impar, las únicas raíces cuadradas de 1 modulo n son 1 y −1.
Aquí una demostración de que si n es un primo impar, entonces n es probable primo fuerte para cualquier base a.
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:
El tiempo de ejecución de este algoritmo es , 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 .
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.
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 . En la práctica, la probabilidad parece ser mucho menor, según un artículo de Damgård, Landrock y Pomerance.
Asumiendo correcta la hipótesis generalizada de Riemann, se puede demostrar que, n es probable primo fuerte para a tal que entonces n es un número primo. Con esto se tiene un test determinístico de primalidad de costo .
