Ir al contenido

Número pseudoprimo de Lucas

De Wikipedia, la enciclopedia libre

Los números pseudoprimos de Lucas y los números pseudoprimos de Fibonacci son números enteros compuestos que pasan ciertas pruebas que todos los primos y muy pocos números compuestos pasan: en este caso, criterios relativos a alguna sucesión de Lucas.

Pseudoprimos de Baillie-Wagstaff-Lucas

[editar]

Baillie y Wagstaff definen los pseudoprimos de Lucas de la siguiente manera:[1]

Dados los números enteros P y Q, donde P > 0 y , sean Uk(P, Q) y Vk(P, Q) las sucesiones de Lucas correspondientes.

Sea n un entero positivo y sea el símbolo de Jacobi. Entonces, se define

Si n es un primo que no divide a Q, entonces se cumple la siguiente condición de congruencia:

 

 

 

 

(1)

Si esta congruencia no se cumple, entonces n no es primo. Si n es compuesto, entonces esta congruencia generalmente no se cumple.[1]​ Estos son los hechos clave que hacen que las secuencias de Lucas sean útiles como test de primalidad.

La congruencia (1) representa uno de los dos criterios que definen un número pseudoprimo de Frobenius. Por lo tanto, cada pseudoprimo de Frobenius es también un pseudoprimo de Baillie-Wagstaff-Lucas, pero no siempre ocurre lo contrario.

Algunas buenas referencias son el capítulo 8 del libro de Bressoud y Wagon (con código Mathematica), las páginas[2]​ 142–152 del libro de Crandall y Pomerance,[3]​ y las páginas 53–74 del libro de Ribenboim.[4]

Números primos y pseudoprimos probables de Lucas

[editar]

Un primo probable de Lucas para un par dado (P, Q) es cualquier entero positivo n para el cual la ecuación (1) anterior es verdadera (consúltese la página[1]​ 1398).

Un pseudoprimo de Lucas para un par dado (P, Q) es un entero positivo compuesto n para el que la ecuación (1) es verdadera (véase[1]​ la página 1391).

Una prueba de primos probables de Lucas es más útil si se elige D de modo que el símbolo de Jacobi sea −1 (véanse las páginas 1401–1409 de[1]​, página 1024 de[5]​ o las páginas 266–269 de[2]​ ). Esto es especialmente importante cuando se combina una prueba de Lucas con una prueba para analizar un número pseudoprimo fuerte, como el test de primalidad de Baillie-PSW. Normalmente, las aplicaciones utilizarán un método de selección de parámetros que garantice esta condición (por ejemplo, el método de Selfridge recomendado en[1]​ y descrito a continuación).

Si entonces la ecuación (1) se convierte en

 

 

 

 

(2)

  • Si la congruencia (2) es falsa, esto constituye una prueba de que n es compuesto.
  • Si la congruencia (2) es verdadera, entonces n es un primo probable de Lucas.

En este caso, o n es primo o es un pseudoprimo de Lucas.

Si la congruencia (2) es verdadera, entonces n es probable que sea primo (esto justifica el término probable primo), pero esto no prueba que n sea primo.

Como es el caso con cualquier otra prueba de primalidad probabilística, si se realizan pruebas adicionales de Lucas con diferentes D, P y Q, entonces a menos que una de las pruebas demuestre que n es compuesto, se refuerza la posibilidad de que n sea primo.

Ejemplos: si P = 3, Q = −1 y D = 13, la secuencia de U es (sucesión A006190 en OEIS): U0 = 0 , U1 = 1, U2 = 3, U3 = 10, etc.

Primero, sea n = 19. El símbolo de Jacobi es −1, entonces δ(n) = 20, U20 = 6616217487 = 19·348221973 y se obtiene

Por lo tanto, 19 es un primo probable de Lucas para este par (P, Q). En este caso, 19 es primo, por lo que no es un pseudoprimo de Lucas.

Para el siguiente ejemplo, sea n = 119. Entonces, = −1, y se puede calcular

Sin embargo, 119 = 7·17 no es primo, por lo que 119 es un pseudoprimo de Lucas para este par ("P, Q").

De hecho, 119 es el pseudoprimo más pequeño para P = 3, Q = −1.

Como se analiza más abajo, para verificar la ecuación (2) para una n dada, no se necesita calcular todos los primeros n + 1 términos en la secuencia U.

