Test de primalidad de Baillie-PSW

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

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

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141 y 52633 (sucesión A001262 en OEIS).

y 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 (sucesión A217255 en OEIS).

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 2⁶⁴ (aproximadamente 1845·10¹⁹) 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 2¹²⁴⁸ 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

Sea n el entero positivo impar cuya primalidad se desea probar:

1. 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.
2. 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.
3. 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.
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:

1. 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.
2. 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.
3. 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.
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 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.
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é 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}
6. 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: ${\displaystyle V_{n+1}\equiv 2Q{\pmod {n}}}$ y ${\displaystyle Q^{(n+1)/2}=Q\cdot Q^{(n-1)/2}\equiv Q\cdot \left({\tfrac {Q}{n}}\right){\pmod {n}}}$.
7. 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.
8. 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.
9. 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]​
10. Con un método apropiado para elegir D, P y Q, solo hay cinco números compuestos impares menores que 10¹⁵ para los cuales ${\displaystyle V_{n+1}\equiv 2Q{\pmod {n}}}$.^[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

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·10⁹. 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 2⁶⁴ 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

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 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 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 2⁶⁴, 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·10¹³, 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

Lecturas relacionadas

• Jacobsen, Dana Pseudoprime Statistics, Tables, and Data (lists of pseudoprimes base 2, Lucas, and other pseudoprimes to 10¹⁴)
• 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. 

Esta página se editó por última vez el 17 ene 2024 a las 15:12.