Los pseudoprimos de Lucas y los pseudoprimos de Fibonacci son enteros compuestos que pasan ciertas pruebas que pasan todos los números primos y muy pocos compuestos: en este caso, criterios relativos a alguna secuencia de Lucas .
Pseudoprimes de Baillie-Wagstaff-Lucas
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 U k ( P , Q ) y V k ( P , Q ) las correspondientes secuencias de Lucas .
Sea n un entero positivo y seasea el símbolo de Jacobi . Definimos
Si n es un primo tal que el máximo común divisor de n y Q (es decir, GCD ( n, Q )) es de 1, a continuación, la siguiente condición congruencia sostiene:
( 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 en las pruebas de primalidad .
La congruencia ( 1 ) representa una de las dos congruencias que definen un pseudoprime de Frobenius . Por lo tanto, cada pseudoprime de Frobenius es también un pseudoprime de Baillie-Wagstaff-Lucas, pero lo contrario no siempre se cumple.
Algunas buenas referencias son el capítulo 8 del libro de Bressoud y Wagon (con código de Mathematica ), [2] páginas 142-152 del libro de Crandall y Pomerance, [3] y páginas 53-74 del libro de Ribenboim. [4]
Lucas probables primos y pseudoprimos
Un primo probable de Lucas para un par ( P, Q ) dado es cualquier entero positivo n para el cual la ecuación ( 1 ) anterior es verdadera (ver, [1] página 1398).
Un pseudoprime de Lucas para un par ( P, Q ) dado es un entero compuesto positivo n para el cual la ecuación ( 1 ) es verdadera (ver, [1] página 1391).
Una prueba de primo probable de Lucas es más útil si D se elige de manera que el símbolo de Jacobies −1 (consulte las páginas 1401–1409 de, [1] la 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 de pseudoprime fuerte , como la prueba de primalidad de Baillie-PSW . Normalmente, las implementaciones utilizarán un método de selección de parámetros que garantice esta condición (por ejemplo, el método 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 número primo probable de Lucas. En este caso, n es primo o es un pseudoprime de Lucas. Si la congruencia ( 2 ) es verdadera, entonces es probable que n 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 realizamos pruebas de Lucas adicionales con diferentes D , P y Q , entonces, a menos que una de las pruebas demuestre que n es compuesto, ganamos más confianza en que n es primo.
Ejemplos: Si P = 3, Q = −1 y D = 13, la secuencia de U es OEIS : A006190 : U 0 = 0, U 1 = 1, U 2 = 3, U 3 = 10, etc.
Primero, sea n = 19. El símbolo de Jacobies −1, entonces δ ( n ) = 20, U 20 = 6616217487 = 19 · 348221973 y tenemos
Por lo tanto, 19 es un número primo probable de Lucas para este par ( P, Q ). En este caso, 19 es primo, por lo que no es un pseudoprime de Lucas.
Para el siguiente ejemplo, sea n = 119. Tenemos = −1, y podemos calcular
Sin embargo, 119 = 7 · 17 no es primo, por lo que 119 es un pseudoprime de Lucas para este par ( P, Q ). De hecho, 119 es el pseudoprime más pequeño para P = 3, Q = −1.
Veremos a continuación que, para verificar la ecuación ( 2 ) para un n dado , no necesitamos calcular todos los primeros n + 1 términos en la secuencia U.
Deje Q = −1, el pseudoprime de Lucas más pequeño a 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, ...
Pseudoprimes fuertes de Lucas
Ahora, factor en la forma dónde es impar.
Un pseudoprime de Lucas fuerte para un par ( P, Q ) dado es un número compuesto impar n con GCD ( n, D ) = 1, que satisface una de las condiciones
o
para algunos 0 ≤ r < s ; consulte la página 1396 de. [1] Un pseudoprime de Lucas fuerte es también un pseudoprime 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 ).
Podemos establecer Q = −1, luego y son la secuencia P -Fibonacci y la secuencia P -Lucas, las pseudoprimas pueden llamarse pseudoprimas de Lucas fuertes en la base P , por ejemplo, las pseudoprimas de Lucas menos fuertes con P = 1, 2, 3, ... son 4181, 169, 119, ...
Un pseudoprime de Lucas extra fuerte [6] es un pseudoprime de Lucas fuerte para un conjunto de parámetros ( P , Q ) donde Q = 1, satisfaciendo una de las condiciones
o
para algunos . Un pseudoprime de Lucas extra fuerte es también un pseudoprime de Lucas fuerte para el mismo par.
Implementación de una prueba de prima probable de Lucas
Antes de embarcarse en una prueba de primos probables, normalmente se verifica que n , el número que se probará para determinar su primalidad, es impar, no es un cuadrado perfecto y no es divisible por ningún primo pequeño menor que algún límite conveniente. Los cuadrados perfectos son fáciles de detectar utilizando el método de Newton para raíces cuadradas.
Elegimos una secuencia de Lucas donde el símbolo de Jacobi , de modo 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. Tenga en cuenta que. (Si D y n tienen un factor primo en común, entonces). Con esta secuencia de valores D , el número medio de valores D que deben probarse antes de encontrar uno cuyo símbolo de Jacobi sea −1 es aproximadamente 1,79; ver, [1] p. 1416. Una vez que tenemos D , establecemos y . Es una buena idea para comprobar que n no tiene factores primos comunes 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 cuadrado y, a la inversa, si tiene éxito, eso es una prueba de que n no es cuadrado. Por lo tanto, se puede ahorrar algo de tiempo si se retrasa la prueba de cuadratura de n hasta que hayan fallado todos los primeros pasos de búsqueda. .)
Dados D , P y Q , existen relaciones de recurrencia que nos permiten calcular rápidamente y en pasos; ver secuencia de Lucas § Otras relaciones . Empezar,
Primero, podemos duplicar el subíndice de a en un solo paso usando las relaciones de recurrencia
- .
A continuación, podemos aumentar el subíndice en 1 usando las recurrencias
- .
Si es extraño, reemplácelo con ; esto es incluso así que ahora se puede dividir por 2. El numerador dese maneja de la misma manera. (Sumar n no cambia el resultado módulo n .) Observe que, para cada término que calculamos en la secuencia U , calculamos el término correspondiente en la secuencia V. A medida que avanzamos, calculamos también la misma, correspondientes potencias de Q .
En cada etapa, reducimos , , y el poder de , mod n .
Usamos los bits de la expansión binaria de n para determinar qué términos de la secuencia U calcular. Por ejemplo, si n +1 = 44 (= 101100 en binario), entonces, tomando los bits uno a la vez de izquierda a derecha, obtenemos la secuencia de índices para calcular: 1 2 = 1, 10 2 = 2, 100 2 = 4, 101 2 = 5, 1010 2 = 10, 1011 2 = 11, 10110 2 = 22, 101100 2 = 44. Por lo tanto, calculamos U 1 , U 2 , U 4 , U 5 , U 10 , U 11 , U 22 y U 44 . También calculamos los términos del mismo número en la secuencia V , junto con Q 1 , Q 2 , Q 4 , Q 5 , Q 10 , Q 11 , Q 22 y Q 44 .
Al final del cálculo, habremos calculado U n + 1 , V n + 1 y Q n + 1 , (mod n ). Luego verificamos la congruencia ( 2 ) usando nuestro valor conocido de U n + 1 .
Cuando se eligen D , P y Q como se describió anteriormente, los primeros 10 pseudoprimos de Lucas son (consulte la página 1401 de [1] ): 323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179 y 10877 ( secuencia A217120 en la OEIS )
Las versiones fuertes de la prueba de Lucas se pueden implementar de manera similar.
Cuando se eligen D , P y Q como se describió anteriormente, los primeros 10 pseudoprimos de Lucas fuertes son: 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309 y 58519 (secuencia A217255 en el OEIS )
Para calcular una lista de pseudoprimas Lucas extra fuertes , establezca. Luego intente P = 3, 4, 5, 6, ..., hasta un valor de se encuentra de modo que el símbolo de Jacobi . Con este método para seleccionar D , P y Q , los primeros 10 pseudoprimes de Lucas extra fuertes son 989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059 y 72389 (secuencia A217719 en el OEIS )
Comprobación de condiciones de congruencia adicionales
Si hemos verificado que la congruencia ( 2 ) es verdadera, existen condiciones de congruencia adicionales que podemos verificar y que casi no tienen costo computacional adicional. Si n resulta ser compuesto, estas condiciones adicionales pueden ayudar a descubrir ese hecho.
Si n es un primo impar y, entonces tenemos lo siguiente (vea 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 prima probable de Lucas, es casi libre de verificar esta condición porque, como se señaló anteriormente, el valor de V n + 1 se calculó en el proceso de calcular U n + 1 .
Si la congruencia ( 2 ) o ( 3 ) es falsa, esto constituye una prueba de que n no es primo. Si ambas congruencias son verdaderas, entonces es incluso más probable que n sea primo que si hubiéramos comprobado solo la congruencia ( 2 ).
Si el método de Selfridge (arriba) para elegir D , P y Q resultó en establecer Q = −1, entonces podemos ajustar P y Q para que D ypermanecen sin cambios y P = Q = 5 (ver la secuencia de Lucas-Relaciones algebraicas ). Si usamos este método mejorado para elegir P y Q , entonces 913 = 11 · 83 es el único compuesto menor que 10 8 para el cual la congruencia ( 3 ) es verdadera (vea la página 1409 y la Tabla 6 de; [1] ). Cálculos más extensos muestran que, con este método de elegir D , P y Q , solo hay cinco números compuestos impares menores que 10 15 para los cuales la congruencia ( 3 ) es verdadera. [7]
Si , entonces se puede implementar una condición de congruencia adicional que implica muy pocos cálculos adicionales.
Recordar que se calcula durante el cálculo de , y podemos guardar fácilmente la potencia calculada previamente de , a saber, .
Si n es primo, entonces, según el criterio de Euler ,
- .
(Aquí, es el símbolo de Legendre ; si n es primo, es lo mismo que el símbolo de Jacobi).
Por lo tanto, si n es primo, debemos tener,
( 4 )
El símbolo de Jacobi en el lado derecho es fácil de calcular, por lo que esta congruencia es fácil de verificar. Si esta congruencia no se cumple, entonces n no puede ser primo. Siempre que MCD ( n, Q ) = 1, la prueba de congruencia ( 4 ) equivale a aumentar nuestra prueba de Lucas con una prueba de primalidad de Solovay-Strassen de "base Q" .
Las condiciones de congruencia adicionales que deben cumplirse si n es primo se describen en la Sección 6 de. [1] Si alguna de estas condiciones no se cumple, entonces hemos probado que n no es primo.
Comparación con la prueba de primaria de Miller-Rabin
k aplicaciones de la prueba de primalidad de Miller-Rabin declaran que un compuesto n es probablemente primo con una probabilidad como máximo (1/4) k .
Existe una estimación de probabilidad similar para la prueba de prima probable fuerte de Lucas. [8]
Aparte de dos excepciones triviales (ver más abajo), la fracción de pares ( P , Q ) (módulo n ) que declaran que un compuesto n es probablemente primo es como máximo (4/15).
Por lo tanto, k aplicaciones de la prueba fuerte de Lucas declararían que un compuesto n es probablemente primo con una probabilidad como máximo (4/15) k .
Hay dos excepciones triviales. Uno es n = 9. El otro es 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. Uno puede detectar rápidamente cuadrados perfectos usando el método de Newton para raíces cuadradas.
Al combinar una prueba de pseudoprime de Lucas con una prueba de primalidad de Fermat , digamos, a base 2, se pueden obtener pruebas probabilísticas muy poderosas para la primalidad, como la prueba 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 pseudoprime de Fibonacci es a menudo [2] : 264, [3] : 142, [4] : 127 definido como un número compuesto n no divisible por 5 para el cual la congruencia ( 1 ) se cumple con P = 1 y Q = −1 (pero n es). Según esta definición, los pseudoprimes de Fibonacci forman una secuencia:
- 323, 377, 1891, 3827, 4181, 5777, 6601, 6721, 8149, 10877, ... (secuencia A081264 en la OEIS ).
Las referencias de Anderson y Jacobsen a continuación utilizan 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 una pseudoprima de Fibonacci también sea una pseudoprima de Fermat 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 11 también siendo pseudoprimos de Fermat en base 2.
Si n es primo y MCD ( n , Q ) = 1, entonces también tenemos [1] : 1392
( 5 )
Esto conduce a una definición alternativa de pseudoprime de Fibonacci: [9] [10]
- un pseudoprime 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 los pseudoprimes de Fibonacci a formar una secuencia:
- 705, 2465, 2737, 3745, 4181, 5777, 6721, 10877, 13201, 15251, ... (secuencia A005845 en la OEIS ),
que también se conocen como pseudoprimes de Bruckman-Lucas . [4] : 129 Hoggatt y Bicknell estudiaron las propiedades de estos pseudoprimes en 1974. [11] Singmaster calculó estos pseudoprimes hasta 100000. [12] Jacobsen enumera todos los 111443 de estos pseudoprimes menos de 10 13 . [13]
Se ha demostrado que ni siquiera hay pseudoprimos de Fibonacci como se define en la ecuación (5). [14] [15] Sin embargo, incluso existen pseudoprimes de Fibonacci (secuencia A141137 en la OEIS ) bajo la primera definición dada por ( 1 ).
Un fuerte pseudoprime Fibonacci es un número compuesto n para el que la congruencia ( 5 ) se mantiene para Q = -1 y todo P . [16] Se deduce [16] : 460 que un entero compuesto impar n es un pseudoprime de Fibonacci fuerte si y solo si:
- n es un número de Carmichael
- 2 ( p + 1) | ( n - 1) o 2 ( p + 1) | ( n - p ) para cada primo p que divide n .
El ejemplo más pequeño de un pseudoprime de Fibonacci fuerte es 443372888629441 = 17 · 31 · 41 · 43 · 89 · 97 · 167 · 331.
Pell pseudoprimes
Un pseudoprime de Pell se puede definir como un número compuesto n para el cual la ecuación ( 1 ) anterior es verdadera con P = 2 y Q = −1; la secuencia U n es entonces la secuencia Pell . Los primeros pseudoprimes son entonces 35, 169, 385, 779, 899, 961, 1121, 1189, 2419, ...
Esto difiere de la definición en OEIS : A099011 que puede escribirse como:
con ( P , Q ) = (2, −1) nuevamente definiendo U n como la secuencia de Pell . Los primeros pseudoprimes 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
- ^ a b c d e f g h i j k l m Robert Baillie; Samuel S. Wagstaff, 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 . Señor 0583518 .
- ^ a b c d David Bressoud ; Stan Wagon (2000). Un curso de teoría de números computacionales . Nueva York: Key College Publishing en cooperación con Springer. ISBN 978-1-930190-10-8.
- ^ a b c Richard E. Crandall ; Carl Pomerance (2005). Números primos: una perspectiva computacional (2ª ed.). Springer-Verlag . ISBN 0-387-25282-7.
- ^ a b c Paulo Ribenboim (1996). El nuevo libro de registros de números primos . Springer-Verlag . ISBN 0-387-94457-5.
- ^ Carl Pomerance ; John L. Selfridge ; Samuel S. Wagstaff, Jr. (julio de 1980). "Los pseudoprimes a 25 · 10 9 " (PDF) . Matemáticas de la Computación . 35 (151): 1003–1026. doi : 10.1090 / S0025-5718-1980-0572872-7 . JSTOR 2006210 .
- ^ Jon Grantham (marzo de 2000). "Frobenius Pseudoprimes" . Matemáticas de la Computación . 70 (234): 873–891. doi : 10.1090 / S0025-5718-00-01197-2 . Señor 1680879 .
- ^ Robert Baillie; Andrew Fiori; Samuel S. Wagstaff, Jr. (julio de 2021). "Fortalecimiento de la prueba de primordialidad Baillie-PSW". Matemáticas de la Computación . 90 (330): 1931-1955. arXiv : 2006.14425 . doi : 10.1090 / mcom / 3616 .
- ^ F. Arnault (abril de 1997). "El teorema de Rabin-Monier para Lucas Pseudoprimes". Matemáticas de la Computación . 66 (218): 869–881. CiteSeerX 10.1.1.192.4789 . doi : 10.1090 / s0025-5718-97-00836-3 .
- ^ Adina Di Porto; Piero Filipponi (1989). "Más sobre los pseudoprimes de Fibonacci" (PDF) . Fibonacci Quarterly . 27 (3): 232–242.
- ^ Di Porto, Adina; Filipponi, Piero; Montolivo, Emilio (1990). "Sobre los pseudoprimes de Fibonacci generalizados". Fibonacci Quarterly . 28 : 347–354. CiteSeerX 10.1.1.388.4993 .
- ^ VE Hoggatt, Jr .; Marjorie Bicknell (septiembre de 1974). "Algunas congruencias de los números de Fibonacci Modulo a Prime p". Revista de Matemáticas . 47 (4): 210–214. doi : 10.2307 / 2689212 . JSTOR 2689212 .
- ^ David Singmaster (1983). "Algunos Lucas Pseudoprimes". Resúmenes Amer. Matemáticas. Soc . 4 (83T – 10–146): 197.
- ^ "Tablas y estadísticas de pseudoprime" . Consultado el 5 de mayo de 2019 .
- ^ PS Bruckman (1994). "Los pseudoprimes de Lucas son raros". Fibonacci Quarterly . 32 : 155-157.
- ^ Di Porto, Adina (1993). "Inexistencia de incluso pseudoprimes de Fibonacci del primer tipo". Fibonacci Quarterly . 31 : 173-177. CiteSeerX 10.1.1.376.2601 .
- ^ a b Müller, Winfried B .; Oswald, Alan (1993). "Primas probables y pseudoprimes generalizados de Fibonacci". En GE Bergum; et al. (eds.). Aplicaciones de los números de Fibonacci . 5 . Kluwer. págs. 459–464. doi : 10.1007 / 978-94-011-2058-6_45 .
enlaces externos
- Anderson, Peter G. Fibonacci Pseudoprimes, sus factores y sus puntos de entrada.
- Anderson, Peter G. Fibonacci Pseudoprimes under 2,217,967,487 y sus factores.
- Jacobsen, Dana Pseudoprime Estadísticas, tablas y datos (datos para Lucas, Strong Lucas, AES Lucas, ES Lucas pseudoprimes por debajo de 10 14 ; pseudoprimes de Fibonacci y Pell por debajo de 10 12 )
- Weisstein, Eric W. "Fibonacci Pseudoprime" . MathWorld .
- Weisstein, Eric W. "Lucas Pseudoprime" . MathWorld .
- Weisstein, Eric W. "Strong Lucas Pseudoprime" . MathWorld .
- Weisstein, Eric W. "Extra Strong Lucas Pseudoprime" . MathWorld .