Número pseudoprimo de Lucas

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

Baillie y Wagstaff definen los pseudoprimos de Lucas de la siguiente manera:​

Dados los números enteros P y Q, donde P > 0 y $D=P^{2}-4Q$, sean U_k(P, Q) y V_k(P, Q) las sucesiones de Lucas correspondientes.

Sea n un entero positivo y sea $\left({\tfrac {D}{n}}\right)$ el símbolo de Jacobi. Entonces, se define

$\delta (n)=n-\left({\tfrac {D}{n}}\right).$

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

$U_{\delta (n)}\equiv 0{\pmod {n}}.$

(1)

Si esta congruencia no se cumple, entonces n no es primo. Si n es compuesto, entonces esta congruencia generalmente no se cumple.​ 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​ 142–152 del libro de Crandall y Pomerance,​ y las páginas 53–74 del libro de Ribenboim.​

Números primos y pseudoprimos probables de Lucas

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​ 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​ 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 $\left({\tfrac {D}{n}}\right)$ sea −1 (véanse las páginas 1401–1409 de​, página 1024 de​ o las páginas 266–269 de​ ). 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​ y descrito a continuación).

Si $\left({\tfrac {D}{n}}\right)=-1,$ entonces la ecuación (1) se convierte en

$U_{n+1}\equiv 0{\pmod {n}}.$

(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): U₀ = 0 , U₁ = 1, U₂ = 3, U₃ = 10, etc.

Primero, sea n = 19. El símbolo de Jacobi $\left({\tfrac {13}{19}}\right)$ es −1, entonces δ(n) = 20, U₂₀ = 6616217487 = 19·348221973 y se obtiene

$U_{20}=6616217487\equiv 0{\pmod {19}}.$

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, $\left({\tfrac {13}{119}}\right)$ = −1, y se puede calcular

$U_{120}\equiv 0{\pmod {119}}.$

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

Aquí se factoriza $\delta (n)=n-\left({\tfrac {D}{n}}\right)$ en la forma $d\cdot 2^{s}$, donde $d$ 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

$U_{d}\equiv 0{\pmod {n}}$

o

$V_{d\cdot 2^{r}}\equiv 0{\pmod {n}}$

para algunos 0 ≤ r < s; véase la página 1396 de​. 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​ establece:

Sean $P$ y $Q$ números enteros positivos relativamente primos entre sí para los cuales $P^{2}-4Q$ es positivo pero no un cuadrado. Entonces hay una constante positiva $c$ (que depende de $P$ y $Q$) tal que el número de pseudoprimos fuertes de Lucas que no excedan de $x$ sea mayor que $c\cdot \log x$, para $x$ suficientemente grande.

Se puede establecer que Q = −1, y entonces $U_{n}$ y $V_{n}$ 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​ es un pseudoprimo fuerte de Lucas para un conjunto de parámetros (P, Q) donde Q = 1, satisfaciendo una de las condiciones

$U_{d}\equiv 0{\pmod {n}}{\text{and }}V_{d}\equiv \pm 2{\pmod {n}}$

o

$V_{d\cdot 2^{r}}\equiv 0{\pmod {n}}$

para algunos $0\leq r<s-1$. Un pseudoprimo de Lucas extrafuerte también es un pseudoprimo de Lucas fuerte para el mismo par $(P,Q)$.

Desarrollo de una prueba de primalidad de Lucas

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 $\left({\tfrac {D}{n}}\right)=-1$, 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 $\left({\tfrac {D}{n}}\right)=-1$ . Téngase en cuenta que $\left({\tfrac {k}{n}}\right)\left({\tfrac {-k}{n}}\right)=-1$. (Si D y n tienen un factor primo en común, entonces $\left({\tfrac {D}{n}}\right)=0$). 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,​ p. 1416. Una vez que se obtiene D, se configuran $P=1$ y $Q=(1-D)/4$. 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 $U_{n+1}$ y $V_{n+1}$ en $O(\log _{2}n)$ pasos; véase sucesión de Lucas. Se empieza con

$U_{1}=1$

$V_{1}=P=1$

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

$U_{2k}=U_{k}\cdot V_{k}$

$V_{2k}=V_{k}^{2}-2Q^{k}={\frac {V_{k}^{2}+DU_{k}^{2}}{2}}$.

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

$U_{2k+1}=(P\cdot U_{2k}+V_{2k})/2$

