Prueba de primalidad

Algoritmo para determinar si un número es primo

Una prueba de primalidad es un algoritmo para determinar si un número de entrada es primo . Entre otros campos de las matemáticas , se utiliza para la criptografía . A diferencia de la factorización de números enteros , las pruebas de primalidad generalmente no dan factores primos , solo indican si el número de entrada es primo o no. Se piensa que la factorización es un problema computacionalmente difícil, mientras que las pruebas de primalidad son comparativamente fáciles (su tiempo de ejecución es polinomial en el tamaño de la entrada). Algunas pruebas de primalidad prueban que un número es primo, mientras que otras como Miller-Rabin prueban que un número es compuesto . Por lo tanto, estas últimas podrían llamarse con mayor precisión pruebas de composición en lugar de pruebas de primalidad.

Métodos simples

La prueba de primalidad más simple es la división por tanteo : dado un número de entrada, , verifique si es divisible por cualquier número primo entre 2 y (es decir, si la división no deja resto ). Si es así, entonces es compuesto . De lo contrario, es primo. ^[1] Para cualquier divisor , debe haber otro divisor , y un divisor primo de , y por lo tanto, buscar divisores primos como máximo es suficiente. ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle n}$ ${\displaystyle p\geq {\sqrt {n}}}$ ${\displaystyle n/p\leq {\sqrt {n}}}$ ${\displaystyle q}$ ${\displaystyle n/p}$ ${\displaystyle {\sqrt {n}}}$

Por ejemplo, consideremos el número 100, cuyos divisores son estos números:

1, 2, 4, 5, 10, 20, 25, 50, 100.

Cuando se prueban todos los divisores posibles hasta , se descubrirán algunos divisores dos veces . Para observar esto, considere la lista de pares de divisores de 100: ${\displaystyle n}$

${\displaystyle 1\times 100,\;2\times 50,\;4\times 25,\;5\times 20,\;10\times 10,\;20\times 5,\;25\times 4,\;50\times 2,\;100\times 1}$.

Los productos pasados ​​son el reverso de los productos que aparecieron antes. Por ejemplo, y son el reverso uno del otro. Además, el de los dos divisores, y . Esta observación se generaliza a todos los : todos los pares de divisores de contienen un divisor menor o igual a , por lo que el algoritmo solo necesita buscar divisores menores o iguales a para garantizar la detección de todos los pares de divisores. ^[1] ${\displaystyle 10\times 10}$ ${\displaystyle 5\times 20}$ ${\displaystyle 20\times 5}$ ${\displaystyle 5\leq {\sqrt {100}}=10}$ ${\displaystyle 20\geq {\sqrt {100}}=10}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle {\sqrt {n}}}$

Además, 2 es un número primo que divide a 100, lo que demuestra inmediatamente que 100 no es primo. Todo entero positivo excepto 1 es divisible por al menos un número primo según el Teorema Fundamental de la Aritmética . Por lo tanto, el algoritmo solo necesita buscar divisores primos menores o iguales a . ${\displaystyle {\sqrt {n}}}$

Para otro ejemplo, considere cómo este algoritmo determina la primalidad de 17. Uno tiene , y los únicos primos son 2 y 3. Ninguno divide a 17, lo que demuestra que 17 es primo. Para un último ejemplo, considere 221. Uno tiene , y los primos son 2, 3, 5, 7, 11 y 13. Al verificar cada uno, uno descubre que , lo que demuestra que 221 no es primo. ${\displaystyle 4<{\sqrt {17}}<5}$ ${\displaystyle \leq {\sqrt {17}}}$ ${\displaystyle 14<{\sqrt {221}}<15}$ ${\displaystyle \leq {\sqrt {221}}}$ ${\displaystyle 221/13=17}$

En los casos en los que no es posible calcular la lista de primos , también es posible comprobar de forma sencilla (y lenta) si todos los números entre y tienen divisores. Una optimización bastante sencilla consiste en comprobar la divisibilidad por 2 y solo por los números impares entre 3 y , ya que la divisibilidad por un número par implica la divisibilidad por 2. ${\displaystyle \leq {\sqrt {n}}}$ ${\displaystyle 2}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle {\sqrt {n}}}$

