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;[1] Michael Oser Rabin modificó la propuesta de Miller para obtener un algoritmo probabilístico que no utiliza resultados no probados.
[2] 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.
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.
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.
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.
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.
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.