stringtranslate.com

Prueba de primalidad de Baillie-PSW

Problema sin resolver en matemáticas :
¿Existe un número compuesto que pase la prueba de primalidad de Baillie-PSW?
(más problemas sin resolver en matemáticas)

La prueba de primalidad de Baillie-PSW es ​​un algoritmo probabilístico o posiblemente determinista que determina si un número es compuesto o es un primo probable . Recibe su nombre en honor a Robert Baillie, Carl Pomerance , John Selfridge y Samuel Wagstaff .

La prueba Baillie-PSW es ​​una combinación de una prueba fuerte de primos probables de Fermat en base 2 y una prueba fuerte o estándar de primos probables de Lucas . La prueba de Fermat y la 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

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141 y 52633 (secuencia A001262 en la OEIS ).

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 superposición conocida entre estas listas, e incluso hay evidencia de que los números tienden a ser de diferente tipo, de hecho, incluso con la prueba estándar y no fuerte de Lucas no hay superposición conocida. Por ejemplo, los pseudoprimos de Fermat en base 2 tienden a caer en la clase de residuo 1 (mod m ) para muchos m pequeños , mientras que los pseudoprimos de Lucas tienden a caer en la clase de residuo −1 (mod m ). [1] : §6  [2] : Tabla 2 y §5  Como resultado, un número que pasa tanto una base 2 fuerte de Fermat como una prueba fuerte de Lucas es muy probable que sea primo. Si elige una base aleatoria, podría haber algún n compuesto que pase tanto la prueba de Fermat como la de Lucas. Por ejemplo, n = 5777 es una base psp fuerte 76, y también es un pseudoprimo fuerte de Lucas.

Ningún número compuesto por debajo de 2 64 (aproximadamente 1,845·10 19 ) pasa la prueba fuerte o estándar de Baillie–PSW, [3] ese resultado también fue verificado por separado por Charles Greathouse en junio de 2011. En consecuencia, esta prueba es una prueba de primalidad determinista sobre números por debajo de ese límite. Tampoco se conocen números compuestos por encima de ese límite que pasen la prueba, en otras palabras, no se conocen pseudoprimos de Baillie–PSW.

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 afirmó incorrectamente que el valor de este premio se había elevado a 620 dólares, pero estaba confundiendo la secuencia de Lucas con la secuencia de Fibonacci , y sus comentarios realmente solo se aplican a una conjetura de Selfridge . [4] A junio de 2014, el premio sigue sin reclamarse. 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 de modo que, entre los casi 2 1248 productos de primos distintos 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 prueba de Lucas.

La prueba

Sea n el entero positivo impar cuya primalidad deseamos probar.

  1. 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.
  2. Realice una prueba de primos probables fuertes en base 2. Si n no es un primo probable fuerte en base 2, entonces n es compuesto; abandone.
  3. Encuentra la primera D en la secuencia 5, −7, 9, −11, 13, −15, ... para la cual el símbolo de Jacobi ( D / n ) es −1. Haz P = 1 y Q = (1 − D ) / 4.
  4. Realice una prueba de probabilidad fuerte de Lucas sobre n utilizando los parámetros D , P y Q. Si n no es un número primo probable fuerte de Lucas, entonces n es compuesto. De lo contrario, n es casi con certeza primo.

