Principio del algoritmo:
Miller-Rabin es una prueba de primalidad probabilística basada en una extensión del pequeño teorema de Fermat. Para un número impar n, escribe n-1 como 2^r × d, luego comprueba si cumple:
a^d ≡ 1 (mod n) 或 a^(2^i × d) ≡ -1 (mod n) 对某个 0 ≤ i < r
Número de rondas de prueba y precisión:
- Prueba probabilística:Selecciona aleatoriamente una base a; cada ronda de prueba reduce la tasa de error a 1/4
- k rondas de prueba:Tasa de error teórica ≤ (1/4)^k, la tasa de error real es mucho menor
- Prueba determinista:Para n < 3.317.044.064.679.887.385.961.981, usando el conjunto de bases específico {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} se obtienen resultados 100% precisos
Casos especiales:
- Primos pequeños:Números como 2, 3, 5, 7 se identifican directamente
- Números pares:Todos los números pares excepto 2 son compuestos
- Números de Carmichael:Los números que pasan la prueba de Fermat pero son realmente compuestos (ej. 561) pueden ser identificados correctamente por Miller-Rabin