En matemáticas, la prueba de Lucas – Lehmer – Riesel es una prueba de primalidad para números de la forma N = k ⋅ 2 n - 1, con k <2 n . La prueba fue desarrollada por Hans Riesel y se basa en la prueba de primalidad de Lucas-Lehmer . Es el algoritmo determinista más rápido conocido para números de esa forma. [ cita requerida ] Para números de la forma N = k ⋅ 2 n + 1 ( números de Proth ), la aplicación del teorema de Proth (un algoritmo de Las Vegas) o una de las pruebas deterministas descritas en Brillhart-Lehmer-Selfridge 1975 [1] .
El algoritmo
El algoritmo es muy similar a la prueba de Lucas-Lehmer , pero con un punto de partida variable en función del valor de k .
Defina una secuencia u i para todo i > 0 mediante:
Entonces N es primo si y solo si divide a u n −2 .
Encontrar el valor inicial
El valor inicial u 0 se determina como sigue.
- Si k = 1: si n es impar, entonces podemos tomar u 0 = 4. Si n ≡ 3 (mod 4), entonces podemos tomar u 0 = 3. Note que si n es primo, estos son números de Mersenne .
- Si k = 3: si n ≡ 0 o 3 (mod 4), entonces u 0 = 5778.
- Si k ≡ 1 o 5 (mod 6): si 3 no divide N , entonces tomamos. Vea a continuación cómo calcular esto usando una secuencia de Lucas (4,1).
- De lo contrario, estamos en el caso en el que k es un múltiplo de 3 y es más difícil seleccionar el valor correcto de u 0 .
Un método alternativo para encontrar el valor inicial u 0 se da en Rödseth 1994. [2] El método de selección es mucho más fácil que el usado por Riesel para el caso de k 3 divisiones . Primero encuentre un valor de P que satisfaga las siguientes igualdades de los símbolos de Jacobi :
- .
En la práctica, solo es necesario verificar unos pocos valores de P antes de encontrar uno (5, 8, 9 u 11 funcionan en aproximadamente el 85% de los ensayos). [ cita requerida ]
Para encontrar el valor inicial u 0 a partir del valor P , podemos usar una secuencia de Lucas (P, 1), como se muestra en [2] así como en la página 124 de. [3] Este último explica que cuando 3 ∤ k , se puede usar P = 4, por lo tanto, la búsqueda anterior no es necesaria. El valor inicial u 0 es entonces igual a la modular Lucas secuencia V k ( P , 1) mod N . Este proceso lleva muy poco tiempo en comparación con la prueba principal.
Cómo funciona la prueba
La prueba de Lucas-Lehmer-Riesel es un caso particular de prueba de primalidad de orden de grupo; demostramos que algún número es primo mostrando que algún grupo tiene el orden que tendría si ese número es primo, y lo hacemos encontrando un elemento de ese grupo precisamente en el orden correcto.
Para las pruebas de estilo Lucas en un número N , trabajamos en el grupo multiplicativo de una extensión cuadrática de los números enteros módulo N ; si N es primo, el orden de este grupo multiplicativo es N 2 - 1, tiene un subgrupo de orden N + 1, y tratamos de encontrar un generador para ese subgrupo.
Comenzamos tratando de encontrar una expresión no iterativa para el . Siguiendo el modelo de la prueba de Lucas-Lehmer, coloque, y por inducción tenemos .
Así que podemos considerarnos como buscar en la 2 i ésimo término de la sucesión. Si a satisface una ecuación cuadrática, esta es una secuencia de Lucas y tiene una expresión de la forma. Realmente, estamos viendo el k ⋅ 2 i- ésimo término de una secuencia diferente, pero dado que las diezmaciones (tome cada k- ésimo término comenzando con cero) de una secuencia de Lucas son en sí mismas secuencias de Lucas, podemos lidiar con el factor k por eligiendo un punto de partida diferente.
Software LLR
LLR es un programa que puede ejecutar las pruebas LLR. El programa fue desarrollado por Jean Penné . Vincent Penné ha modificado el programa para que pueda obtener pruebas a través de Internet. [ cita requerida ] El software es utilizado tanto por buscadores principales individuales como por algunos proyectos de computación distribuida , incluidos Riesel Sieve y PrimeGrid .
Ver también
Referencias
- ^ Brillhart, John ; Lehmer, Derrick Henry ; Selfridge, John (abril de 1975). "Nuevos criterios de primacía y factorizaciones de 2 ^ m ± 1" . Matemáticas de la Computación . 29 (130): 620–647. doi : 10.1090 / S0025-5718-1975-0384673-1 .
- ^ a b Rödseth, Öystein J. (1994). "Una nota sobre las pruebas de primalidad para N = h · 2 ^ n − 1" (PDF) . BIT Matemáticas numéricas . 34 (3): 451–454. doi : 10.1007 / BF01935653 . Archivado desde el original (PDF) el 6 de marzo de 2016.
- ^ Riesel, Hans (1994). Números primos y métodos informáticos de factorización . Progreso en Matemáticas. 126 (2ª ed.). Birkhäuser. págs. 107-121. ISBN 0-8176-3743-5.
- Riesel, Hans (1969). "Criterios de Lucas para la primacía de N = h · 2 n - 1". Matemáticas de la Computación . Sociedad Matemática Estadounidense. 23 (108): 869–875. doi : 10.2307 / 2004975 . JSTOR 2004975 .
enlaces externos
- Descarga el LLR de Jean Penné
- Math :: Prime :: Util :: GMP : parte del módulo ntheory de Perl, tiene implementaciones básicas de pruebas de formularios LLR y Proth, así como algunos métodos de prueba BLS75.