Calculadora Test de Miller-Rabin (Primalidad)

Test de primalidad de Miller-Rabin: multi-round probabilistico con error (1/4)^k, deterministico para n<3.3e24, comparacion con Fermat y numeros de Carmichael.

Parámetros de cálculo
Scegli la variante del test.
Numero intero da testare (2 <= n <= 1e15 per calcolo JS esatto).
Base a per il testimone singolo. 2 e' la piu' usata.
Numero di testimoni casuali. Probabilita' di errore <= (1/4)^k.
¿Te ha sido útil esta calculadora?

El test de Miller-Rabin

El test de primalidad de Miller-Rabin es el algoritmo mas usado del mundo para decidir si un numero natural es primo. Miller (1976) lo desarrollo como deterministico bajo la hipótesis de Riemann generalizada; Rabin (1980) lo modifico a forma probabilistica incondicional.

Algoritmo

Para n impar > 3, escribir n − 1 = d · 2^s con d impar. Con base a: calcular x_0 = a^d mod n. Si x_0 = 1 o n−1, probablemente primo. Si no, iterar x_(i+1) = x_i^2 mod n; si algun x_i = n−1, primo. De lo contrario, n es compuesto con testigo a.

Los cuatro modos

  1. Test individual con base especifica.
  2. Multi-round aleatorio, error <= (1/4)^k.
  3. Deterministico con bases fijas para n < 3,3·10^24.
  4. Comparación con Fermat y Carmichael.

Probabilidad de error

Rabin (1980): al menos 3/4 de las bases son testigos de composición. k rounds independientes dan error <= (1/4)^k. Para k = 20: < 10^-12.

Variante deterministica

Con bases fijas se obtiene test exacto hasta limites conocidos: n < 2 047 con a=2; n < 4,76·10^9 con {2, 7, 61}; n < 3,3·10^24 con {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}.

Numeros de Carmichael

561, 1105, 1729, 2465, 2821, 6601, 8911, ... Compuestos que pasan Fermat para toda base coprima. Infinitos pero raros (2.163 bajo 10^9). Miller-Rabin los detecta.

Aplicaciones

  • Generación claves RSA: k = 40 rounds, error < 10^-24.
  • TLS: Diffie-Hellman y curvas elipticas.
  • Blockchain: secp256k1 en Bitcoin.
  • OpenSSL BN_is_prime_ex().
  • Python sympy.isprime(), gmpy2.is_prime().
  • Certificados X.509.

Comparación

  • Trial división: exacto pero O(√n).
  • Fermat: falla con Carmichael.
  • Solovay-Strassen: peor que Miller-Rabin.
  • BPSW: Miller-Rabin + Lucas, sin contraejemplo hasta 2^64.
  • AKS (2002): polinomial deterministico pero lento.
  • ECPP: certificado de primalidad verificable.

Por que un test probabilistico es digno de confianza

Puede parecer inquietante basar la seguridad del mundo en un test que solo dice "probablemente primo", pero el numero detras de esa palabra lo cambia todo. Cada ronda de Miller-Rabin con un testigo aleatorio tiene una probabilidad de error de como maximo un cuarto para un compuesto, y las rondas son independientes, de modo que con k testigos la probabilidad de un falso positivo cae a un cuarto elevado a k. Con solo veinte rondas el error es inferior a una parte en un billon, y con las cuarenta que usa la generacion de claves RSA baja por debajo de una parte en 10 elevado a 24.

Para poner esa cifra en perspectiva, es mucho menor que la probabilidad de que un rayo cosmico invierta un bit en la memoria del ordenador justo durante el calculo, o de que falle el hardware de forma silenciosa. En la practica, un veredicto de Miller-Rabin con suficientes rondas es mas fiable que casi cualquier otra parte del sistema. Esta es la razon por la que los generadores de numeros primos de RSA, TLS y las criptomonedas confian en el sin dudar: la certeza absoluta seria mas lenta y, a efectos practicos, no aportaria nada.

Fermat, los numeros de Carmichael y el test fuerte

