Prueba de primalidad de Miller-Rabin - Miller–Rabin primality test

La prueba de primalidad de Miller-Rabin o la prueba de primalidad de Rabin-Miller es una prueba de primalidad probabilística : un algoritmo que determina si un número dado es probable que sea primo , similar a la prueba de primalidad de Fermat y la prueba de primalidad de Solovay-Strassen .

Tiene importancia histórica en la búsqueda de una prueba de primalidad determinista de tiempo polinómico . Su variante probabilística sigue siendo muy utilizada en la práctica, como una de las pruebas más sencillas y rápidas que se conocen.

Gary L. Miller descubrió la prueba en 1976; La versión de Miller de la prueba es determinista , pero su corrección se basa en la hipótesis ampliada de Riemann no probada . Michael O. Rabin lo modificó para obtener un algoritmo probabilístico incondicional en 1980.

Conceptos matemáticos

De manera similar a las pruebas de Fermat y Solovay-Strassen, la prueba de primalidad de Miller-Rabin verifica si una propiedad específica, que se sabe que se cumple para los valores primos, es válida para el número bajo prueba.

Primos probables fuertes

La propiedad es la siguiente. Para un determinado número entero impar n > 2 , vamos a escribir n como 2 ^s ⋅ d + 1 , donde s y d son números enteros positivos y d es impar. Consideremos un número entero  a , llamado base , tal que 0 < a < n . Entonces, se dice que n es un primo probable fuerte para basar a si se cumple una de estas relaciones de congruencia :

• ${\ Displaystyle a ^ {d} \ equiv 1 {\ pmod {n}}}$;
• ${\ Displaystyle a ^ {2 ^ {r} \ cdot d} \ equiv -1 {\ pmod {n}}}$ para algunos 0 ≤ r < s .

La idea detrás de esta prueba es que cuando n es un primo impar, pasa la prueba debido a dos hechos:

• por el pequeño teorema de Fermat , (esta propiedad por sí sola define la noción más débil de primo probable para basar a , en la que se basa la prueba de Fermat);${\ Displaystyle a ^ {n-1} \ equiv 1 {\ pmod {n}}}$
• las únicas raíces cuadradas de 1 módulo n son 1 y −1.

Por lo tanto, por contraposición , si n no es un primo probable fuerte para la base a , entonces n es definitivamente compuesto, y a se llama testigo de la composición de n (a veces engañosamente llamado testigo fuerte ).

Sin embargo, esta propiedad no es una caracterización exacta de los números primos. Si n es compuesto, no obstante, puede ser un número primo probable fuerte para la base a , en cuyo caso se le llama un pseudoprimo fuerte , y a es un mentiroso fuerte .

Elecciones de bases

Afortunadamente, ningún número compuesto es un pseudoprime fuerte para todas las bases al mismo tiempo. Sin embargo, no se conoce una forma sencilla de encontrar un testigo. Una solución ingenua es probar todas las bases posibles, lo que produce un algoritmo determinista ineficiente. La prueba de Miller es una variante más eficiente de esto (consulte la sección Prueba de Miller a continuación ).

Otra solución es elegir una base al azar. Esto produce una prueba probabilística rápida . Cuando n es compuesto, la mayoría de las bases son testigos, por lo que la prueba detectará n como compuesto con una probabilidad razonablemente alta (consulte la sección Precisión a continuación ). Podemos reducir rápidamente la probabilidad de un falso positivo a una tasa arbitrariamente pequeña, combinando el resultado de tantas bases elegidas independientemente como sea necesario para lograr dicha tasa. Esta es la prueba de Miller-Rabin. El número de bases a probar no depende de n . Parece haber rendimientos decrecientes al probar muchas bases, porque si n es un pseudoprime para alguna base, entonces parece más probable que sea un pseudoprime para otra base.

Para probar n arbitrariamente grande , elegir bases al azar es esencial, ya que no conocemos la distribución de testigos y mentirosos fuertes entre los números 1, 2,…, n −1 .

Sin embargo, un conjunto preseleccionado de unas pocas bases pequeñas garantiza la identificación de todos los compuestos hasta un máximo precalculado. Este máximo es generalmente bastante grande en comparación con las bases. Esto proporciona pruebas deterministas muy rápidas para n suficientemente pequeños (consulte la sección Pruebas con conjuntos pequeños de bases a continuación ).

