Miller-Rabin Primality Test

Miller-Rabin es una prueba de primalidad probabilística: escribiendo n-1=2^s*d, comprueba a^d≡1 o algún a^(2^r*d)≡-1 (mod n), con probabilidad de falso positivo de a lo sumo 1/4 por ronda.

Propósito

Probar la primalidad de forma eficiente y probabilística, usada para generar primos grandes de RSA.

Mecanismo

Para n-1=2^s*d, elija un a aleatorio en [2,n-2] y calcule x=a^d mod n. Si x=1 o n-1, n es probablemente primo. Si no, eleve al cuadrado hasta s-1 veces; si aparece n-1 es probablemente primo; en caso contrario n es compuesto con certeza. Tras k rondas, el error es a lo sumo 4^(-k).