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 , 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:
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 () 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 () 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 () 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 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 entonces la ecuación () se convierte en
Si la congruencia () es falsa, esto constituye una prueba de que n es compuesto.
Si la congruencia () 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 () 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 : 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 () 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 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. 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 ().
Hay infinitos pseudoprimos fuertes de Lucas y, por lo tanto, infinitos pseudoprimos de Lucas.
El teorema 7 en 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 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 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, 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 () 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): 323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179 y 10877
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 .
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 .
Comprobación de condiciones de congruencia adicionales Si se ha verificado que la congruencia () 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):
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 () o la () 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 ().
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 () 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 1015 para los cuales la congruencia () es verdadera.
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
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 () 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/4k).
Hay una estimación de probabilidad similar para la prueba de los probables primos fuerte de Lucas.