$V_{2k+1}=(D\cdot U_{2k}+P\cdot V_{2k})/2$.

Si $P\cdot U_{2k}+V_{2k}$ es impar, se debe reemplazar por $P\cdot U_{2k}+V_{2k}+n$; que es par, por lo que ahora se puede dividir por 2. El numerador de $V_{2k+1}$ 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 $U$, $V$ y la potencia de $Q$, 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: 1₂ = 1, 10₂ = 2 , 100₂ = 4, 101₂ = 5, 1010₂ = 10, 1011₂ = 11, 10110₂ = 22, 101100₂ = 44. Por lo tanto, se calcula U₁, U₂, U₄, U₅, U₁₀, U₁₁, U₂₂ y U₄₄. También se calculan los términos del mismo número en la secuencia V, junto con Q¹, Q², Q⁴, Q⁵, Q ¹⁰, Q¹¹, Q²² y Q⁴⁴.

Al final del cálculo, se habrán obtenido U_n+1, V_n+1 y ⁿ⁺¹X, (mod n).

A continuación se verifica la congruencia (2) usando el valor conocido de U_n+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​): 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 $Q=1$.

Luego, se debe probar con P = 3, 4, 5, 6, ..., hasta que se encuentre un valor de $D=P^{2}-4Q$ para el que el símbolo de Jacobi $\left({\tfrac {D}{n}}\right)=-1$.

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

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 $\left({\tfrac {D}{n}}\right)=-1$, entonces se tiene lo siguiente (véase la ecuación 2 en la página 1392 de​):

$V_{n+1}\equiv 2Q{\pmod {n}}.$

(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 V_n+1 se calculó en el proceso de cálculo de U_n+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 $\left({\tfrac {D}{n}}\right)$ 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 10⁸ para el cual la congruencia (3) es verdadera (véase la página 1409 y la Tabla 6 de;​). 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 10¹⁵ para los cuales la congruencia (3) es verdadera.​

Si $Q\neq \pm 1$, entonces se puede establecer una condición de congruencia adicional que implica muy pocos nuevos cálculos.

Recuérdese que $Q^{n+1}$ se obtiene durante el cálculo de $U_{n+1}$, y se puede guardar fácilmente la potencia de $Q$ calculada previamente, es decir, $Q^{(n+1)/2}$.

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

$Q^{(n-1)/2}\equiv \left({\tfrac {Q}{n}}\right){\pmod {n}}$.

(aquí, $\left({\tfrac {Q}{n}}\right)$ 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

$Q^{(n+1)/2}\equiv Q\cdot Q^{(n-1)/2}\equiv Q\cdot \left({\tfrac {Q}{n}}\right){\pmod {n}}.$

(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.​ 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

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/4^k).

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

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)² 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

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

Un pseudoprimo de Fibonacci suele ser​​​ 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,​ y Crandall y Pomerance​ 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 10¹¹ 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​

$V_{n}(P,Q)\equiv P{\pmod {n}}.$

(5)

Esto lleva a una definición alternativa de los pseudoprimos de Fibonacci:​​

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.​ Hoggatt y Bicknell estudiaron las propiedades de estos pseudoprimos en 1974.​ Singmaster calculó estos pseudoprimos hasta 100000.​ Jacobsen enumera todos los 111.443 de estos pseudoprimos menores que 10¹³.​

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

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.​ Se sigue de​ 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) | (n − p) 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

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 U_n 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:

${\text{ }}U_{n}\equiv \left({\tfrac {2}{n}}\right){\pmod {n}}$

con (P, Q) = (2, −1) definiendo nuevamente U_n 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, ...

Enlaces externos

• Anderson, Peter G. Pseudoprimos de Fibonacci, sus factores y sus puntos de entrada.
• Anderson, Peter G. Fibonacci Pseudoprimes bajo 2,217,967,487 y sus factores.
• Jacobsen, Dana Estadísticas, tablas y datos de pseudoprimos (datos para pseudoprimos de Lucas, Strong Lucas, AES Lucas, ES Lucas por debajo de 10¹⁴; pseudoprimos de Fibonacci y Pell por debajo de 10¹²)
• Weisstein, Eric W. «Fibonacci Pseudoprime». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Lucas Pseudoprime». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Strong Lucas Pseudoprime». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Extra Strong Lucas Pseudoprime». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

• Datos: Q3343106