Algoritmo probabilístico que prueba si un entero impar n es probablemente primo realizando una o más comprobaciones de 'strong probable prime' a bases aleatorias (o elegidas) mediante exponentiación modular y reglas de cuadrado.

Principio

Escribir n-1 = 2^s * d con d impar; para una base a calcular a^d mod n y los cuadrados sucesivos; si ninguno de estos valores es 1 o n-1 en el patrón requerido, n es compuesto. Repetir con bases independientes reduce exponencialmente la probabilidad de error.

Demostración

Probar n=561 con la base a=2: calcular 2^{d} mod 561 y sus cuadrados; la prueba expone un testigo de compositeness (561 es un número de Carmichael), por lo que Miller–Rabin lo detecta como compuesto para algunas bases pero puede resultar 'strong probable prime' para otras —de ahí la necesidad de usar múltiples bases.

Aplicación incorrecta

Tratar un resultado 'probable prime' de Miller–Rabin como prueba absoluta de primalidad sin usar suficientes bases, o emplear muy pocas rondas en contextos criptográficos donde el pequeño error residual puede ser explotado.

Consecuencia

Ofrece un test de primalidad probabilístico rápido y fácilmente ajustable: con una elección/numero adecuado de bases la probabilidad de que un compuesto pase todos los tests se vuelve despreciable; para ciertos rangos de tamaño bases fijas proporcionan resultados deterministas.

Inversión

Usar pruebas de primalidad deterministas (por ejemplo, algoritmos que generan certificados) o la factorización completa para obtener certeza en lugar de garantía probabilística.

Límite

Sólo es una prueba probabilística: afirma 'probable primo' o 'compuesto' con error de un solo sentido (los compuestos pueden pasar); garantías deterministas requieren rondas adicionales, bases elegidas para rangos limitados u otros algoritmos.

Tensión semántica

Compite con tests de primalidad deterministas y basados en certificados: Miller–Rabin es mucho más rápido para números grandes y suficiente para la mayoría de usos prácticos, pero su naturaleza probabilística contrasta con los algoritmos que prueban primalidad definitivamente.

Síntesis

Miller–Rabin es un filtro aleatorizado rápido basado en exponentiación modular y cuadraturas que, con repetición sobre bases independientes, reduce la probabilidad de clasificar erróneamente un compuesto como primo hasta niveles despreciables manteniendo un coste computacional reducido.