Test de primalidad de Baillie-PSW , la enciclopedia libre
El test de primalidad de Baillie-PSW es una prueba que emplea un algoritmo probabilístico que determina si un número es compuesto o probable primo. Lleva el nombre de Robert Baillie, Carl Pomerance, John Selfridge y Samuel S. Wagstaff, Jr..
Es una combinación de una prueba de probable primo de Fermat fuerte de base 2 y una prueba de probable primo de Lucas fuerte.
Propiedades
[editar]Las pruebas de Fermat y de Lucas tienen cada una su propia lista de pseudoprimos, es decir, números compuestos que pasan la prueba. Por ejemplo, los primeros diez pseudoprimos fuertes en base 2 son
y los primeros diez pseudoprimos fuertes de Lucas (con parámetros de Lucas ("P", "Q") definidos por el Método A de Selfridge) son
No existe una superposición conocida entre estas listas de pseudoprimos fuertes de Fermat y de pseudoprimos fuertes de Lucas, e incluso hay evidencia de que los números en estas listas tienden a ser diferentes tipos de números. Por ejemplo, los pseudoprimos de Fermat en base 2 tienden a caer en la clase de residuo 1 (mod m) para muchas m pequeñas, mientras que los pseudoprimos de Lucas tienden a caer en la clase de residuo −1 (mod m'').[1]: §6 [2]: Table 2 & §5 Como resultado, es muy probable que un número que pase una prueba fuerte de Fermat y una fuerte de Lucas sea primo.
Ningún número compuesto por debajo de 264 (aproximadamente 1845·1019) pasa la prueba de Baillie-PSW.[3] En consecuencia, esta prueba es una prueba de primalidad determinista en números por debajo de ese límite. Tampoco hay números compuestos conocidos por encima de ese límite que pasen la prueba, en otras palabras, no hay pseudoprimos Baillie-PSW conocidos. A pesar de esto, se conjetura que hay infinitamente muchos.
En 1980, los autores Pomerance, Selfridge y Wagstaff ofrecieron 30 dólares por el descubrimiento de un contraejemplo, es decir, un número compuesto que pasara esta prueba. Richard Guy declaró incorrectamente que el valor de este premio se había elevado a 620 dólares, pero estaba confundiendo la sucesión de Lucas con la sucesión de Fibonacci, y sus comentarios en realidad solo se aplican a la conjetura de Selfridge.[4] En junio de 2014, el premio seguía sin reclamar. Sin embargo, un argumento heurístico de Pomerance sugiere que hay infinitos contraejemplos.[5]
Además, Chen y Greene[6][7] han construido un conjunto S de 1248 primos tales que, entre los casi 21248 productos de distintos primos en S, puede haber alrededor de 740 contraejemplos. Sin embargo, están hablando de la prueba de PSW más débil que sustituye una prueba de Fibonacci por la de Lucas.
La prueba
[editar]Sea n el entero positivo impar cuya primalidad se desea probar:
- Opcionalmente, realícese una división por tentativa para verificar si n es divisible por un número primo pequeño menor que algún límite conveniente.
- Realícese una prueba sobre si es un probable primo fuerte de base 2. Si n no es un probable primo fuerte de base 2, entonces n es compuesto; abandonar.
- Encontrar la primera D en la secuencia 5, −7, 9, −11, 13, −15, ... para la que el símbolo de Jacobi (D/n) es −1 . Establecer P = 1 y Q = (1 − D) / 4.
- Realizar una prueba sobre si es un probable primo de Lucas fuerte en n utilizando los parámetros D, P y Q. Si n no es un probable primo de Lucas fuerte, entonces n es compuesto. De lo contrario, n es casi seguro un número primo.
Comentarios:
- El primer paso es solo por eficiencia. La prueba de Baillie-PSW funciona sin este paso, pero si n tiene factores primos pequeños, entonces la forma más rápida de demostrar que n es compuesto es encontrar un factor por división de prueba.
- El paso 2 es, en efecto, una sola aplicación del test de primalidad de Miller-Rabin, pero usando la base 2 fija. No hay nada especial en usar la base 2; otras bases podrían funcionar igual de bien. Sin embargo, se ha trabajado mucho (véase arriba) para verificar que la combinación de la prueba de primos probables fuertes de base 2 y una prueba de Lucas fuerte hace un buen trabajo al distinguir los números primos de los compuestos.
- Baillie y Wagstaff demostraron en el Teorema 9, en la página 1413 de[2], que el número promedio de valores de D que deben probarse es aproximadamente 3.147755149.
- Si n es un cuadrado perfecto, entonces el paso 3 nunca producirá una D con (D/n) = −1; esto no es un problema porque los cuadrados perfectos son fáciles de detectar usando método de Newton para raíces cuadradas. Si el paso 3 no produce una D rápidamente, se debe verificar si n es un cuadrado perfecto.
- Dado n, existen otros métodos para elegir D, P y Q. [2]: 1401, 1409 Lo importante es que el símbolo de Jacobi (D/n) sea −1. Bressoud y Wagon explican por qué se requiere que el símbolo de Jacobi sea −1, así como por qué se obtienen pruebas de primalidad más poderosas si Q ≠ ±1.[8]: 266–269
- La Sección 6 de[2] recomienda que si Q ≠ ±1, una buena prueba de primalidad también debe verificar dos condiciones de congruencia adicionales. Estas dos congruencias casi no implican ningún costo computacional adicional y rara vez son verdaderas si n es compuesto: y .
- Hay versiones más débiles de la prueba de Baillie-PSW, y esta a veces se conoce como la prueba de Baillie-PSW fuerte.
- Si la prueba de Lucas se reemplaza por una prueba de Fibonacci, entonces no debería llamarse prueba de Baillie-PSW, sino prueba de Selfridge o prueba de PSW. Véase Conjetura de Selfridge sobre tests de primalidad.
- Pomerance, Selfridge y Wagstaff ofrecieron 30 dólares en 1980 por encontrar un número compuesto que superase una versión más débil de la prueba Baillie-PSW. Está pendiente de encontrar un número que pase la prueba fuerte de Baillie-PSW.[1]
- Con un método apropiado para elegir D, P y Q, solo hay cinco números compuestos impares menores que 1015 para los cuales .[9] Los autores de[9] sugieren una versión más sólida de la prueba de primalidad de Baillie-PSW que incluye esta congruencia; y ofrecen una gratificación de 2000 dólares por un número compuesto que pase esta prueba más fuerte.
El peligro de confiar solo en las pruebas de Fermat
[editar]Existe una superposición significativa entre las listas de pseudoprimos para diferentes bases.
Elíjase una base a. Si n es un pseudoprimo respecto a la base a, entonces es probable que n sea uno de esos pocos números que es un pseudoprimo de muchas bases.[10]
Por ejemplo, n = 341 es un pseudoprimo de base 2. Del Teorema 1 de la página 1392 de[2] se deduce que hay 100 valores de a (mod 341) para los cuales 341 es un pseudoprimo de base a (los primeros diez de estos a son 1, 2, 4, 8, 15, 16, 23, 27, 29 y 30). La proporción de tales a en comparación con n suele ser mucho menor.
Por lo tanto, si n es un pseudoprimo respecto a la base a, entonces es más probable que n sea un pseudoprimo de alguna otra base. [1]: 1020 Por ejemplo, hay 21853 pseudoprimos en base 2 hasta 25·109. Esto es solo alrededor de dos de cada millón de números enteros impares en este rango. Sin embargo:[1]: 1021
- 4709 de estos 21853 números (más del 21 por ciento) también son pseudoprimos en base 3;
- 2522 de estos 4709 números (más del 53 por ciento) son pseudoprimos en bases 2, 3 y 5;
- 1770 de "estos" 2522 números (más del 70 por ciento) son pseudoprimos en las bases 2, 3, 5 y 7.
- 29341 es el pseudoprimo más pequeño en las bases 2 a 12.
Todo esto sugiere que las pruebas de primos probables a diferentes bases no son independientes entre sí, por lo que realizar pruebas de primos probables de Fermat a más y más bases dará rendimientos decrecientes.
Por otro lado, los cálculos en [2]: 1400 y los cálculos hasta 264 mencionados anteriormente sugieren que las pruebas de primos probables de Fermat y Lucas son independientes, por lo que una combinación de estos tipos de pruebas proporciona una prueba de primalidad muy potente, especialmente si se utilizan las formas fuertes de las dos pruebas.
Téngase en cuenta que un número que es pseudoprimo para todas las bases primas 2, ..., p también es pseudoprimo para todas las bases que son p-lisos.
También hay superposición entre pseudoprimos fuertes con diferentes bases. Por ejemplo, 1373653 es el pseudoprimo fuerte más pequeño para las bases 2 a 4, y 3215031751 es el pseudoprimo fuerte más pequeño para las bases 2 a 10.
Arnault[11] obtuvo un número de Carmichael N de 397 dígitos que es un pseudoprimo fuerte para todas las bases primas menores que 307. Debido a que esta N es un número de Carmichael, N es también un pseudoprimo (no necesariamente fuerte) para todas las bases menores que p, donde p es el factor primo más pequeño de 131 dígitos de N. Un cálculo rápido muestra que N no es un primo probable de Lucas cuando D, P y Q se eligen mediante el método descrito anteriormente, por lo que este número sería correctamente determinado por la prueba de Baillie-PSW como compuesto.
Aplicaciones de las pruebas combinadas de primalidad de Fermat y Lucas
[editar]Los siguientes sistemas de álgebra computacional y paquetes de software utilizan alguna versión de la prueba de primalidad de Baillie-PSW:
- Función isprime de Maple,[12]
- Función PrimeQ de Mathematica,[13]
- Funciones isprime y ispseudoprime de PARI/GP,[14] y la función SageMath is_pseudoprime de[15] todos usan una combinación de una prueba de primos probables fuertes de Fermat y una prueba de Lucas.
- La función primep de Maxima usa una prueba de este tipo para números mayores que 341550071728321.[16]
- La biblioteca FLINT tiene funciones n_is_probabprime y n_is_probabprime_BPSW que utilizan una prueba combinada, así como otras funciones que realizan las pruebas de Fermat y Lucas por separado.[17]
- La clase BigInteger en versiones estándar de Java y en implementaciones de código abierto como OpenJDK tiene un método llamado isProbablePrime. Este método realiza una o más pruebas de Miller-Rabin con bases aleatorias. Si n, el número que se está probando, tiene 100 bits o más, este método también realiza una prueba de Lucas no fuerte que verifica si Un+1 es 0 (mod n).[18][19] El uso de bases aleatorias en las pruebas de Miller-Rabin tiene una ventaja y un inconveniente en comparación con hacer una sola prueba de base 2 como se especifica en la prueba de Baillie-PSW. La ventaja es que, con bases aleatorias, se puede obtener un límite en la probabilidad de que n sea compuesto. El inconveniente es que, a diferencia de la prueba de Baillie-PSW, no se puede decir con certeza que si n es menor que un límite fijo como 264, entonces n es primo.
- En Perl, los módulos Math::Primality[20] y Math::Prime::Util[21][22] tienen funciones para realizar la prueba fuerte de Baillie–PSW, así como funciones separadas para pruebas fuertes de pseudoprimo y fuertes pruebas de Lucas.
- En Python, la biblioteca NZMATH[23] tiene las pruebas fuertes de pseudoprimo y Lucas, pero no tiene una función combinada. La biblioteca SymPy[24] si dispone de ambas.
- A partir de la versión 6.2.0, la función mpz_probab_prime_p de GNU Multiple Precision Arithmetic Library usa una fuerte prueba de Lucas y una prueba de Miller-Rabin; las versiones anteriores no hacían uso de Baillie-PSW.[25]
- Las funciones IsProbablePrime y IsProbablyPrime de Magma usan 20 pruebas de Miller-Rabin para números > 34·1013, pero no las combinan con una prueba de números primos probables de Lucas.[26]
Las bibliotecas criptográficas a menudo tienen funciones de prueba principales. Albrecht et al. analizaron las pruebas utilizadas en estas bibliotecas. Algunas emplean una prueba combinada de Fermat y Lucas; aunque otras no.[27]: Table 1 Para algunas de estas últimas, pudieron construir números compuestos que las bibliotecas declararon primos.
Referencias
[editar]- ↑ a b c d Pomerance, Carl; Selfridge, John L.; Wagstaff, Samuel S. Jr. (July 1980). «The pseudoprimes to 25·109». Mathematics of Computation 35 (151): 1003-1026. JSTOR 2006210. doi:10.1090/S0025-5718-1980-0572872-7.
- ↑ a b c d e f Baillie, Robert; Wagstaff, Samuel S. Jr. (October 1980). «Lucas Pseudoprimes». Mathematics of Computation 35 (152): 1391-1417. JSTOR 2006406. MR 583518. doi:10.1090/S0025-5718-1980-0583518-6.
- ↑ Nicely, Thomas R. (2012-01-13 (1ª Ed. 2005-06-10)). «The Baillie–PSW Primality Test». trnicely.net. Archivado desde el original el 21 de noviembre de 2019. Consultado el 17 de marzo de 2013.
- ↑ Guy, R. (1994). "Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes." §A12 in Unsolved Problems in Number Theory. 2nd ed., p. 28, New York: Springer-Verlag. ISBN 0-387-20860-7.
- ↑ Pomerance, C. (1984). «Are There Counterexamples to the Baillie–PSW Primality Test?».
- ↑ Greene, John R. (n.d.). «Baillie–PSW». University of Minnesota Duluth. Consultado el 29 de mayo de 2020.
- ↑ Chen, Zhuo; Greene, John (August 2003). «Some Comments on Baillie–PSW Pseudoprimes». The Fibonacci Quarterly 41 (4): 334-344.
- ↑ Bressoud, David; Wagon, Stan (2000). A Course in Computational Number Theory. New York: Key College Publishing in cooperation with Springer. ISBN 978-1-930190-10-8. (requiere registro).
- ↑ a b Robert Baillie; Andrew Fiori; Samuel S. Wagstaff, Jr. (July 2021). «Strengthening the Baillie-PSW Primality Test». Mathematics of Computation 90 (330): 1931-1955. doi:10.1090/mcom/3616. «eprint: 2006.14425».
- ↑ Wagstaff, Samuel S. Jr. (1982). «Pseudoprimes and a generalization of Artin's conjecture». Acta Arithmetica 41 (2): 141-150. doi:10.4064/aa-41-2-141-150.
- ↑ Arnault, F. (August 1995). «Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases». Journal of Symbolic Computation 20 (2): 151-161. doi:10.1006/jsco.1995.1042.
- ↑ isprime - Maple Help, documentation at maplesoft.com.
- ↑ Wolfram Language & System Documentation Center - Some Notes on Internal Implementation documentation at wolfram.com.
- ↑ User's Guide to PARI/GP (version 2.11.1) documentation for PARI/GP.
- ↑ SageMath Documentation documentation for SageMath.
- ↑ Maxima Manual Archivado el 9 de julio de 2014 en Wayback Machine. documentation for Maxima.
- ↑ FLINT: Fast Library for Number Theory documentation for FLINT 2.5.
- ↑ BigInteger.java Archivado el 8 de diciembre de 2015 en Wayback Machine. DocJar: Search Open Source Java API.
- ↑ BigInteger.java documentation for OpenJDK.
- ↑ Math::Primality Perl module with BPSW test
- ↑ Math::Prime::Util Perl module with primality tests including BPSW
- ↑ Math::Prime::Util::GMP Perl module with primality tests including BPSW, using C+GMP
- ↑ NZMATH Archivado el 17 de enero de 2013 en Wayback Machine. number theory calculation system in Python
- ↑ «SymPy». SymPy - A Python library for symbolic mathematics.
- ↑ GNU MP 6.2.0 Prime Testing Algorithm documentation for GMPLIB.
- ↑ Magma Computational Algebra System - Primes and Primality Testing documentation for Magma.
- ↑ Albrecht, Martin R.; Massimo, Jake; Paterson, Kenneth G.; Somorovsky, Juraj (15 de octubre de 2018). Prime and Prejudice: Primality Testing Under Adversarial Conditions. ACM SIGSAC Conference on Computer and Communications Security 2018. Toronto: Association for Computing Machinery. pp. 281-298. doi:10.1145/3243734.3243787.
Lecturas relacionadas
[editar]- Jacobsen, Dana Pseudoprime Statistics, Tables, and Data (lists of pseudoprimes base 2, Lucas, and other pseudoprimes to 1014)
- Nicely, Thomas R., The Baillie–PSW primality test., archivado desde el original el 28 de agosto de 2013, consultado el 7 de agosto de 2007.
- Weisstein, Eric W. «Baillie–PSW Primality Test». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.