Pruebas

Aquí hay una prueba de que, cuando n es un primo impar, las únicas raíces cuadradas de 1 módulo n son 1 y −1.

Aquí hay una prueba de que si n es un primo impar, entonces es un primo probable fuerte para la base a .

Ejemplo

Suponga que deseamos determinar si n  = 221 es primo. Escribimos n −1 como 2 ² · 55, de modo que tenemos s  = 2 y d  = 55. Seleccionamos aleatoriamente un número a tal que 1 <  a  <  n - 1, digamos a = 174. Procedemos a calcular:

• a ^{2 0 · d} mod n = 174 ⁵⁵ mod 221 = 47 ≠ 1, n - 1
• un ^{2 1 · d} mod n = 174 ¹¹⁰ mod 221 = 220 = n - 1.

Desde 220 ≡ -1 mod n , o bien 221 es primo, o 174 es un fuerte mentiroso 221. Tratamos otra al azar una , esta vez la elección de un = 137:

• a ^{2 0 · d} mod n = 137 ⁵⁵ mod 221 = 188 ≠ 1, n - 1
• un ^{2 1 · d} mod n = 137 ¹¹⁰ mod 221 = 205 ≠ n - 1.

Por lo tanto, 137 es un testigo de la compostura de 221, y 174 fue de hecho un gran mentiroso. Tenga en cuenta que esto no nos dice nada sobre los factores de 221 (que son 13 y 17). Sin embargo, el ejemplo con 341 en una sección posterior muestra cómo estos cálculos a veces pueden producir un factor de n .

Prueba de Miller-Rabin

El algoritmo se puede escribir en pseudocódigo de la siguiente manera. El parámetro k determina la precisión de la prueba. Cuanto mayor sea el número de rondas, más preciso será el resultado.

Input #1: n > 3, an odd integer to be tested for primality
Input #2: k, the number of rounds of testing to perform
Output: “composite” if n is found to be composite, “probably prime” otherwise

write n as 2r·d + 1 with d odd (by factoring out powers of 2 from n − 1)
WitnessLoop: repeat k times:
    pick a random integer a in the range [2, n − 2]
    x ← ad mod n
    if x = 1 or x = n − 1 then
        continue WitnessLoop
    repeat r − 1 times:
        x ← x2 mod n
        if x = n − 1 then
            continue WitnessLoop
    return “composite”
return “probably prime”

Complejidad

Utilizando la cuadratura repetida , el tiempo de ejecución de este algoritmo es O ( k  log ³ n ) , donde n es el número de prueba de primalidad y k es el número de rondas realizadas; por lo tanto, este es un algoritmo de tiempo polinomial eficiente. La multiplicación basada en FFT puede reducir el tiempo de ejecución a O ( k log ² n log log n log log log n ) = Õ ( k  log ² n ) .

Precisión

El error cometido por la prueba de primalidad se mide por la probabilidad de que un número compuesto se declare probablemente primo. Los más bases de un son juzgados, mejor será la precisión de la prueba. Se puede demostrar que si n es compuesto, entonces como máximo 1 ⁄ 4 de las bases a son fuertes mentirosas para n . Como consecuencia, si n es compuesto, ejecutar k iteraciones de la prueba de Miller-Rabin declarará n probablemente primo con una probabilidad de 4 ^{- k} como máximo .

Esta es una mejora con respecto a la prueba de Solovay-Strassen , cuyo límite de error en el peor de los casos es 2 ^{- k} . Además, la prueba de Miller-Rabin es estrictamente más fuerte que la prueba de Solovay-Strassen en el sentido de que para cada compuesto n , el conjunto de mentirosos fuertes para n es un subconjunto del conjunto de mentirosos de Euler para n , y para muchos n , el subconjunto es adecuado.

Además, para valores grandes de n , la probabilidad de que un número compuesto se declare probablemente primo es a menudo significativamente menor que 4 ^{- k} . Por ejemplo, para la mayoría de los números n , esta probabilidad está limitada por 8 ^{- k} ; la proporción de números n que invalidan este límite superior desaparece cuando consideramos valores más grandes de n . Por lo tanto, el caso promedio tiene una precisión mucho mejor que 4 ^{- k} , un hecho que puede aprovecharse para generar números primos probables (ver más abajo ). Sin embargo, no se debe confiar en tales límites de error mejorados para verificar primos cuya distribución de probabilidad no está controlada, ya que un adversario criptográfico podría enviar un pseudoprime cuidadosamente elegido para vencer la prueba de primalidad. En tales contextos, solo se puede confiar en el límite de error del peor caso de 4 ^{- k} .

