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;[2]

Descripción del test[3]

Supóngase que n > 1 es un número impar del cual queremos saber si es primo o no. Sean k el número natural y m el impar tales que n − 1 = 2k m y un entero escogido aleatoriamente entre 2 y n − 2.

(Paso 0) Se calcula .

Si , el test culmina con la conclusión de que n es probable primo.

(Paso 1) En caso contrario se calcula .

Si , el test culmina con la conclusión de que n es probable primo.
Si , el test culmina con la conclusión de que n no es primo.

(Paso i) De igual forma, siempre que y se calcula .

Si , el test culmina con la conclusión de que n es probable primo.
Si , el test culmina con la conclusión de que n no es primo.

(Paso k-1) Se calcula .

Si , el test culmina con la conclusión de que n es probable primo.
En cualquier otro caso, el test culmina con la conclusión de que n no es primo.

Si n es un probable primo se escoge un nuevo valor para a, y se itera nuevamente reduciendo el margen de error probable. Al utilizar exponenciación binaria las operaciones necesarias se realizan muy rápidamente.

Other Languages