Este método se puede mejorar aún más. Observe que todos los primos mayores que 3 tienen la forma para un entero no negativo y . De hecho, cada entero tiene la forma para un entero positivo y . Como 2 divide a , y , y 3 divide a y , los únicos residuos posibles módulo 6 para un primo mayor que 3 son 1 y 5. Por lo tanto, una prueba de primalidad más eficiente para es probar si es divisible por 2 o 3, luego verificar todos los números de la forma y que son . Esto es casi tres veces más rápido que probar todos los números hasta . ${\displaystyle 6k+i}$ ${\displaystyle k}$ ${\displaystyle i\in \{1,5\}}$ ${\displaystyle 6k+i}$ ${\displaystyle k}$ ${\displaystyle i\in \{0,1,2,3,4,5\}}$ ${\displaystyle 6k,6k+2}$ ${\displaystyle 6k+4}$ ${\displaystyle 6k}$ ${\displaystyle 6k+3}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 6k+1}$ ${\displaystyle 6k+5}$ ${\displaystyle \leq {\sqrt {n}}}$ ${\displaystyle {\sqrt {n}}}$

Generalizando aún más, todos los primos mayores que ( c primorial ) son de la forma para los enteros positivos, , y coprimos con . Por ejemplo, considere . Todos los enteros son de la forma para los enteros con . Ahora, 2 divide a , 3 divide a , y 5 divide a . Por lo tanto, todos los números primos mayores que 30 son de la forma para . Por supuesto, no todos los números de la forma con coprimos con son primos. Por ejemplo, no es primo, aunque 17 es coprimo con . ${\displaystyle c\#}$ ${\displaystyle c\#\cdot k+i}$ ${\displaystyle i,k}$ ${\displaystyle 0\leq i<c\#}$ ${\displaystyle i}$ ${\displaystyle c\#}$ ${\displaystyle 6\#=2\cdot 3\cdot 5=30}$ ${\displaystyle 30k+i}$ ${\displaystyle i,k}$ ${\displaystyle 0\leq i<30}$ ${\displaystyle 0,2,4,\dots ,28}$ ${\displaystyle 0,3,6,\dots ,27}$ ${\displaystyle 0,5,10,\dots ,25}$ ${\displaystyle 30k+i}$ ${\displaystyle i\in \{1,7,11,13,17,19,23,29\}}$ ${\displaystyle c\#\cdot k+i}$ ${\displaystyle i}$ ${\displaystyle c\#}$ ${\displaystyle 19\cdot 23=437=210\cdot 2+17=2\cdot 7\#+17}$ ${\displaystyle 7\#=2\cdot 3\cdot 5\cdot 7}$

A medida que crece, la fracción de restos coprimos a restos disminuye, y por lo tanto el tiempo para realizar la prueba disminuye (aunque todavía es necesario verificar la divisibilidad por todos los primos que son menores que ). Observaciones análogas a las anteriores se pueden aplicar de forma recursiva , dando como resultado la Criba de Eratóstenes . ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle c}$

Una forma de acelerar estos métodos (y todos los demás mencionados a continuación) es calcular previamente y almacenar una lista de todos los primos hasta un cierto límite, como todos los primos hasta 200. (Esta lista se puede calcular con la Criba de Eratóstenes o mediante un algoritmo que prueba cada incremental con todos los primos conocidos ). Luego, antes de probar la primalidad con un método a gran escala, primero se puede verificar la divisibilidad por cualquier primo de la lista. Si es divisible por cualquiera de esos números, entonces es compuesto y se pueden omitir las pruebas posteriores. ${\displaystyle m}$ ${\displaystyle \leq {\sqrt {m}}}$ ${\displaystyle n}$ ${\displaystyle n}$

Una prueba de primalidad simple pero muy ineficiente utiliza el teorema de Wilson , que establece que es primo si y solo si: ${\displaystyle p}$

