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 para la investigación de una prueba de primalidad determinista de tiempo polinomial . 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 . [1] Michael O. Rabin lo modificó para obtener un algoritmo probabilístico incondicional en 1980. [2] [a]
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 :
- ;
- 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);
- 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 un 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. [4] : §8
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 . [B]
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.
Ciertamente 1 y −1, cuando se elevan al cuadrado módulo n , siempre dan 1. Queda por mostrar que no hay otras raíces cuadradas de 1 módulo n . Este es un caso especial, aplicado aquí con el polinomio X 2 - 1 sobre el campo finito Z / n Z , del hecho más general de que un polinomio sobre algún campo no tiene más raíces que su grado (este teorema se sigue de la existencia de una división euclidiana para polinomios ). Aquí sigue una demostración más elemental. Suponga que x es una raíz cuadrada de 1 módulo n . Luego:
En otras palabras, n divide el producto ( x - 1) ( x + 1). . Según el lema de Euclides , dado que n es primo, divide uno de los factores x - 1 o x + 1, lo que implica que x es congruente con 1 o con −1 módulo n .
Aquí hay una prueba de que si n es un primo impar, entonces es un primo probable fuerte para la base a .
Por el pequeño teorema de Fermat:
Cada término de la secuencia , es una raíz cuadrada del término anterior. Dado que el primer término es congruente con 1, el segundo término es una raíz cuadrada módulo n de 1. Según el lema anterior , es congruente con 1 o −1. Si es congruente con −1, hemos terminado. De lo contrario, es congruente con 1 y podemos iterar el razonamiento . Al final, uno de los términos es congruente con -1, o todos son congruentes con 1, y en particular el último término, a d , es.
Ejemplo
Suponga que deseamos determinar si n = 221 es primo. Escribimos n −1 como 2 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 55 mod 221 = 47 ≠ 1, n - 1
- un 2 1 · d mod n = 174 110 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 55 mod 221 = 188 ≠ 1, n - 1
- un 2 1 · d mod n = 137 110 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.
Entrada n. ° 1 : n > 3, un entero impar que se probará para determinar la primalidad. Entrada n. ° 2 : k , el número de rondas de prueba que se realizarán. Salida : " compuesto " si se encuentra que n es compuesto, " probablemente primo " en caso contrarioescriba n como 2 r · d + 1 con d impar (factorizando potencias de 2 de n - 1)WitnessLoop: repetir k veces : elija un entero aleatorio a en el rango [2, n - 2] x ← a d mod n si x = 1 o x = n - 1 luego continúe WitnessLoop repetir r - 1 veces : x ← x 2 mod n si x = n - 1 luego continúe WitnessLoop return " composite " return " probablemente principal "
Complejidad
Utilizando el cuadrado repetido , el tiempo de ejecución de este algoritmo es O ( k log 3 n ) , donde n es el número probado para determinar la 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 2 n log n log log log n ) = Õ ( k log 2 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 . [2] [6] 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 . [7] 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. [c] 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 estamos interesados en 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 :
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 falso negativo ). Al eliminar la parte izquierda del denominador , obtenemos un límite superior simple:
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 sobre. 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.
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 ) 2 ) , lo cual ya fue señalado por Miller. [1] La constante involucrada en la notación Big O fue reducida a 2 por Eric Bach . [9] Esto conduce al siguiente algoritmo de prueba de primalidad determinista, conocido como prueba de Miller :
Entrada : n > 1, un entero impar que se probará en cuanto a primalidad Salida : " compuesto " si n es compuesto, " primo " en caso contrarioescriba n como 2 r · d + 1 con d impar (factorizando potencias de 2 de n - 1)WitnessLoop: para todo a en el rango [2, min ( n −2, ⌊2 (ln n ) 2 ⌋)]: x ← a d mod n si x = 1 o x = n - 1 entonces continúe WitnessLoop repetir r - 1 veces : x ← x 2 mod n si x = n - 1 entonces continúa WitnessLoop devuelve " compuesto " devuelve " primo "
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 . [6]
El tiempo de ejecución del algoritmo es, en la notación O suave , Õ ((log n ) 4 ) (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 fines 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.
Prueba 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 ) 2 , ya que se sabe que son suficientes conjuntos mucho más pequeños de testigos potenciales. Por ejemplo, Pomerance, Selfridge, Wagstaff [4] y Jaeschke [10] 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.
Utilizando el trabajo de Feitsma y Galway que enumera todos los pseudoprimes de base 2 en 2010, esto se amplió (ver OEIS : A014233 ), y el primer resultado se muestra más tarde utilizando diferentes métodos en Jiang y Deng: [11]
- 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 64 , es suficiente probar a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 y 37.
Sorenson y Webster [12] 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. [13] [14] [15] [16] 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 ) . [17] 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 . [18] : 1402 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 0 = a d · 2 Se ha comprobado que s −1 de la variable x es diferente de ± 1, podemos deducir que x 0 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 0 2 ≡ 1 (mod n ) , sabemos que n divide x 0 2 - 1 = ( x 0 - 1) ( x 0 + 1) ;
- dado que x 0 ≢ ± 1 (mod n ) , sabemos que n no divide x 0 - 1 ni x 0 + 1 .
De esto deducimos que A = MCD ( x 0 - 1, n ) y B = MCD ( x 0 + 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:
Entrada n. ° 1 : n > 3, un entero impar que se probará para determinar la primalidad. Entrada n. ° 2 : k , el número de rondas de prueba para realizar Salida : (" múltiplo de ", m ) si un factor no trivial m de n es encontrado, " compuesto " si, por lo demás, se encuentra que n es compuesto, " Probablemente prima " de lo contrarioescriba n como 2 r · d + 1 con d impar (factorizando potencias de 2 de n - 1)WitnessLoop: repetir k veces : elija un número entero aleatorio a en el rango [2, n - 2] x ← a d mod n si x = 1 o x = n - 1 luego continúe WitnessLoop repetir r - 1 veces : y ← x 2 mod n si y = 1 : return (" múltiplo de ", MCD ( x - 1, n )) x ← y si x = n - 1 entonces continue WitnessLoop return " compuesto " return " probablemente primo "
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 85 mod 341 = 32. y 32 2 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 2 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 . [13]
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:
Entrada n. ° 1 : b , el número de bits del resultado Entrada n. ° 2 : k , el número de rondas de prueba para realizar Salida : un número primo probable fuerte nmientras que es verdadero: Elija un número entero impar aleatorio n en el rango [2 b −1 , 2 b −1] si la prueba de Miller-Rabin con entradas n y k devuelve " probablemente primo " y luego devuelva n
Complejidad
Por supuesto, el tiempo de ejecución en el peor de los casos es infinito, ya que es posible que el ciclo externo 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 ).
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:
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:
Por lo 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 4 ) (o O ( k b 3 ) 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 (mostrada 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:
Por lo tanto, para b suficientemente grande , esta medida de error es menor que. Sin embargo, existen límites mucho mejores.
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 . [7] 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 se cumple 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 [19] ). Nuevamente, este límite simple se puede mejorar para valores grandes de b . Por ejemplo, otro límite derivado de los mismos autores es:
que es válido para todo b ≥ 21 y k ≥ b ⁄ 4 . Este límite es menor que 4- k tan pronto comob≥ 32.
Notas
- ↑ A menudo se dice incorrectamente que MM Artjuhov descubrió la prueba de Miller-Rabinen 1967; una lectura del artículo de Artjuhov [3] (en particular su Teorema E ) muestra que en realidad descubrió la prueba Solovay-Strassen.
- ↑ Por ejemplo, en 1995, Arnault da un número compuesto de 397 dígitos para el cual todas las bases menores a 307 son fuertes mentirosas; se informó que este número era primo por lafunción de Maple
isprime()
, porque implementó la prueba de Miller-Rabin con las bases específicas 2, 3, 5, 7 y 11. [5] - ^ Por ejemplo, en 2018, Albrecht et al. fueron capaces de construir, para muchas bibliotecas criptográficas como OpenSSL y GNU GMP , números compuestos que estas bibliotecas declararon primordiales, demostrando así que no se implementaron con un contexto adversario en mente. [8]
Referencias
- ^ a b Miller, Gary L. (1976), "Hipótesis y pruebas de primalidad de Riemann", Journal of Computer and System Sciences , 13 (3): 300–317, doi : 10.1145 / 800116.803773 , S2CID 10690396
- ^ a b Rabin, Michael O. (1980), "Algoritmo probabilístico para probar la primalidad", Journal of Number Theory , 12 (1): 128-138, doi : 10.1016 / 0022-314X (80) 90084-0
- ^ Artjuhov, MM (1966-1967), "Ciertos criterios para la primacía de los números relacionados con el pequeño teorema de Fermat", Acta Arithmetica , 12 : 355-364, MR 0213289
- ^ a b Carl Pomerance ; John L. Selfridge ; Samuel S. Wagstaff, Jr. (julio de 1980). "Los pseudoprimes a 25 · 10 9 " (PDF) . Matemáticas de la Computación . 35 (151): 1003–1026. doi : 10.1090 / S0025-5718-1980-0572872-7 .
- ^ F. Arnault (agosto de 1995). "Construcción de números de Carmichael que son pseudoprimes fuertes a varias bases" . Revista de Computación Simbólica . 20 (2): 151-161. doi : 10.1006 / jsco.1995.1042 .
- ^ a b Schoof, René (2004), "Cuatro algoritmos de prueba de primalidad" (PDF) , Teoría algorítmica de números: celosías, campos numéricos, curvas y criptografía , Cambridge University Press, ISBN 978-0-521-80854-5
- ^ a b Damgård, I .; Landrock, P. & Pomerance, C. (1993), "Estimaciones de error de caso promedio para la prueba de primos probables fuertes" (PDF) , Mathematics of Computation , 61 (203): 177-194, Bibcode : 1993MaCom..61 .. 177D , doi : 10.2307 / 2152945 , JSTOR 2152945
- ^ Martin R. Albrecht; Jake Massimo; Kenneth G. Paterson; Juraj Somorovsky (15 de octubre de 2018). Prima y prejuicio: prueba de la primacía en condiciones adversas (PDF) . Conferencia ACM SIGSAC sobre seguridad informática y de comunicaciones 2018. Toronto: Association for Computing Machinery . págs. 281-298. doi : 10.1145 / 3243734.3243787 .
- ^ Bach, Eric (1990), "Límites explícitos para las pruebas de primalidad y problemas relacionados", Matemáticas de la computación , 55 (191): 355–380, Bibcode : 1990MaCom..55..355B , doi : 10.2307 / 2008811 , JSTOR 2008811
- ^ Jaeschke, Gerhard (1993), "Sobre pseudoprimas fuertes a varias bases", Matemáticas de la Computación , 61 (204): 915–926, doi : 10.2307 / 2153262 , JSTOR 2153262
- ^ Jiang, Yupeng; Deng, Yingpu (2014). "Pseudoprimes fuertes a las primeras ocho bases principales" . Matemáticas de la Computación . 83 (290): 2915-2924. doi : 10.1090 / S0025-5718-2014-02830-5 .
- ^ Sorenson, Jonathan; Webster, Jonathan (2015). "Pseudoprimes fuertes a doce bases principales". Matemáticas de la Computación . 86 (304): 985–1003. arXiv : 1509.00864 . Código bibliográfico : 2015arXiv150900864S . doi : 10.1090 / mcom / 3134 . S2CID 6955806 .
- ^ a b Caldwell, Chris. "Encontrar números primos y probar la primordialidad - 2.3: una fuerte probabilidad primaria y una prueba práctica" . Las Prime Pages . Consultado el 24 de febrero de 2019 .
- ^ Zhang, Zhenxiang & Tang, Min (2003), "Encontrar pseudoprimos fuertes en varias bases. II", Mathematics of Computation , 72 (44): 2085-2097, Bibcode : 2003MaCom..72.2085Z , doi : 10.1090 / S0025-5718 -03-01545-X
- ^ Sloane, N. J. A. (ed.). "Secuencia A014233 (número impar más pequeño para el cual la prueba de primalidad de Miller-Rabin en bases <= n-ésimo primo no revela composición)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
- ^ Izykowski, Wojciech. "Variantes deterministas de la prueba de primalidad de Miller-Rabin" . Consultado el 24 de febrero de 2019 .
- ^ Alford, WR ; Granville, A .; Pomerance, C. (1994), "Sobre la dificultad de encontrar testigos fiables" (PDF) , Lecture Notes in Computer Science , Springer-Verlag, 877 : 1-16, doi : 10.1007 / 3-540-58691-1_36 , ISBN 978-3-540-58691-3
- ^ Robert Baillie; Samuel S. Wagstaff, Jr. (octubre de 1980). "Lucas Pseudoprimes" (PDF) . Matemáticas de la Computación . 35 (152): 1391-1417. doi : 10.1090 / S0025-5718-1980-0583518-6 . Señor 0583518 .
- ^ Burthe Jr., Ronald J. (1996), "Investigaciones adicionales con la prueba fuerte de primos probables" (PDF) , Mathematics of Computation , 65 (213): 373–381, Bibcode : 1996MaCom..65..373B , doi : 10.1090 / S0025-5718-96-00695-3
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