Observaciones.

  1. El primer paso es solo por eficiencia. La prueba 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.
  2. El paso 2 es, en efecto, una única aplicación de la prueba de primalidad de Miller-Rabin , pero utilizando la base fija 2. No hay nada especial en el uso de la base 2; los pseudoprimos de bases diferentes parecen tener la misma tasa de crecimiento [1] , : §8,  por lo que otras bases podrían funcionar igual de bien. Sin embargo, se ha realizado mucho trabajo (ver arriba) para verificar que la combinación de la prueba de primos probables fuertes de base 2 y una prueba fuerte de Lucas hace un buen trabajo para distinguir primos de compuestos.
  3. Baillie y Wagstaff demostraron en el Teorema 9 de la página 1413 de [2] que el número promedio de D que deben probarse es aproximadamente 3,147755149.
  4. 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 utilizando 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.
  5. 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é queremos que el símbolo de Jacobi sea −1, así como por qué se obtienen pruebas de primalidad más potentes si Q ≠ ±1. [8] : 266–269 
  6. 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 ningún costo computacional adicional y solo rara vez son verdaderas si n es compuesto: y .
  7. Existen versiones más débiles de la prueba Baillie-PSW, y a esta a veces se la denomina prueba Baillie-PSW fuerte .
  8. Si la prueba de Lucas se sustituye por una prueba de Fibonacci, no debería llamarse prueba de Baillie-PSW, sino prueba de Selfridge o prueba de PSW. Véase la conjetura de Selfridge sobre las pruebas de primalidad .
  9. En 1980, Pomerance, Selfridge y Wagstaff ofrecieron 30 dólares por un número compuesto que pasara una versión más débil de la prueba Baillie-PSW. Un número así que pasara la prueba (fuerte) Baillie-PSW cumpliría los requisitos. [1]
  10. Con un método apropiado para elegir D , P y Q , solo hay cinco números compuestos impares (también llamados pseudoprimos de Dickson de segunda especie) menores que 10 15 para los cuales . [9] Los autores de [9] sugieren una versión más fuerte de la prueba de primalidad de Baillie-PSW que incluye esta congruencia; los autores ofrecen una recompensa de $2000 por un número compuesto que pase esta prueba más fuerte. Esta versión del algoritmo ya se usa en Mathematica.

El peligro de confiar únicamente en las pruebas de Fermat

Existe una superposición significativa entre las listas de pseudoprimos para diferentes bases.

Elija una base a . Si n es un pseudoprimo con respecto a la base a , entonces es probable que n sea uno de esos pocos números que es un pseudoprimo con respecto a muchas bases. [10]

Por ejemplo, n = 341 es un pseudoprimo en 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 en base a . (Los primeros diez de tales a son 1, 2, 4, 8, 15, 16, 23, 27, 29 y 30). La proporción de tales a en comparación con n es normalmente mucho menor.

Por lo tanto, si n es un pseudoprimo en base a , entonces es más probable que n sea un pseudoprimo en alguna otra base que el promedio. [1] : 1020  Por ejemplo, hay 21853 pseudoprimos en base 2 hasta 25·10 9 . Esto es solo alrededor de dos de cada millón de números enteros impares en este rango. Sin embargo: [1] : 1021 

El número 29341 es el pseudoprimo 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í, de modo que realizar 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, de modo que una combinación de estos tipos de pruebas constituiría una poderosa prueba de primalidad, especialmente si se utilizan las formas fuertes de las pruebas.

Nótese 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-suaves .

También hay superposición entre pseudoprimos fuertes para 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] da un número de Carmichael de 397 dígitos N que es un pseudoprimo fuerte para todas las bases primas menores que 307. Debido a que este N es un número de Carmichael, N también es 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 por el método descrito anteriormente, por lo que este número se determinaría correctamente por la prueba de Baillie-PSW como compuesto.

Aplicaciones de los tests de primalidad combinados de Fermat y Lucas

Los siguientes sistemas de álgebra computacional y paquetes de software utilizan alguna versión de la prueba de primalidad de Baillie-PSW.

La función de Mapleisprime , [12] la función de MathematicaPrimeQ (que ya utiliza la versión de 2020 de Baillie–PSW), [13] las funciones de PARI/GP [14] y la función de SageMath [15] utilizan una combinación de una prueba de probabilidad fuerte de Fermat y una prueba de Lucas. La función de Maxima utiliza una prueba de este tipo para números mayores que 341550071728321. [16]isprimeispseudoprimeis_pseudoprimeprimep

La biblioteca FLINT tiene funciones n_is_probabprimey n_is_probabprime_BPSWque utilizan una prueba combinada, así como otras funciones que realizan pruebas de Fermat y Lucas por separado. [17]

La BigIntegerclase 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 una desventaja en comparación con hacer una prueba de base 2 única como se especifica en la prueba 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 Baillie-PSW, no se puede decir con certeza que si n es menor que algún 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 fuertes de pseudoprime y Lucas. En Python , la biblioteca NZMATH[23] tiene las pruebas fuertes de pseudoprime y Lucas, pero no tiene una función combinada. La biblioteca SymPy [24] sí implementa esto.

A partir de la versión 6.2.0, la función de GNU Multiple Precision Arithmetic Librarympz_probab_prime_p utiliza una prueba de Lucas fuerte y una prueba de Miller–Rabin; las versiones anteriores no utilizaban Baillie–PSW. [25] Las funciones de MagmaIsProbablePrime y IsProbablyPrimeutilizan 20 pruebas de Miller–Rabin para números > 34·10 13 , pero no las combinan con una prueba de primos probables de Lucas. [26]