La medida de error anterior es la probabilidad de que un número compuesto se declare como un número primo probable fuerte después de k rondas de prueba; en palabras matemáticas, es la probabilidad condicional donde P es el evento de que el número que se está probando sea primo y MR _k es el evento de que pasa la prueba de Miller-Rabin con k rondas. En cambio, a menudo nos interesa la probabilidad condicional inversa : la probabilidad de que un número que ha sido declarado como un número primo probable fuerte sea de hecho compuesto. Estas dos probabilidades están relacionadas por la ley de Bayes : ${\ Displaystyle \ Pr (M \! R_ {k} \ mid \ lnot P)}$${\ Displaystyle \ Pr (\ lnot P \ mid M \! R_ {k})}$

${\ Displaystyle \ Pr (\ lnot P \ mid M \! R_ {k}) = {\ frac {\ Pr (\ lnot P \ land M \! R_ {k})} {\ Pr (\ lnot P \ land M \! R_ {k}) + \ Pr (P \ tierra M \! R_ {k})}} = {\ frac {1} {1 + {\ frac {\ Pr (M \! R_ {k} \ mid P)} {\ Pr (M \! R_ {k} \ mid \ lnot P)}} \ cdot {\ frac {\ Pr (P)} {\ Pr (\ lnot P)}}}} = {\ frac {1} {1 + {\ frac {1} {\ Pr (M \! R_ {k} \ mid \ lnot P)}} \ cdot {\ frac {\ Pr (P)} {1- \ Pr ( PAG)}}}}}$

En la última ecuación, simplificamos la expresión usando el hecho de que todos los números primos se informan correctamente como números primos probables fuertes (la prueba no tiene un falso negativo ). Al eliminar la parte izquierda del denominador , obtenemos un límite superior simple:

${\ Displaystyle \ Pr (\ lnot P \ mid M \! R_ {k}) <\ Pr (M \! R_ {k} \ mid \ lnot P) \ cdot \ left ({\ tfrac {1} {\ Pr (P)}} - 1 \ derecha)}$

Por lo tanto, esta probabilidad condicional está relacionada no solo con la medida de error discutida anteriormente, que está limitada por 4 ^{- k}  , sino también con la distribución de probabilidad del número de entrada. En el caso general, como se dijo anteriormente, esta distribución está controlada por un adversario criptográfico, por lo tanto desconocido, por lo que no podemos deducir mucho al respecto . Sin embargo, en el caso en el que usamos la prueba de Miller-Rabin para generar números primos (ver más abajo ), la distribución la elige el propio generador, por lo que podemos aprovechar este resultado. ${\ Displaystyle \ Pr (\ lnot P \ mid M \! R_ {k})}$

Variantes deterministas

Prueba de Miller

El algoritmo de Miller-Rabin se puede hacer determinista tratando posible una por debajo de un cierto límite. Tomar n como límite implicaría O ( n ) ensayos, por lo que el tiempo de ejecución sería exponencial con respecto al tamaño log n de la entrada. Para mejorar el tiempo de ejecución, el desafío es reducir el límite tanto como sea posible mientras se mantiene la confiabilidad de la prueba.

Si el número probado n es compuesto, los mentirosos fuertes un coprimo con n están contenidas en una adecuada subgrupo del grupo ( Z / n Z ) *, que significa que si probamos todos una de un conjunto que genera ( Z / n Z ) *, uno de ellos debe estar fuera de dicho subgrupo, por lo que debe ser testigo de la composición de n . Suponiendo la verdad de la hipótesis de Riemann generalizada (GRH), se sabe que el grupo es generado por sus elementos menores que O (( ln n ) ² ) , lo cual ya fue señalado por Miller. La constante involucrada en la notación Big O fue reducida a 2 por Eric Bach . Esto conduce al siguiente algoritmo de prueba de primalidad determinista, conocido como prueba de Miller :

Input: n > 1, an odd integer to be tested for primality
Output: “composite” if n is composite, “prime” otherwise

