Prueba de Luc-Lehmer-Riesel

La prueba de Lucas-Lehmer-Riesel ( LLR ) es una prueba de primalidad para números de la forma c (un subconjunto de tales números se llama números Sabit ). Desarrollado por Hans Riesel y basado en la prueba de Luc-Lehmer , es el algoritmo determinista más rápido para números de este tipo [1] . $N=k\cdot 2^{n}-1$ $2^{n}>k$ $3\cdot 2^{n}-1$

Algoritmo

El algoritmo es muy similar a la prueba de Luc-Lehmer, pero comienza con un valor que depende de . Para el algoritmo se utiliza la sucesión de Lucas , la cual viene dada por la fórmula: $k$ ${\ estilo de visualización \ {u_ {i} \}}$ ${\ estilo de visualización i> 0}$

u_{i}=u_{i-1}^{2}-2

$norte$ es primo si y solo si divide a . ${\ Displaystyle u_ {n-2}}$

Encontrar un valor inicial

caso _ Si — es impar, entonces se toma el valor . Si , entonces se toma . Para una simple , estos son los números de Mersenne . $k=1$ $norte$ $tu_{0}=4$ $n\equiv 3{\pmod {4}}$ $tu_{0}=3$ $norte$
caso _ El valor se puede utilizar para todo n ≡ 0,3 (mod 4). $k = 3$ $u_{0}=5778$ $n\equiv 0.3{\pmod {4}}$
Si y no es divisible por 3, se puede usar el valor . $k\equiv 1.5{\pmod {6}}$ $norte$ $u_{0}=(2+{\raíz cuadrada {3}})^{k}+(2-{\raíz cuadrada {3}})^{k}$
En otros casos, es divisible por 3, y elegir el valor inicial correcto u 0 es mucho más difícil. $k$

En 1994 [2] se proporcionó un método alternativo para encontrar el valor inicial . El método es mucho más simple que el usado por Riesel para el caso cuando 3 divide . En el método alternativo, primero encuentre el valor que satisfaga la siguiente igualdad del símbolo de Jacobi : $tu_{0}$ $k$ $PAGS$

\left({\frac{P-2}{N}}\right)=1

y .

\left({\frac{P+2}{N}}\right)=-1

En la práctica, solo es necesario verificar algunos valores (5, 8, 9 u 11 cubren el 85 %). $PAGS$

Para obtener el valor inicial , puede usar la secuencia de Lucas [ 2] [3] . Para 3 ∤ k (k no es divisible por 3), se puede usar el valor y no se necesita una búsqueda preliminar. El valor inicial es entonces igual al módulo de la secuencia de Lucas . Este proceso lleva muy poco tiempo en comparación con la prueba principal. $tu_{0}$ $PAGS$ ${\ estilo de visualización (P, 1)}$ ${\ estilo de visualización P = 4}$ $tu_{0}$ ${\ Displaystyle V_ {k} (P, 1)}$ $norte$

Mecanismo de la prueba

La prueba de Luc-Lehmer-Riesel es un caso especial de verificación de la simplicidad del orden de un grupo. La prueba muestra que cierto número es primo debido a que cierto grupo tiene un orden que sería igual a ese número primo, por lo que se identifica un elemento del grupo que tiene exactamente el orden deseado.

Pruebas como las pruebas de Luke usan el grupo multiplicativo de la expansión del módulo cuadrático de enteros para un número . Si es primo, el orden del grupo multiplicativo es , y tiene un subgrupo de orden , para efectos de la prueba se busca el conjunto generador de este subgrupo. $norte$ $norte$ $norte$ ${\ estilo de visualización N^{2}-1}$ $N+1$

Puede encontrar una expresión no iterativa para . Siguiendo el modelo de prueba de Lucas-Lehmer, establecemos y obtenemos por inducción . $tu_{yo}$ $u_{i}=a^{{2^{i}}}+a^{{-2^{i}}}$ $u_{i}=u_{{i-1}}^{2}-2$

Considere el 2 i -ésimo elemento de la secuencia . Si a satisface una ecuación cuadrática, es una sucesión de Lucas y obedece a la expresión . En realidad estamos buscando el -ésimo elemento de otra secuencia, pero dado que diezmar (seleccionar cada k -ésimo elemento) de la secuencia de Lucas también produce una secuencia de Lucas, podemos elegir el factor k eligiendo un punto de partida. $v(i)=a^{i}+a^{{-i}}$ $v(i)=\alfa v(i-1)+\beta v(i-2)$ $k\veces 2^{i}$

Programa LLR

LLR es un programa que realiza una prueba LLR. El programa fue desarrollado por Jean Penné. Vincent Penné modificó el programa para que puedas comprobar la primacía de un número a través de Internet. El programa se puede utilizar tanto para búsquedas individuales, como también se incluye en algunos proyectos de computación distribuida como Riesel Sieve y PrimeGrid .

Véase también

numeros riesel

Notas

↑ Para probar la primalidad de los números de Proth similares a estos , se usa el Teorema de Proth ( algoritmo probabilístico ) o uno de los algoritmos deterministas descritos por Brilhart, Lehmer y Selfridge en 1975 - véase Brillhart, Lehmer, Selfridge, 1975 $N=k\cdot 2^{n}+1$
↑ 1 2 Rodset, 1994 .
↑ Riesel, 1994 , pág. 194.

Literatura

Hans Riesel. Criterios Lucasianos para la Primalidad de N = h •2 n − 1 // Matemáticas de Computación. - Sociedad Matemática Americana, 1969. - V. 23 , no. 108 . - S. 869-875 . -doi : 10.2307/ 2004975 . — .
John Brillhart, Derrick Henry Lehmer, John Selfridge. Nuevos Criterios de Primalidad y Factorizaciones de 2^m ± 1 // Matemáticas de Computación. - 1975. - vol. 29.- Emisión. 130 . - S. 620-647 . -doi : 10.1090/ S0025-5718-1975-0384673-1 .
Öystein J. Rodseth. Una nota sobre las pruebas de primacía para N=h•2^n−1 // BIT Numerical Mathematics. - 1994. - T. 34 , núm. 3 . - S. 451-454 . -doi : 10.1007/ BF01935653 . Archivado desde el original el 4 de marzo de 2016.
Hans Riesel. Números primos y métodos informáticos de factorización. — 2do. - Birkhäuser, 1994. - T. 126. - S. 107-121. — (Progreso en Matemáticas). — ISBN 0-8176-3743-5 .

Enlaces

Descargar LLR de Jean Penne
Math::Prime::Util::GMP — Módulo Perl, implementación básica de la prueba LLR y Prot, y algunos métodos del artículo de Brilhart, Lemaire y Selfridge.