Miller-Rabin se apoya en el pequeno teorema de Fermat, que afirma que si n es primo entonces a elevado a n menos uno es congruente con uno modulo n, para toda base a coprima con n. Un test ingenuo simplemente comprueba esta congruencia, pero tiene un punto ciego devastador: los numeros de Carmichael, como 561, 1105 y 1729, son compuestos que sin embargo satisfacen la congruencia de Fermat para todas las bases coprimas con ellos. Un test de Fermat los clasifica erroneamente como primos por mas testigos que se prueben.

Miller-Rabin cierra ese agujero anadiendo una comprobacion mas exigente. Ademas de la condicion de Fermat, exige que a lo largo de los cuadrados sucesivos no aparezca una raiz cuadrada no trivial de uno, es decir un valor distinto de uno y de menos uno cuyo cuadrado sea uno modulo n. Un numero primo nunca tiene tales raices, pero un compuesto si, y el test las detecta. Por eso ningun analogo de los numeros de Carmichael puede enganar a Miller-Rabin para una mayoria de bases, lo que lo hace robusto alli donde el test de Fermat fracasa.

Actualizado a julio de 2026

Preguntas frecuentes

Que es el test de Miller-Rabin?

Es el algoritmo de primalidad mas usado del mundo para decidir si un numero es primo. Desarrollado por Miller en 1976 (deterministico bajo la hipotesis de Riemann generalizada) y hecho probabilistico incondicional por Rabin en 1980, es muy rapido y fiable, en la base de RSA, TLS y las criptomonedas.

Como funciona el algoritmo?

Para n impar se escribe n-1 = d x 2^s con d impar. Elegida una base a, se calcula x = a^d mod n: si x = 1 o x = n-1, n es probablemente primo. Si no, se eleva repetidamente al cuadrado; si algun valor se vuelve n-1, n es probablemente primo, de lo contrario es compuesto con testigo a.

Que modos ofrece la calculadora?

Cuatro: una sola ronda con una base elegida, multi-ronda con k testigos aleatorios y estimacion del error, un test deterministico con bases fijas, y una comparacion directa entre Fermat y Miller-Rabin. Cada modo senala los numeros de Carmichael y muestra los pasos del algoritmo.

Que fiabilidad tiene un test probabilistico?

Cada ronda tiene una probabilidad de error de como maximo 1/4 para un compuesto, y las rondas son independientes: con k testigos el error baja a (1/4)^k. Con 40 rondas (como en RSA) el error es inferior a 10^-24, mucho mas bajo que la probabilidad de que un rayo cosmico corrompa la memoria durante el calculo.

Que es un numero de Carmichael?

Es un numero compuesto que engana al test de Fermat: satisface a^(n-1) congruente con 1 mod n para toda base coprima con n, pese a no ser primo. Los primeros son 561, 1105, 1729, 2465. Miller-Rabin no se deja enganar gracias a la comprobacion de raices cuadradas no triviales de 1.

Que diferencia hay con el test de Fermat?

El test de Fermat solo comprueba a^(n-1) congruente con 1 mod n y falla con los numeros de Carmichael. Miller-Rabin anade la comprobacion de que, al elevar al cuadrado, no aparezca una raiz no trivial de 1 (distinta de +1 y -1). Esta condicion mas fuerte hace robusto a Miller-Rabin donde Fermat se equivoca.

Puede ser deterministico el test?

Si. Para numeros por debajo de un umbral conocido, probar un conjunto fijo de bases garantiza un resultado cierto: las bases {2,3,5,7,11,13,17,19,23,29,31,37} son deterministicas para n < 3,3 x 10^24 (Sorenson-Webster 2015). Para n hasta 10^12 bastan {2,3,5,7,11}, para n hasta 10^9 bastan {2,7,61}.

Donde se usa Miller-Rabin?

En la generacion de claves RSA (con unas 40 rondas), en el intercambio de claves TLS y Diffie-Hellman, en las curvas elipticas como secp256k1 de Bitcoin, y en librerias como OpenSSL, sympy y gmpy2. Es el metodo estandar porque combina velocidad y fiabilidad practicamente absoluta.

Comentarios (0)

Sin comentarios aún. ¡Sé el primero!