write n as 2r·d + 1 with d odd (by factoring out powers of 2 from n − 1)
WitnessLoop: for all a in the range [2, min(n−2, ⌊2(ln n)2⌋)]:
    x ← ad mod n
    if x = 1 or x = n − 1 then
        continue WitnessLoop
    repeat r − 1 times:
        x ← x2 mod n
        if x = n − 1 then
            continue WitnessLoop
    return “composite”
return “prime”

No se necesita todo el poder de la hipótesis de Riemann generalizada para asegurar la exactitud de la prueba: como tratamos con subgrupos de índice par , es suficiente asumir la validez de GRH para caracteres de Dirichlet cuadráticos .

El tiempo de ejecución del algoritmo es, en la notación O suave , Õ ((log n ) ⁴ ) (usando la multiplicación basada en FFT).

La prueba de Miller no se utiliza en la práctica. Para la mayoría de los propósitos, el uso adecuado de la prueba probabilística de Miller-Rabin o la prueba de primalidad de Baillie-PSW brinda suficiente confianza mientras se ejecuta mucho más rápido. También es más lento en la práctica que los métodos de prueba comúnmente utilizados, como APR-CL y ECPP, que dan resultados que no se basan en suposiciones no probadas. Para propósitos teóricos que requieren un algoritmo de tiempo polinomial determinista, fue reemplazado por la prueba de primalidad AKS , que tampoco se basa en suposiciones no probadas.

Pruebas contra pequeños conjuntos de bases

Cuando el número n que se va a probar es pequeño, no es necesario probar todo a <2 (ln n ) ² , ya que se sabe que son suficientes conjuntos mucho más pequeños de testigos potenciales. Por ejemplo, Pomerance, Selfridge, Wagstaff y Jaeschke han verificado que

• si n <2,047, es suficiente probar a = 2;
• si n <1373,653, es suficiente probar a = 2 y 3;
• si n <9.080.191, es suficiente probar a = 31 y 73;
• si n <25,326,001, es suficiente probar a = 2, 3 y 5;
• si n <3,215,031,751, es suficiente probar a = 2, 3, 5 y 7;
• si n <4,759,123,141, es suficiente probar a = 2, 7 y 61;
• si n <1,122,004,669,633, es suficiente probar a = 2, 13, 23 y 1662803;
• si n <2,152,302,898,747, es suficiente probar a = 2, 3, 5, 7 y 11;
• si n <3.474.749.660.383, es suficiente probar a = 2, 3, 5, 7, 11 y 13;
• si n <341,550,071,728,321, es suficiente probar a = 2, 3, 5, 7, 11, 13 y 17.

Usando el trabajo de Feitsma y Galway enumerando todos los pseudoprimes de base 2 en 2010, esto se extendió (ver OEIS :  A014233 ), y el primer resultado se muestra más tarde usando diferentes métodos en Jiang y Deng:

• si n <3,825,123,056,546,413,051, es suficiente probar a = 2, 3, 5, 7, 11, 13, 17, 19 y 23.
• si n <18,446,744,073,709,551,616 = 2 ⁶⁴ , es suficiente probar a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 y 37.

Sorenson y Webster verifican lo anterior y calculan resultados precisos para estos resultados superiores a 64 bits:

• si n <318,665,857,834,031,151,167,461, es suficiente probar a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 y 37.
• si n <3,317,044,064,679,887,385,961,981, es suficiente probar a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 y 41.

Existen otros criterios de este tipo, a menudo más eficientes (se requieren menos bases) que los mostrados anteriormente. Proporcionan pruebas de primalidad deterministas muy rápidas para números en el rango apropiado, sin ningún supuesto.

Hay una pequeña lista de posibles testigos para cada posible tamaño de entrada (en la mayoría de b valores para b números -bit). Sin embargo, ningún conjunto finito de bases es suficiente para todos los números compuestos. Alford, Granville y Pomerance han demostrado que existen infinitos números compuestos n cuyo testigo de composición más pequeño es al menos (ln n ) ^{1 / (3ln ln ln n )} . También argumentan heurísticamente que el número más pequeño w tal que cada número compuesto por debajo de n tenga un testigo de composición menor que w debería ser de orden Θ (log n log log n ).

Variantes para encontrar factores

Al insertar los cálculos del máximo común divisor en el algoritmo anterior, a veces podemos obtener un factor de n en lugar de simplemente determinar que n es compuesto. Esto ocurre, por ejemplo, cuando n es una base prima probable a pero no una base prima probable fuerte a . Podemos detectar este caso en el algoritmo comparando x en el bucle interno no solo con -1, sino también con 1.

