La prueba de primalidad de Baillie-PSW es un algoritmo de prueba de primalidad probabilística que determina si un número es compuesto o probable primo . Lleva el nombre de Robert Baillie, Carl Pomerance , John Selfridge y Samuel Wagstaff .
La prueba de Baillie-PSW es una combinación de una fuerte prueba de prima probable de Fermat en base 2 y una fuerte prueba de prima probable de Lucas . Las pruebas de Fermat y 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 a base 2 son
Los primeros diez pseudoprimos fuertes de Lucas (con parámetros de Lucas ( P , Q ) definidos por el Método A de Selfridge) son
- 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309 y 58519 (secuencia A217255 en la OEIS ).
No existe una superposición conocida entre estas listas de pseudoprimas fuertes de Fermat y pseudoprimas 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 a base 2 tienden a caer en la clase de residuo 1 (mod m ) para muchos m pequeños , mientras que los pseudoprimes de Lucas tienden a caer en la clase de residuo -1 (mod m ). [1] : §6 [2] : Tabla 2 y §5 Como resultado, es muy probable que un número que pase tanto una prueba de Fermat fuerte como una prueba de Lucas fuerte sea primo.
Ningún número compuesto por debajo de 2 64 (aproximadamente 1.845 · 10 19 ) pasa la prueba 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 pseudoprimes conocidos de Baillie-PSW. A pesar de esto, se conjetura que son infinitos.
En 1980, los autores Pomerance, Selfridge y Wagstaff ofrecieron $ 30 por el descubrimiento de un contraejemplo, es decir, un número compuesto que pasó esta prueba. Richard Guy declaró incorrectamente que el valor de este premio se había elevado a $ 620, pero estaba confundiendo la secuencia de Lucas con la secuencia de Fibonacci , y sus comentarios realmente se aplican solo a una conjetura de Selfridge . [4] En junio de 2014, el premio sigue sin ser reclamado. 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 números primos de modo que, entre los casi 2 1248 productos de distintos números primos en S , puede haber alrededor de 740 contraejemplos. Sin embargo, están hablando de la prueba PSW más débil que sustituye una prueba de Fibonacci por la de Lucas.
La prueba
Sea n el entero positivo impar que deseamos probar para determinar su primalidad.
- Opcionalmente, realice una división de prueba para verificar si n es divisible por un número primo pequeño menor que algún límite conveniente.
- Realice una prueba de cebado probable fuerte en base 2 . Si n no es una base principal 2 probable fuerte, entonces n es compuesta; dejar.
- Encuentre la primera D en la secuencia 5, −7, 9, −11, 13, −15, ... para la cual el símbolo de Jacobi ( D / n ) es −1. Establezca P = 1 y Q = (1 - D ) / 4.
- Realizar una fuerte probable primo Lucas prueba en n utilizando parámetros D , P y Q . Si n no es un número primo probable de Lucas fuerte, entonces n es compuesto. De lo contrario, es casi seguro que n sea primo.
Observaciones.
- El primer paso es solo por eficiencia. La prueba de Baillie-PSW funciona sin este paso, pero si n tiene factores primos pequeños, 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 de la prueba de primalidad de Miller-Rabin , pero usando la base fija 2. No hay nada especial en usar la base 2; otras bases podrían funcionar igual de bien. Sin embargo, se ha trabajado mucho (ver arriba) para verificar que la combinación de la prueba de cebado probable fuerte de base 2 y una prueba de Lucas fuerte hace un buen trabajo para distinguir los primos de los compuestos.
- Baillie y Wagstaff demostraron en el Teorema 9 de la página 1413 de [2] que el número promedio de D s que deben probarse es de 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 el 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.
- Dada n , hay 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é queremos que el símbolo de Jacobi sea −1, así como por qué se obtienen pruebas de primordialidad 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 debería verificar dos condiciones de congruencia adicionales. Estas dos congruencias casi no implican un costo computacional adicional, y rara vez son verdaderas si n es compuesto: y .
- Hay versiones más débiles de la prueba Baillie-PSW, y esta a veces se denomina prueba Strong Baillie-PSW.
- Si la prueba de Lucas se reemplaza por una prueba de Fibonacci, entonces no debería llamarse prueba de Baillie-PSW, sino más bien una prueba de Selfridge o una prueba de PSW. Véase la conjetura de Selfridge sobre las pruebas de primalidad .
- Pomerance, Selfridge y Wagstaff ofrecieron $ 30 en 1980 por un número compuesto que pasara una versión más débil de la prueba Baillie-PSW. Un número así que pasa la prueba (fuerte) Baillie-PSW calificaría. [1]
- Con un método apropiado para elegir D , P y Q , solo hay cinco números compuestos impares menores que 10 15 para los cuales. [9] Los autores de [9] sugieren una versión más sólida de la prueba de primalidad Baillie-PSW que incluye esta congruencia; los autores ofrecen una recompensa de $ 2000 por un número compuesto que pase esta prueba más sólida.
El peligro de confiar solo en las pruebas de Fermat
Existe una superposición significativa entre las listas de pseudoprimes a diferentes bases.
Elija una base a . Si n es un pseudoprime para la base a , entonces es probable que n sea uno de esos pocos números que es un pseudoprime para muchas bases. [10]
Por ejemplo, n = 341 es un pseudoprime a base 2. Se sigue del Teorema 1 en la página 1392 de [2] que hay 100 valores de a (mod 341) para los cuales 341 es un pseudoprime base a . (El primero diez de tales una son 1, 2, 4, 8, 15, 16, 23, 27, 29, y 30). La proporción de tal en comparación con n suele ser mucho menor.
Por lo tanto, si n es un pseudoprime para la base a , entonces n es más probable que el promedio para ser un pseudoprime para alguna otra base. [1] : 1020 Por ejemplo, hay 21853 pseudoprimes en base 2 hasta 25 · 10 9 . Esto es solo alrededor de dos de cada millón de enteros impares en este rango. Sin embargo: [1] : 1021
- 4709 de estos 21853 números (más del 21 por ciento) también son pseudoprimes a la base 3;
- 2522 de estos 4709 números (más del 53 por ciento) son pseudoprimos de las bases 2, 3 y 5;
- 1770 de estos 2522 números (más del 70 por ciento) son pseudoprimos de las bases 2, 3, 5 y 7.
29341 es el pseudoprime más pequeño para las bases 2 a 12. Todo esto sugiere que las pruebas de primos probables para diferentes bases no son independientes entre sí, por lo que la realización de pruebas de primos probables de Fermat para cada vez más bases dará rendimientos decrecientes. Por otro lado, los cálculos en [2] : 1400 y los cálculos hasta 2 64 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 sería una prueba de primalidad poderosa, especialmente si se utilizan las formas fuertes de las pruebas.
Tenga en cuenta que un número que es pseudoprime para todas las bases primas 2, ..., p también es pseudoprime para todas las bases que son p-suaves .
También hay superposición entre pseudoprimos fuertes a diferentes bases. Por ejemplo, 1373653 es el pseudoprime fuerte más pequeño a las bases 2 a 4, y 3215031751 es el pseudoprime fuerte más pequeño a las bases 2 a 10. Arnault [11] da un número N de Carmichael de 397 dígitos que es un pseudoprime fuerte a todas las bases primas menos de 307. Debido a que este N es un número Carmichael, N es también una (no necesariamente fuerte) pseudoprime a todas las bases de menos de p , donde p es el 131 dígitos factor primo más pequeño de N . Un cálculo rápido muestra que N no es un número primo probable de Lucas cuando D , P y Q se eligen mediante el método descrito anteriormente, por lo que este número se determinaría correctamente mediante la prueba de Baillie-PSW como compuesto.
Aplicaciones de las pruebas de primalidad combinadas de Fermat y Lucas
Los siguientes sistemas informáticos de álgebra y paquetes de software utilizan alguna versión de la prueba de primalidad Baillie – PSW.
Arce 's ISPrime función, [12] Mathematica ' s PrimeQ función, [13] PARI / GP 's ISPrime y ispseudoprime funciones, [14] y SageMath ' s is_pseudoprime función [15] todo el uso de una combinación de un Fermat fuerte probable primo prueba y una prueba de Lucas. La función primep de Maxima usa dicha prueba para números mayores que 341550071728321. [dieciséis]
La biblioteca FLINT tiene funciones n_is_probabprime y n_is_probabprime_BPSW que usan una prueba combinada, así como otras funciones que realizan 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 U n + 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 prueba de base 2 única 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 2 64 , 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 Baillie-PSW así como funciones separadas para pruebas pseudoprime y Lucas fuertes. En Python , la biblioteca NZMATH [23] tiene las pruebas de pseudoprime y Lucas fuertes, pero no tiene una función combinada. La biblioteca SymPy [24] implementa esto.
A partir de 6.2.0, GNU múltiple de precisión aritmética Biblioteca 's mpz_probab_prime_p función utiliza una fuerte prueba de Lucas y una prueba de Miller-Rabin; las versiones anteriores no hacían uso de Baillie – PSW. [25] Magma 's IsProbablePrime y IsProbablyPrime funciones utilizan 20 pruebas Miller-Rabin para los números de> 34 · 10 13 , pero no se combinan con una prueba probable primo Lucas. [26]
Las bibliotecas criptográficas a menudo tienen funciones de prueba principales. Albrecht y col. discutir las pruebas utilizadas en estas bibliotecas. Algunos utilizan una prueba combinada de Fermat y Lucas; muchos no lo hacen. [27] : Tabla 1 Para algunos de estos últimos, Albrecht, et al. fueron capaces de construir números compuestos que las bibliotecas declararon primos.
Referencias
- ^ a b c d Pomerance, Carl ; Selfridge, John L .; Wagstaff, Samuel S. 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 . JSTOR 2006210 .
- ^ a b c d e f 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 . JSTOR 2006406 . Señor 0583518 .
- ^ Muy bien, Thomas R. (13 de enero de 2012) [Publicado por primera vez el 10 de junio de 2005]. "La prueba de primordialidad de Baillie-PSW" . 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 en Problemas no resueltos en teoría de números . 2ª ed., Pág. 28, Nueva York: Springer-Verlag. ISBN 0-387-20860-7 .
- ^ Pomerance, C. (1984). "¿Hay contraejemplos de la prueba de primordialidad de Baillie-PSW?" (PDF) .
- ^ Greene, John R. (sin fecha). "Baillie – PSW" . Universidad de Minnesota Duluth . Consultado el 29 de mayo de 2020 .
- ^ Chen, Zhuo; Greene, John (agosto de 2003). "Algunos comentarios sobre los pseudoprimes de Baillie – PSW" (PDF) . El Fibonacci Quarterly . 41 (4): 334–344.
- ^ Bressoud, David ; Vagón, Stan (2000). Un curso de teoría de números computacionales . Nueva York: Key College Publishing en cooperación con Springer. ISBN 978-1-930190-10-8.
- ^ a b Robert Baillie; Andrew Fiori; Samuel S. Wagstaff, Jr. (julio de 2021). "Fortalecimiento de la prueba de primordialidad Baillie-PSW". Matemáticas de la Computación . 90 (330): 1931-1955. arXiv : 2006.14425 . doi : 10.1090 / mcom / 3616 .
- ^ Wagstaff, Samuel S. Jr. (1982). "Pseudoprimes y una generalización de la conjetura de Artin" . Acta Arithmetica . 41 (2): 141–150. doi : 10.4064 / aa-41-2-141-150 .
- ^ Arnault, F. (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 .
- ^ isprime - Documentación de ayuda de Maple en maplesoft.com.
- ^ Wolfram Language & System Documentation Center - Algunas notas sobre la documentación de implementación interna en wolfram.com.
- ^ Guía del usuario de la documentación de PARI / GP (versión 2.11.1) para PARI / GP.
- ^ Documentación de la documentación de SageMath para SageMath.
- ^ Documentación del Manual de Maxima para Maxima.
- ^ FLINT: Biblioteca rápida para la documentación de teoría de números para FLINT 2.5.
- ^ BigInteger.java DocJar: API de Java de búsqueda de código abierto.
- ^ Documentación de BigInteger.java para OpenJDK.
- ^ Matemáticas :: Módulo Perl Primality con prueba BPSW
- ^ Math :: Prime :: Util Módulo Perl con pruebas de primalidad que incluyen BPSW
- ^ Math :: Prime :: Util :: GMP Módulo Perl con pruebas de primalidad que incluyen BPSW, usando C + GMP
- ^ NZMATH Archivado el 17 de enero de 2013 en elsistema de cálculo de la teoría de números Wayback Machine en Python
- ^ "SymPy" . SymPy: una biblioteca de Python para matemáticas simbólicas .
- ^ Documentación del algoritmo de prueba principal de GNU MP 6.2.0 para GMPLIB.
- ^ Sistema de álgebra computacional de magma: documentación de pruebas de prima y primordialidad para magma.
- ^ Albrecht, Martin R .; Massimo, Jake; Paterson, Kenneth G .; Somorovsky, Juraj (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 .
Otras lecturas
- Jacobsen, Dana Pseudoprime Estadísticas, tablas y datos (listas de pseudoprimes base 2, Lucas y otros pseudoprimes hasta 10 14 )
- Muy bien, Thomas R., La prueba de primalidad de Baillie-PSW. , Archivado desde el original en 08/28/2013 , recuperado 2007-08-07
- Weisstein, Eric W. "Prueba de primordialidad de Baillie-PSW" . MathWorld .