${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$

Aunque este método requiere multiplicaciones modulares, lo que lo hace poco práctico, los teoremas sobre primos y residuos modulares forman la base de muchos métodos más prácticos. ${\displaystyle p}$

Pruebas heurísticas

Se trata de pruebas que parecen funcionar bien en la práctica, pero que no están probadas y, por lo tanto, técnicamente hablando, no son algoritmos en absoluto. La prueba de Fermat y la prueba de Fibonacci son ejemplos sencillos y son muy eficaces cuando se combinan. John Selfridge ha conjeturado que si p es un número impar y p ≡ ±2 (mod 5), entonces p será primo si se cumplen las dos condiciones siguientes:

• 2 ^{p −1} ≡ 1 (mód p ),
• f _{p +1} ≡ 0 (mód p ),

donde f _k es el k - ésimo número de Fibonacci . La primera condición es la prueba de primalidad de Fermat usando base 2.

En general, si p ≡ a (mod x ² +4), donde a es un residuo cuadrático no nulo (mod x ² +4), entonces p debería ser primo si se cumplen las siguientes condiciones:

• 2 ^{p −1} ≡ 1 (mód p ),
• f ( 1 ) _{p +1} ≡ 0 (mód p ),

f ( x ) _k es el k -ésimo polinomio de Fibonacci en x .

Selfridge, Carl Pomerance y Samuel Wagstaff juntos ofrecen $620 por un contraejemplo. ^[2]

Pruebas probabilísticas

Las pruebas probabilísticas son más rigurosas que las heurísticas en el sentido de que proporcionan límites demostrables sobre la probabilidad de ser engañado por un número compuesto. Muchas pruebas de primalidad populares son pruebas probabilísticas. Estas pruebas utilizan, aparte del número probado n , algunos otros números a que se eligen al azar de algún espacio muestral ; las pruebas de primalidad aleatorias habituales nunca informan un número primo como compuesto, pero es posible que un número compuesto se informe como primo. La probabilidad de error se puede reducir repitiendo la prueba con varios valores de a elegidos independientemente ; para dos pruebas de uso común, para cualquier compuesto n al menos la mitad de los a ' detectan la composición de n ' , por lo que k repeticiones reducen la probabilidad de error a como máximo 2 ^{− k} , que se puede hacer arbitrariamente pequeña aumentando k .

La estructura básica de las pruebas de primalidad aleatorias es la siguiente:

1. Escoge al azar un número a .
2. Comprueba la igualdad (correspondiente a la prueba elegida) entre a y el número dado n . Si la igualdad no es cierta, entonces n es un número compuesto y a es un testigo de la composición, y la prueba se detiene.
3. Regrese al paso uno hasta alcanzar la precisión requerida.

Después de una o más iteraciones, si no se descubre que n es un número compuesto, entonces se puede declarar probablemente primo .

Prueba de primalidad de Fermat

La prueba de primalidad probabilística más simple es la prueba de primalidad de Fermat (en realidad, una prueba de composición). Funciona de la siguiente manera:

Dado un entero n , elija un entero a coprimo con n y calcule un ^{n − 1} módulo n . Si el resultado es distinto de 1, entonces n es compuesto. Si es 1, entonces n puede ser primo.

Si a ^{n −1} (módulo n ) es 1 pero n no es primo, entonces n se llama pseudoprimo a base de a . En la práctica, si a ^{n −1} (módulo n ) es 1, entonces n suele ser primo. Pero aquí hay un contraejemplo: si n = 341 y a = 2, entonces

${\displaystyle 2^{340}\equiv 1{\pmod {341}}}$

aunque 341 = 11·31 es compuesto. De hecho, 341 es el pseudoprimo más pequeño de base 2 (ver Figura 1 de ^[3] ).

Sólo hay 21853 pseudoprimos de base 2 que son menores que 2,5 × 10¹⁰ (ver página 1005 de ^[3] ). Esto significa que, para n hasta 2,5 × 10¹⁰ , si 2 ^{n −1} (módulo n ) es igual a 1, entonces n es primo, a menos que n sea uno de estos 21853 pseudoprimos.

Algunos números compuestos ( números de Carmichael ) tienen la propiedad de que a ^{n − 1} es 1 (módulo n ) para todo a que sea coprimo con n . El ejemplo más pequeño es n = 561 = 3·11·17, para el cual a ⁵⁶⁰ es 1 (módulo 561) para todo a coprimo con 561. Sin embargo, la prueba de Fermat se utiliza a menudo si se necesita una selección rápida de números, por ejemplo en la fase de generación de claves del algoritmo criptográfico de clave pública RSA .

Prueba de primalidad de Miller-Rabin y Solovay-Strassen

La prueba de primalidad de Miller-Rabin y la prueba de primalidad de Solovay-Strassen son variantes más sofisticadas, que detectan todos los compuestos (una vez más, esto significa: para cada número compuesto n , al menos 3/4 (Miller-Rabin) o 1/2 (Solovay-Strassen) de los números a son testigos de la composición de n ). Estas también son pruebas de composición.

La prueba de primalidad de Miller-Rabin funciona de la siguiente manera: dado un entero n , elija un entero positivo a  <  n . Sea 2 ^s d = n  − 1, donde d es impar. Si

${\displaystyle a^{d}\not \equiv \pm 1{\pmod {n}}}$

y

${\displaystyle a^{2^{r}d}\not \equiv -1{\pmod {n}}}$a pesar de ${\displaystyle 0\leq r\leq s-1,}$

entonces n es compuesto y a es un testigo de la composición. De lo contrario, n puede ser primo o no. La prueba de Miller-Rabin es una prueba de primos probables sólida (ver PSW ^[3] página 1004).

La prueba de primalidad de Solovay-Strassen utiliza otra igualdad: Dado un número impar n , elija algún entero a  <  n , si

${\displaystyle a^{(n-1)/2}\not \equiv \left({\frac {a}{n}}\right){\pmod {n}}}$, ¿dónde está el símbolo de Jacobi ? ${\displaystyle \left({\frac {a}{n}}\right)}$

entonces n es compuesto y a es un testigo de la composición. De lo contrario, n puede ser primo o no. La prueba de Solovay-Strassen es una prueba de primos probables de Euler (véase PSW ^[3] página 1003).

Para cada valor individual de a , la prueba de Solovay–Strassen es más débil que la prueba de Miller–Rabin. Por ejemplo, si n = 1905 y a = 2, entonces la prueba de Miller-Rabin muestra que n es compuesto, pero la prueba de Solovay–Strassen no. Esto se debe a que 1905 es un pseudoprimo de Euler de base 2, pero no un pseudoprimo fuerte de base 2 (esto se ilustra en la Figura 1 de PSW ^[3] ).

Prueba de primalidad de Frobenius

Las pruebas de primalidad de Miller-Rabin y de Solovay-Strassen son sencillas y mucho más rápidas que otras pruebas de primalidad generales. Un método para mejorar aún más la eficiencia en algunos casos es la prueba de pseudoprimalidad de Frobenius ; una ronda de esta prueba lleva aproximadamente tres veces más tiempo que una ronda de Miller-Rabin, pero logra un límite de probabilidad comparable a siete rondas de Miller-Rabin.

La prueba de Frobenius es una generalización de la prueba de primos probables de Lucas .

Prueba de primalidad de Baillie-PSW

La prueba de primalidad de Baillie-PSW es ​​una prueba de primalidad probabilística que combina una prueba de Fermat o Miller-Rabin con una prueba de primos probables de Lucas para obtener una prueba de primalidad que no tiene contraejemplos conocidos. Es decir, no hay ningún compuesto n conocido para el cual esta prueba informe que n es probablemente primo. ^{[4] [5]} Se ha demostrado que no hay contraejemplos para n . ${\displaystyle <2^{64}}$

Otras pruebas

Leonard Adleman y Ming-Deh Huang presentaron una variante sin errores (pero con un tiempo polinomial esperado) de la prueba de primalidad de curva elíptica . A diferencia de otras pruebas probabilísticas, este algoritmo produce un certificado de primalidad y, por lo tanto, se puede utilizar para demostrar que un número es primo. ^[6] El algoritmo es prohibitivamente lento en la práctica.

Si existieran ordenadores cuánticos , la primalidad podría comprobarse de forma asintótica más rápida que utilizando ordenadores clásicos. Una combinación del algoritmo de Shor , un método de factorización de números enteros, con la prueba de primalidad de Pocklington podría resolver el problema en . ^[7] ${\displaystyle O((\log n)^{3}(\log \log n)^{2}\log \log \log n)}$

Pruebas deterministas rápidas

A principios del siglo XX se demostró que se podía utilizar un corolario del pequeño teorema de Fermat para comprobar la primalidad. ^[8] Esto dio lugar a la prueba de primalidad de Pocklington . ^[9] Sin embargo, como esta prueba requiere una factorización parcial de n  − 1, el tiempo de ejecución seguía siendo bastante lento en el peor de los casos. La primera prueba de primalidad determinista significativamente más rápida que los métodos ingenuos fue la prueba de ciclotomía ; se puede demostrar que su tiempo de ejecución es O ((log  n ) ^{c  log log log  n} ), donde n es el número para comprobar la primalidad y c es una constante independiente de n . Se realizaron muchas mejoras adicionales, pero no se pudo demostrar que ninguna tuviera un tiempo de ejecución polinomial. (El tiempo de ejecución se mide en términos del tamaño de la entrada, que en este caso es ~ log  n , que es el número de bits necesarios para representar el número n .) Se puede demostrar que la prueba de primalidad de la curva elíptica se ejecuta en O((log  n ) ⁶ ), si algunas conjeturas sobre la teoría analítica de números son verdaderas. ^{[ ¿cuáles? ]} De manera similar, bajo la hipótesis generalizada de Riemann , se puede demostrar que la prueba determinista de Miller , que forma la base de la prueba probabilística de Miller-Rabin, se ejecuta en Õ ((log  n ) ⁴ ). ^[10] En la práctica, este algoritmo es más lento que los otros dos para tamaños de números con los que se puede trabajar. Debido a que la implementación de estos dos métodos es bastante difícil y crea un riesgo de errores de programación, a menudo se prefieren pruebas más lentas pero más simples.

En 2002, Manindra Agrawal , Neeraj Kayal y Nitin Saxena inventaron la primera prueba polinómica determinista incondicional demostrable para la primalidad . La prueba de primalidad AKS se ejecuta en Õ((log  n ) ¹² ) (mejorada a Õ((log  n ) ^7,5 ) ^[11] en la revisión publicada de su artículo), que puede reducirse aún más a Õ((log  n ) ⁶ ) si la conjetura de Sophie Germain es verdadera. ^[12] Posteriormente, Lenstra y Pomerance presentaron una versión de la prueba que se ejecuta en un tiempo Õ((log  n ) ⁶ ) incondicionalmente. ^[13]

Agrawal, Kayal y Saxena sugieren una variante de su algoritmo que funcionaría en Õ((log  n ) ³ ) si la conjetura de Agrawal es verdadera; sin embargo, un argumento heurístico de Hendrik Lenstra y Carl Pomerance sugiere que probablemente sea falsa. ^[11] Una versión modificada de la conjetura de Agrawal, la conjetura de Agrawal-Popovych, ^[14] todavía puede ser verdadera.

Complejidad

En la teoría de la complejidad computacional , el lenguaje formal correspondiente a los números primos se denota como PRIMES. Es fácil demostrar que PRIMES está en Co-NP : su complemento COMPOSITES está en NP porque uno puede decidir la composición adivinando de manera no determinista un factor.

En 1975, Vaughan Pratt demostró que existía un certificado de primalidad que se podía comprobar en tiempo polinomial y, por lo tanto, que PRIMES estaba en NP y, por lo tanto, en ⁠ ⁠ ${\displaystyle {\mathsf {NP\cap coNP}}}$ . Véase el certificado de primalidad para más detalles.

El descubrimiento posterior de los algoritmos Solovay–Strassen y Miller–Rabin puso a PRIMES en coRP . En 1992, el algoritmo Adleman–Huang ^[6] redujo la complejidad a ⁠ ⁠ ${\displaystyle {\mathsf {{\color {Blue}ZPP}=RP\cap coRP}}}$ , lo que sustituyó al resultado de Pratt.

La prueba de primalidad de Adleman-Pomerance-Rumely de 1983 puso a PRIMES en QP ( tiempo cuasi-polinomial ), que no se sabe que sea comparable con las clases mencionadas anteriormente.

Debido a su manejabilidad en la práctica, los algoritmos de tiempo polinomial que asumen la hipótesis de Riemann y otras evidencias similares, se sospechó durante mucho tiempo, pero no se demostró, que la primalidad podía resolverse en tiempo polinomial. La existencia de la prueba de primalidad AKS finalmente resolvió esta pregunta de larga data y colocó a PRIMES en P . Sin embargo, no se sabe que PRIMES sea P-completo , y no se sabe si se encuentra en clases que se encuentran dentro de P, como NC o L . Se sabe que PRIMES no está en AC 0 . ^[15]

Métodos de teoría de números

Existen ciertos métodos de teoría de números para comprobar si un número es primo, como la prueba de Lucas y la prueba de Proth . Estas pruebas suelen requerir la factorización de n  + 1, n − 1 o una cantidad similar, lo que significa que no son útiles para pruebas de primalidad de propósito general, pero suelen ser bastante potentes cuando se sabe que el número n probado tiene una forma especial.

La prueba de Lucas se basa en el hecho de que el orden multiplicativo de un número a módulo n es n − 1 para un número primo n cuando a es una raíz primitiva módulo n . Si podemos demostrar que a es primitivo para n , podemos demostrar que n es primo.

Referencias

1. Riesel (1994) págs. 2-3
2. John Selfridge#La conjetura de Selfridge sobre las pruebas de primalidad .
3. Pomerance, Carl ; Selfridge, John L. ; Wagstaff, Samuel S. Jr. (julio de 1980). "Los pseudoprimos hasta 25·109" (PDF) . Matemáticas de la computación . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 .
4. Baillie, Robert; Wagstaff, Samuel S. 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 . MR  0583518.
5. Baillie, Robert; Fiori, Andrew; Wagstaff, Samuel S. Jr. (julio de 2021). "Fortalecimiento de la prueba de primalidad Baillie-PSW". Matemáticas de la computación . 90 (330): 1931–1955. arXiv : 2006.14425 . doi :10.1090/mcom/3616. S2CID  220055722.
6. Adleman, Leonard M. ; Huang, Ming-Deh (1992). Pruebas de primalidad y variedades abelianas sobre cuerpos finitos . Apuntes de clase sobre matemáticas. Vol. 1512. Springer-Verlag . ISBN 3-540-55308-8.
7. Chau, HF; Lo, H.-K. (1995). "Prueba de primalidad mediante factorización cuántica". arXiv : quant-ph/9508005 .
8. Pocklington, HC (1914). "La determinación de la naturaleza primo o compuesta de los grandes números mediante el teorema de Fermat". Cambr. Phil. Soc. Proc . 18 : 29–30. JFM  45.1250.02.
9. Weisstein, Eric W. "Teorema de Pocklington". MathWorld .
10. Gary L. Miller (1976). "Hipótesis de Riemann y pruebas de primalidad". Revista de Ciencias de la Computación y de Sistemas . 13 (3): 300–317. doi : 10.1016/S0022-0000(76)80043-8 .
11. Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "Los números primos están en P" (PDF) . Anales de Matemáticas . 160 (2): 781–793. doi : 10.4007/anales.2004.160.781 .
12. Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES está en P" (PDF) . Anales de Matemáticas . 160 (2): 781–793. doi : 10.4007/anales.2004.160.781 .
13. Carl Pomerance y Hendrik W. Lenstra (20 de julio de 2005). "Prueba de primalidad con períodos gaussianos" (PDF) .
14. Popovych, Roman (30 de diciembre de 2008). "Una nota sobre la conjetura de Agrawal" (PDF) .
15. Allender, Eric; Saks, Michael; Shparlinski, Igor (2001). "Un límite inferior para la primalidad". Revista de Ciencias de la Computación y de Sistemas . 62 (2): 356–366. doi :10.1006/jcss.2000.1725.

Fuentes

• Crandall, Richard ; Pomerance, Carl (2005). Números primos: una perspectiva computacional (2.ª ed.). Springer. ISBN 0-387-25282-7.Capítulo 3: Reconocimiento de primos y compuestos, págs. 109-158. Capítulo 4: Demostración de primalidad, págs. 159-190. Sección 7.6: Demostración de primalidad de curva elíptica (ECPP), págs. 334-340.
• Knuth, Donald (1997). "Sección 4.5.4". El arte de la programación informática . Vol. 2: Algoritmos seminuméricos (3.ª ed.). Addison–Wesley. págs. 391–396. ISBN 0-201-89684-2.
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "Sección 31.8: Pruebas de primalidad". Introducción a los algoritmos (segunda edición). MIT Press, McGraw–Hill. págs. 887–896. ISBN 0-262-03293-7.
• Papadimitriou, Christos H. (1993). "Sección 10.2: Primalidad". Complejidad computacional (1.ª ed.). Addison Wesley. pp. 222–227. ISBN 0-201-53082-1.Zbl 0833.68049  .
• Riesel, Hans (1994). Números primos y métodos informáticos para la factorización . Progreso en matemáticas. Vol. 126 (segunda edición). Boston, Massachusetts: Birkhäuser. ISBN 0-8176-3743-5.Zbl 0821.11001  .

Enlaces externos

• Solovay-Strassen (computacion.cs.cinvestav.mx) en archive.today (archivado 2012-12-20) – Implementación de la prueba de primalidad de Solovay-Strassen en Maple
• Distinguir números primos de números compuestos, por DJ Bernstein (cr.yp.to)
• Las páginas principales (primes.utm.edu)
• Prueba de primalidad de Lucas con factor N − 1 (MathPages.com) en los Archivos web de la Biblioteca del Congreso (archivado el 6 de agosto de 2010)
• PRIMABOINCA es un proyecto de investigación que utiliza ordenadores conectados a Internet para buscar un contraejemplo a algunas conjeturas. La primera conjetura ( la conjetura de Agrawal ) fue la base para la formulación del primer algoritmo determinista de prueba de primos en tiempo polinomial ( algoritmo AKS ).