Si en alguna iteración 1 ≤ i < r del ciclo interno, el algoritmo descubre que el valor a ^{d · 2 i} mod n de la variable x es igual a 1, entonces, sabiendo que el valor anterior x ₀ = a ^{d · 2} Se ha comprobado que ^{s −1} de la variable x es diferente de ± 1, podemos deducir que x ₀ es una raíz cuadrada de 1 que no es ni 1 ni −1. Como esto no es posible cuando n es primo, esto implica que n es compuesto. Es más:

• dado que x ₀ ² ≡ 1 (mod n ) , sabemos que n divide x ₀ ² - 1 = ( x ₀ - 1) ( x ₀ + 1) ;
• dado que x ₀ ≢ ± 1 (mod n ) , sabemos que n no divide x ₀ - 1 ni x ₀ + 1 .

De esto deducimos que A = MCD ( x ₀ - 1, n ) y B = MCD ( x ₀ + 1, n ) son factores no triviales (no necesariamente primos) de n (de hecho, dado que n es impar, estos los factores son coprime yn = A · B ). Por lo tanto, si la factorización es un objetivo, estos cálculos de GCD se pueden insertar en el algoritmo con un pequeño costo computacional adicional. Esto conduce al siguiente pseudocódigo, donde se resalta el código agregado o modificado:

Input #1: n > 3, an odd integer to be tested for primality
Input #2: k, the number of rounds of testing to perform
Output: (“multiple of”, m) if a non‐trivial factor m of n is found,
        “composite” if n is otherwise found to be composite,
        “probably prime” otherwise

write n as 2r·d + 1 with d odd (by factoring out powers of 2 from n − 1)
WitnessLoop: repeat k times:
    pick a random integer a in the range [2, n − 2]
    x ← ad mod n
    if x = 1 or x = n − 1 then
        continue WitnessLoop
    repeat r − 1 times:
        y ← x2 mod n
        if y = 1:
            return (“multiple of”, GCD(x − 1, n))
        x ← y
        if x = n − 1 then
            continue WitnessLoop
    return “composite”
return “probably prime”

Este algoritmo no produce un algoritmo de factorización probabilística porque solo es capaz de encontrar factores para números n que son pseudoprime a la base a (en otras palabras, para números n tales que a ^{n −1} ≡ 1 mod n ). Para otros números, el algoritmo solo devuelve " compuesto " sin más información.

Por ejemplo, considere n = 341 y a = 2. Tenemos n - 1 = 85 · 4. Entonces 2 ⁸⁵ mod 341 = 32. y 32 ² mod 341 = 1. Esto nos dice que n es una pseudoprime base 2, pero no una fuerte pseudoprime base 2. Al calcular un GCD en esta etapa, encontramos un factor de 341: MCD (32 - 1, 341) = 31. De hecho, 341 = 11 · 31 .

Para encontrar factores con más frecuencia, las mismas ideas también se pueden aplicar a las raíces cuadradas de -1 (o cualquier otro número). Esta estrategia se puede implementar aprovechando el conocimiento de rondas anteriores de la prueba Miller-Rabin. En esas rondas que puede haber identificado un módulo raíz cuadrada n de -1, por ejemplo R . Entonces, cuando x ² mod n = n −1 , podemos comparar el valor de x contra R : si x no es ni R ni n - R , entonces GCD ( x - R , n ) y GCD ( x + R , n ) son factores no triviales de n .

Generación de probables primos

La prueba de Miller-Rabin se puede utilizar para generar números primos probables fuertes, simplemente extrayendo números enteros al azar hasta que uno pase la prueba. Este algoritmo termina casi con seguridad (ya que en cada iteración existe la posibilidad de extraer un número primo). El pseudocódigo para la generación de b - mordió fuertes probable primo (con el bit más significativo) es el siguiente:

Input #1: b, the number of bits of the result
Input #2: k, the number of rounds of testing to perform
Output: a strong probable prime n

while True:
    pick a random odd integer n in the range [2b−1, 2b−1]
    if the Miller–Rabin test with inputs n and k returns “probably prime” then
        return n

Complejidad