Las bibliotecas criptográficas suelen tener funciones de prueba de primos. Albrecht et al. analizan las pruebas utilizadas en estas bibliotecas. Algunas utilizan una prueba combinada de Fermat y Lucas; muchas no lo hacen. [27] : Tabla 1  Para algunas de estas últimas, Albrecht et al. pudieron construir números compuestos que las bibliotecas declararon como primos.

Referencias

  1. ^ abcde 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 . JSTOR  2006210.
  2. ^ abcdef 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. MR  0583518.
  3. ^ Nicely, Thomas R. (13 de enero de 2012) [Publicado por primera vez el 10 de junio de 2005]. "La prueba de primalidad de Baillie-PSW". trnicely.net . Archivado desde el original el 21 de noviembre de 2019 . Consultado el 17 de marzo de 2013 .
  4. ^ Guy, R. (1994). "Pseudoprimos. Pseudoprimos de Euler. Pseudoprimos fuertes". §A12 en Problemas sin resolver en teoría de números . 2.ª ed., pág. 28, Nueva York: Springer-Verlag. ISBN 0-387-20860-7 . 
  5. ^ Pomerance, C. (1984). "¿Existen contraejemplos de la prueba de primalidad de Baillie-PSW?" (PDF) .
  6. ^ Greene, John R. (sin fecha). "Baillie–PSW". Universidad de Minnesota Duluth . Consultado el 29 de mayo de 2020 .
  7. ^ Chen, Zhuo; Greene, John (agosto de 2003). "Algunos comentarios sobre los pseudoprimos Baillie-PSW" (PDF) . The Fibonacci Quarterly . 41 (4): 334–344.
  8. ^ Bressoud, David ; Wagon, Stan (2000). Un curso de teoría computacional de números . Nueva York: Key College Publishing en colaboración con Springer. ISBN 978-1-930190-10-8.
  9. ^ por Robert Baillie; Andrew Fiori; Samuel S. Wagstaff, 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. ISSN  0025-5718. S2CID  220055722.
  10. ^ Wagstaff, Samuel S. Jr. (1982). "Pseudoprimos y una generalización de la conjetura de Artin". Acta Aritmética . 41 (2): 141-150. doi : 10.4064/aa-41-2-141-150 .
  11. ^ Arnault, F. (agosto de 1995). "Construcción de números de Carmichael que son pseudoprimos fuertes para varias bases". Journal of Symbolic Computation . 20 (2): 151–161. doi : 10.1006/jsco.1995.1042 .
  12. ^ isprime - Documentación de ayuda de Maple en maplesoft.com.
  13. ^ Wolfram Language & System Documentation Center - Algunas notas sobre la documentación de implementación interna en wolfram.com.
  14. ^ Guía del usuario de PARI/GP (versión 2.11.1) documentación de PARI/GP.
  15. ^ Documentación de SageMath documentación para SageMath.
  16. ^ Documentación manual de Maxima para Maxima.
  17. ^ FLINT: Biblioteca rápida para documentación de teoría de números para FLINT 2.5.
  18. ^ BigInteger.java DocJar: Búsqueda en API Java de código abierto.
  19. ^ Documentación de BigInteger.java para OpenJDK.
  20. ^ Módulo Perl Math::Primality con prueba BPSW
  21. ^ Módulo Perl Math::Prime::Util con pruebas de primalidad que incluyen BPSW
  22. ^ Módulo Perl Math::Prime::Util::GMP con pruebas de primalidad que incluyen BPSW y utilizan C+GMP
  23. ^ NZMATH Archivado el 17 de enero de 2013 en Wayback Machine Sistema de cálculo de teoría de números en Python
  24. ^ "SymPy". SymPy: una biblioteca de Python para matemáticas simbólicas .
  25. ^ Documentación del algoritmo de prueba principal GNU MP 6.2.0 para GMPLIB.
  26. ^ Sistema de Álgebra Computacional Magma - Documentación de pruebas de primos y primalidad para Magma.
  27. ^ Albrecht, Martin R.; Massimo, Jake; Paterson, Kenneth G.; Somorovsky, Juraj (15 de octubre de 2018). Primaria y prejuicio: pruebas de primalidad 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.

Lectura adicional