Sea Q = −1, entonces, los pseudoprimos de Lucas más pequeños para P = 1, 2, 3, ... son

323, 35, 119, 9, 9, 143, 25, 33, 9, 15, 123, 35, 9, 9, 15, 129, 51, 9, 33, 15, 21, 9, 9, 49, 15, 39, 9, 35, 49, 15, 9, 9, 33, 51, 15, 9, 35, 85, 39, 9, 9, 21, 25, 51, 9, 143, 33, 119, 9, 9, 51, 33, 95, 9, 15, 301, 25, 9, 9, 15, 49, 155, 9, 399, 15, 33, 9, 9, 49, 15, 119, 9, ...

Pseudoprimos fuertes de Lucas

[editar]

Aquí se factoriza en la forma , donde es impar.

Un pseudoprimo fuerte de Lucas para un par dado (P, Q) es un número compuesto impar n con MCD(n, D) = 1, que satisface una de las condiciones

o

para algunos 0 ≤ r < s; véase la página 1396 de[1]​. Un pseudoprimo fuerte de Lucas también es un pseudoprimo de Lucas (para el mismo par (P, Q), pero lo contrario no es necesariamente cierto.

Por lo tanto, la prueba fuerte es una prueba de primalidad más estricta que la ecuación (1).

Hay infinitos pseudoprimos fuertes de Lucas y, por lo tanto, infinitos pseudoprimos de Lucas.

El teorema 7 en[1]​ establece:

Sean y números enteros positivos relativamente primos entre sí para los cuales es positivo pero no un cuadrado. Entonces hay una constante positiva (que depende de y ) tal que el número de pseudoprimos fuertes de Lucas que no excedan de sea mayor que , para suficientemente grande.

Se puede establecer que Q = −1, y entonces y son una P-secuencia de Fibonacci y una P-secuencia de Lucas. Los pseudoprimos se pueden llamar pseudoprimos de Lucas fuertes en base P, por ejemplo, los pseudoprimos fuertes de Lucas más pequeños con P = 1, 2, 3, .. son 4181, 169, 119, ...

Un pseudoprimo de Lucas extra fuerte[6]​ es un pseudoprimo fuerte de Lucas para un conjunto de parámetros (P, Q) donde Q = 1, satisfaciendo una de las condiciones

o

para algunos . Un pseudoprimo de Lucas extrafuerte también es un pseudoprimo de Lucas fuerte para el mismo par .

Desarrollo de una prueba de primalidad de Lucas

[editar]

Antes de iniciar una prueba de primos probables, generalmente se verifica que n, el número del que se va a probar su primalidad, es impar, no es un cuadrado perfecto y no es divisible por ningún primo pequeño menor que un límite conveniente. Los cuadrados perfectos son fáciles de detectar usando el método de Newton para raíces cuadradas.

Se elige una sucesión de Lucas donde el símbolo de Jacobi , de forma que δ(n) = n + 1.

Dado n, una técnica para elegir D es usar prueba y error para encontrar la primera D en la secuencia 5, −7, 9, −11, ... tal que . Téngase en cuenta que . (Si D y n tienen un factor primo en común, entonces ). Con esta secuencia de valores D, el número promedio de valores D que deben probarse antes de encontrar uno cuyo símbolo de Jacobi sea −1 es aproximadamente 1,79; véase,[1]​ p. 1416. Una vez que se obtiene D, se configuran y . Es una buena idea comprobar que n no tiene factores primos en común con P o Q. Este método de elegir D, P y Q fue sugerido por John Selfridge.

Esta búsqueda nunca tendrá éxito si n es un cuadrado y, por el contrario, si tiene éxito, es una prueba de que n no es un cuadrado. Por lo tanto, se puede ahorrar algo de tiempo retrasando la prueba de n para la cuadratura hasta después de que los primeros pasos de búsqueda hayan fallado.

Dados D, P y Q, existen relaciones de recurrencia que permiten calcular rápidamente y en pasos; véase sucesión de Lucas. Se empieza con

Primero, se puede duplicar el subíndice de a en un solo paso usando las relaciones de recurrencia

.

A continuación, se puede aumentar el subíndice en 1 usando las recurrencias

.

Si es impar, se debe reemplazar por ; que es par, por lo que ahora se puede dividir por 2. El numerador de se maneja de la misma manera (agregar n no cambia el resultado de la operación módulo n). Obsérvese que, para cada término que se calcula en la sucesión U, se calcula el término correspondiente en la sucesión V. A medida que se avanza, también se calculan las mismas potencias correspondientes de Q.

En cada etapa se reducen , y la potencia de , mod n.

Se usan los bits de la expansión binaria de n para determinar qué términos en la secuencia U calcular. Por ejemplo, si n+1 = 44 (= 101100 en binario), entonces, tomando los bits uno por uno de izquierda a derecha, se obtiene la secuencia de índices a calcular: 12 = 1, 102 = 2 , 1002 = 4, 1012 = 5, 10102 = 10, 10112 = 11, 101102 = 22, 1011002 = 44. Por lo tanto, se calcula U1, U2, U4, U5, U10, U11, U22 y U44. También se calculan los términos del mismo número en la secuencia V, junto con Q1, Q2, Q4, Q5, Q 10, Q11, Q22 y Q44.

Al final del cálculo, se habrán obtenido Un+1, Vn+1 y n+1X, (mod n).

A continuación se verifica la congruencia (2) usando el valor conocido de Un+1.

Cuando se eligen D, P y Q como se describe arriba, los primeros 10 pseudoprimos de Lucas son (consúltese la página 1401 de[1]​): 323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179 y 10877 (sucesión A217120 en OEIS)

Las versiones fuertes de la prueba de Lucas se pueden aplicar de manera similar.

Cuando se eligen D, P y Q como se describe anteriormente, los primeros 10 pseudoprimos de Lucas fuertes son: 5459, 5777, 10877, 16109, 18971, 22499, 24569 , 25199, 40309 y 58519 (sucesión A217255 en OEIS).

Para calcular una lista de pseudoprimos de Lucas extra fuertes, configúrese .

Luego, se debe probar con P = 3, 4, 5, 6, ..., hasta que se encuentre un valor de para el que el símbolo de Jacobi .

Con este método para seleccionar D, P y Q, los primeros 10 pseudoprimos de Lucas extra fuertes son 989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059 y 72389 (sucesión A217719 en OEIS).

Comprobación de condiciones de congruencia adicionales

[editar]

Si se ha verificado que la congruencia (2) es verdadera, hay condiciones de congruencia adicionales que se pueden verificar y que casi no tienen costo computacional adicional.

Si resulta que n es compuesto, estas condiciones adicionales pueden ayudar a descubrir ese hecho.

Si n es un primo impar y , entonces se tiene lo siguiente (véase la ecuación 2 en la página 1392 de[1]​):

 

 

 

 

(3)

Aunque esta condición de congruencia no es, por definición, parte de la prueba de los primos probables de Lucas, es casi gratis verificar esta condición porque, como se señaló anteriormente, el valor de Vn+1 se calculó en el proceso de cálculo de Un+1.

Si la congruencia (2) o la (3) es falsa, esto constituye una prueba de que n no es primo.

Si ambas congruencias son verdaderas, entonces es aún más probable que n sea primo que si se hubiera verificado solo la congruencia (2).

Si el método de Selfridge (arriba) para elegir D, P y Q estableciera Q = −1, entonces se pueden ajustar P y Q para que D y permanezcan sin cambios y P = Q = 5 (véanse las Relaciones algebraicas en el artículo sucesión de Lucas).

Si se usa este método mejorado para elegir P y Q, entonces 913 = 11·83 es ​​el único compuesto menor que 108 para el cual la congruencia (3) es verdadera (véase la página 1409 y la Tabla 6 de;[1]​). Cálculos más extensos demuestran que, con este método de elegir D, P y Q, solo hay cinco números compuestos impares menores que 1015 para los cuales la congruencia (3) es verdadera.[7]

Si , entonces se puede establecer una condición de congruencia adicional que implica muy pocos nuevos cálculos.

Recuérdese que se obtiene durante el cálculo de , y se puede guardar fácilmente la potencia de calculada previamente, es decir, .

Si n es primo, entonces, por el criterio de Euler,

.

(aquí, es el símbolo de Legendre; si n es primo, esto es lo mismo que el símbolo de Jacobi).

Por lo tanto, si n es primo, se debe tener que

 

 

 

 

(4)

El símbolo de Jacobi del lado derecho es fácil de calcular, por lo que esta congruencia es sencilla de verificar.

Si esta congruencia no se cumple, entonces n no puede ser primo. Siempre que el MCD(n, Q) = 1, la prueba de congruencia (4) es equivalente a aumentar la prueba de Lucas en desarrollo con una Q base para el test de Solovay-Strassen.

Las condiciones de congruencia adicionales que deben cumplirse si n es primo se describen en la Sección 6 de.[1]​ Si cualquiera de estas condiciones no se cumple, entonces se ha demostrado que n no es primo.

Comparación con la prueba de primalidad de Miller-Rabin

[editar]

Las k aplicaciones del test de primalidad de Miller-Rabin declaran que un compuesto n es probablemente primo con una probabilidad máxima de (1/4k).

Hay una estimación de probabilidad similar para la prueba de los probables primos fuerte de Lucas.[8]

Aparte de dos excepciones triviales (véase más abajo), la fracción de los pares (P,Q) (módulo n) que declaran que la probabilidad de que un compuesto n sea primo es a lo sumo (4/15).

Por lo tanto, las k aplicaciones de la prueba fuerte de Lucas declararían que un compuesto n es probablemente primo con una probabilidad máxima de (4/15)k.

Hay dos excepciones triviales. Una es n = 9. La otra se produce cuando n = p(p+2) es el producto de dos primos gemelos. Tal n es fácil de factorizar, porque en este caso, n+1 = (p+1)2 es un cuadrado perfecto. También se pueden detectar rápidamente cuadrados perfectos usando el método de Newton para obtener raíces cuadradas.

Al combinar una prueba de pseudoprimos de Lucas con un test de primalidad de Fermat, por ejemplo, en base 2, se pueden obtener pruebas probabilísticas de primalidad muy potentes, como el test de primalidad de Baillie-PSW.

Pseudoprimos de Fibonacci

[editar]

Cuando P = 1 y Q = −1, la secuencia Un(P,Q) representa los números de Fibonacci.

Un pseudoprimo de Fibonacci suele ser[2]: 264,  [3]: 142,  [4]: 127  definido como un número compuesto n no divisible por 5 para el cual se cumple la congruencia (1) con P = 1 y Q = −1 (pero n lo es). Según esta definición, los pseudoprimos de Fibonacci forman una secuencia:

323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, 10877, ... (sucesión A081264 en OEIS).

Las referencias de Anderson y Jacobsen a continuación usan esta definición.

Si n es congruente con 2 o 3 módulo 5, entonces Bressoud,[2]: 272–273  y Crandall y Pomerance[3]: 143, 168  señalan que es raro que un pseudoprimo de Fibonacci también sea un número pseudoprimo de Fermat de base 2. Sin embargo, cuando n es congruente con 1 o 4 módulo 5, lo contrario es cierto, con más del 12% de los pseudoprimos de Fibonacci por debajo de 1011 que también son pseudoprimos de Fermat de base 2.

Si n es primo y MCD(n, Q) = 1, entonces también se tiene que[1]: 1392 

 

 

 

 

(5)

Esto lleva a una definición alternativa de los pseudoprimos de Fibonacci:[9][10]

un pseudoprimo de Fibonacci es un número compuesto n para el cual se cumple la congruencia (5) con P = 1 y Q = −1.

Esta definición lleva a que los pseudoprimos de Fibonacci formen una secuencia:

705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251, ... (sucesión A005845 en OEIS)

por lo que también se conocen como pseudoprimos de Bruckman-Lucas.[4]: 129  Hoggatt y Bicknell estudiaron las propiedades de estos pseudoprimos en 1974.[11]​ Singmaster calculó estos pseudoprimos hasta 100000.[12]​ Jacobsen enumera todos los 111.443 de estos pseudoprimos menores que 1013.[13]

Se ha demostrado que ni siquiera existen pseudoprimos de Fibonacci tal como los define la ecuación (5).[14][15]

Sin embargo, los pseudoprimos de Fibonacci sí que existen (sucesión A141137 en OEIS) bajo la primera definición dada por (1).

Un pseudoprimo fuerte de Fibonacci es un número compuesto n para el que se cumple la congruencia (5) para Q = −1 y todo P.[16]​ Se sigue de[16]: 460  que un entero compuesto impar n es un pseudoprimo fuerte de Fibonacci si y solo si:

  1. n es un Número de Carmichael
  2. 2(p + 1) | (n − 1) o 2(p + 1) | (np) para cada primo p que divide a n.

El ejemplo más pequeño de un pseudoprimo fuerte de Fibonacci es 443372888629441 = 17·31·41·43·89·97·167·331.

Pseudoprimos de Pell

[editar]

Un pseudoprimo de Pell puede definirse como un número compuesto n para el que la ecuación (1) anterior es verdadera con P = 2 y Q = −1; siendo entonces la secuencia Un de números de Pell. Los primeros pseudoprimos son entonces 35, 169, 385, 779, 899, 961, 1121, 1189, 2419,...

Esto difiere de la definición en A099011, que puede escribirse como:

con (P, Q) = (2, −1) definiendo nuevamente Un como números de Pell. Los primeros pseudoprimos son entonces 169, 385, 741, 961, 1121, 2001, 3827, 4879, 5719, 6215...

Una tercera definición usa la ecuación (5) con (P, Q) = (2, −1), lo que lleva a los pseudoprimos 169, 385, 961, 1105, 1121, 3827, 4901, 6265, 6441, 6601, 7107, 7801, 8119, ...

Referencias

[editar]
  1. a b c d e f g h i j k l m n Robert Baillie; Samuel S. Wagstaff, Jr. (October 1980). «Lucas Pseudoprimes». Mathematics of Computation 35 (152): 1391-1417. JSTOR 2006406. MR 583518. doi:10.1090/S0025-5718-1980-0583518-6. 
  2. a b c d David Bressoud; Stan Wagon (2000). A Course in Computational Number Theory. New York: Key College Publishing in cooperation with Springer. ISBN 978-1-930190-10-8. (requiere registro). 
  3. a b c Richard E. Crandall; Carl Pomerance (2005). Prime numbers: A computational perspective (2nd edición). Springer Science+Business Media. ISBN 0-387-25282-7. 
  4. a b c Paulo Ribenboim (1996). The New Book of Prime Number Records. Springer Science+Business Media. ISBN 0-387-94457-5. 
  5. Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, 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. 
  6. Jon Grantham (March 2000). «Frobenius Pseudoprimes». Mathematics of Computation 70 (234): 873-891. MR 1680879. arXiv:1903.06820. doi:10.1090/S0025-5718-00-01197-2. 
  7. 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». 
  8. F. Arnault (April 1997). «The Rabin-Monier Theorem for Lucas Pseudoprimes». Mathematics of Computation 66 (218): 869-881. doi:10.1090/s0025-5718-97-00836-3. «citeseerx: 10.1.1.192.4789». 
  9. Adina Di Porto; Piero Filipponi (1989). «More on the Fibonacci Pseudoprimes». Fibonacci Quarterly 27 (3): 232-242. 
  10. Di Porto, Adina; Filipponi, Piero; Montolivo, Emilio (1990). «On the generalized Fibonacci pseudoprimes». Fibonacci Quarterly 28: 347-354. «citeseerx: 10.1.1.388.4993». 
  11. V. E. Hoggatt, Jr.; Marjorie Bicknell (September 1974). «Some Congruences of the Fibonacci Numbers Modulo a Prime p». Mathematics Magazine 47 (4): 210-214. JSTOR 2689212. doi:10.2307/2689212. 
  12. David Singmaster (1983). «Some Lucas Pseudoprimes». Abstracts Amer. Math. Soc. 4 (83T–10–146): 197. 
  13. «Pseudoprime Statistics and Tables». Consultado el 5 de mayo de 2019. 
  14. P. S. Bruckman (1994). «Lucas Pseudoprimes are odd». Fibonacci Quarterly 32: 155-157. 
  15. Di Porto, Adina (1993). «Nonexistence of Even Fibonacci Pseudoprimes of the First Kind». Fibonacci Quarterly 31: 173-177. «citeseerx: 10.1.1.376.2601». 
  16. a b Müller, Winfried B.; Oswald, Alan (1993). «Generalized Fibonacci Pseudoprimes and Probable Primes». En G.E. Bergum, ed. Applications of Fibonacci Numbers 5. Kluwer. pp. 459-464. doi:10.1007/978-94-011-2058-6_45. 

Enlaces externos

[editar]