Test de primalidad de Miller-Rabin

Esta calculadora comprueba si un número entero es un número primo utilizando el test de primalidad de Miller-Rabin. El test utiliza una serie de números enteros como bases de prueba, que también se llaman testigos de prueba. Los testigos de prueba se pueden obtener de dos maneras: introduciéndolos o generándolos aleatoriamente. Si la prueba devuelve un no, entonces el número dado es definitivamente compuesto; si la prueba devuelve un sí, entonces el número es primo con una alta probabilidad. Cuanto mayor sea el número de testigos, mayor será la precisión de la prueba. Puede entender mejor el resultado detallado de la calculadora leyendo los principios del algoritmo de Miller-Rabin descritos justo debajo de la calculadora.

Test de primalidad de Miller-Rabin

Número entero

Bases

Aleatorio

Lista

Número de rondas

Bases

Detalles

Calcular

Puede ser primo

 

Factorización de potencias de 2

 

El archivo es muy grande; La ralentización del navegador puede ocurrir durante la carga y creación.

Descargar 

 Enlace  Guardar  Widget

Algoritmo del test de primalidad de Miller-Rabin

Para aplicar el test de primalidad de Miller-Rabin a un número entero impar n, representamos un número entero par n-1 como 2^sd, donde d - número entero impar, s - potencia entera de 2. Obtenemos los números s y d dividiendo secuencialmente n-1 por 2 hasta que el resto sea impar.
Después de eso comprobamos secuencialmente, uno de los siguientes es cierto:

1. 
2. 
   donde:
   • a - un testigo de prueba, número entero en el rango [2..n-1]
   • r - un número natural menor que s.

Si se cumple al menos una condición, entonces el a elegido es un testigo de primalidad del número n, y el número n puede ser primo con una alta probabilidad. Para aumentar esta probabilidad, repetimos la prueba para otras bases a generadas aleatoriamente.
Si no se cumplen ambas condiciones, entonces el número n es compuesto, y se puede dejar de hacer la prueba.
El test de primalidad de Miller-Rabin maneja con éxito los números de Carmichael, que no son factibles para el test de primalidad de Fermat.
Por ejemplo el número 29341, erróneamente declarado por el test de Fermat como primo, es determinado como compuesto por el test de Miller- Rabin.

A diferencia del test de Fermat, no hay números de prueba "malos" para el test de Miller-Rabin. Para cualquier número, la prueba da la respuesta correcta con una alta probabilidad. El resultado incorrecto del algoritmo está determinado únicamente por una elección aleatoria de los testigos de prueba, cuya probabilidad es pequeña¹.
Según las investigaciones de Rabin, no más de una cuarta parte de los números del rango [1..n-1] no son testigos² (es decir, dan un resultado erróneo en el test de Miller-Rabin). Por lo tanto, la probabilidad de error final de la prueba de k rondas es inferior a 1/4^k.