Por supuesto, el tiempo de ejecución en el peor de los casos es infinito, ya que es posible que el bucle exterior nunca termine, pero eso sucede con probabilidad cero. Según la distribución geométrica , el número esperado de dibujos es (reutilizando notaciones de antes ). ${\ Displaystyle {\ tfrac {1} {\ Pr (M \! R_ {k})}}}$

A medida que cualquier número primo pasa la prueba, la probabilidad de ser primo da un límite inferior aproximado a la probabilidad de pasar la prueba. Si dibujamos números enteros impares uniformemente en el rango [2 ^{b −1} , 2 ^b −1], entonces obtenemos:

${\ Displaystyle \ Pr (M \! R_ {k})> \ Pr (P) = {\ frac {\ pi \ left (2 ^ {b} \ right) - \ pi \ left (2 ^ {b-1 } \ right)} {2 ^ {b-2}}}}$

donde π es la función de conteo de primos . Usando una expansión asintótica de π (una extensión del teorema de los números primos ), podemos aproximar esta probabilidad cuando b crece hacia el infinito. Encontramos:

${\ Displaystyle \ Pr (P) = {\ tfrac {2} {\ ln 2}} b ^ {- 1} + {\ mathcal {O}} \ left (b ^ {- 3} \ right)}$

${\ displaystyle {\ tfrac {1} {\ Pr (P)}} = {\ tfrac {\ ln 2} {2}} b + {\ mathcal {O}} \ left (b ^ {- 1} \ right) }$

Por tanto, podemos esperar que el generador no ejecute más pruebas de Miller-Rabin que un número proporcional a b . Teniendo en cuenta la complejidad del peor caso de cada prueba Miller-Rabin (véase anteriormente ), el tiempo esperado del generador se ejecuta con entradas b y k a continuación, está limitada por O ( k b ⁴ ) (o O ( k b ³ ) usando Multiplicación basada en FFT).

Precisión

La medida de error de este generador es la probabilidad de que genere un número compuesto.

Usando la relación entre probabilidades condicionales (mostradas en una sección anterior ) y el comportamiento asintótico de (mostrado justo antes), esta medida de error puede tener un límite superior aproximado: ${\ Displaystyle \ Pr (P)}$

${\ Displaystyle \ Pr (\ lnot P \ mid M \! R_ {k}) <\ Pr (M \! R_ {k} \ mid \ lnot P) \ cdot \ left ({\ tfrac {1} {\ Pr (P)}} - 1 \ right) \ leq 4 ^ {- k} \ cdot \ left ({\ tfrac {\ ln 2} {2}} b-1 + {\ mathcal {O}} \ left (b ^ {- 1} \ right) \ right)}$

Por lo tanto, para b suficientemente grande , esta medida de error es menor que . Sin embargo, existen límites mucho mejores. ${\ Displaystyle {\ tfrac {\ ln 2} {2}} \ cdot b \ cdot 4 ^ {- k}}$

Usando el hecho de que la propia prueba de Miller-Rabin a menudo tiene un límite de error mucho más pequeño que 4 ^{- k} (véase anteriormente ), Damgard , Landrock y Pomerance derivan varios límites de error para el generador, con diversas clases de parámetros b y k . Estos límites de error permiten al implementador elegir un k razonable para una precisión deseada.

Uno de estos límites de error es 4 ^{- k} , que es válido para todo b ≥ 2 (los autores solo lo mostraron para b ≥ 51, mientras que Ronald Burthe Jr. completó la demostración con los valores restantes 2 ≤ b ≤ 50). Nuevamente, este límite simple se puede mejorar para valores grandes de b . Por ejemplo, otro límite derivado de los mismos autores es:

${\ Displaystyle \ left ({\ tfrac {1} {7}} b ^ {15/4} 2 ^ {- b / 2} \ right) \ cdot 4 ^ {- k}}$

que es válido para todo b ≥ 21 y k ≥ b ⁄ 4 . Este límite es menor que 4 ^{- k} tan pronto como b ≥ 32.

Notas

Referencias

enlaces externos

• Weisstein, Eric W. "Prueba de pseudoprime fuerte de Rabin-Miller" . MathWorld .
• Implementación interactiva en línea de la variante determinista (paso a paso por el algoritmo)
• Applet (alemán)
• Prueba de primalidad de Miller-Rabin en C #
• Prueba de primalidad de Miller-Rabin en JavaScript utilizando aritmética de precisión arbitraria