Comprueba si un número de Mersenne es primo
En matemáticas , la prueba de Lucas-Lehmer ( LLT ) es una prueba de primalidad para los números de Mersenne . La prueba fue desarrollada originalmente por Édouard Lucas en 1878 [1] y posteriormente demostrada por Derrick Henry Lehmer en 1930.
La prueba
La prueba de Lucas-Lehmer funciona de la siguiente manera. Sea M p = 2 p − 1 el número de Mersenne para probar con p un primo impar . La primalidad de p se puede comprobar de manera eficiente con un algoritmo simple como la división de prueba ya que p es exponencialmente menor que M p . Defina una secuencia para todo i ≥ 0 mediante
Los primeros términos de esta sucesión son 4, 14, 194, 37634, ... (secuencia A003010 en la OEIS ). Entonces M p es primo si y sólo si
El número s p − 2 mod M p se denomina residuo de Lucas-Lehmer de p . (Algunos autores establecen de manera equivalente s 1 = 4 y prueban s p −1 mod M p ). En pseudocódigo , la prueba podría escribirse como
// Determinar si M p = 2 p − 1 es primo para p > 2 Lucas–Lehmer (p) var s = 4 var M = 2 p − 1 repetir p − 2 veces: s = ((s × s) − 2) módulo M si s == 0 devuelve PRIME de lo contrario devuelve COMPOSITE
Al ejecutar la operación mod M
en cada iteración se garantiza que todos los resultados intermedios tengan como máximo p bits (de lo contrario, la cantidad de bits se duplicaría en cada iteración). La misma estrategia se utiliza en la exponenciación modular .
Valores iniciales alternativos
Son posibles valores iniciales s 0 distintos de 4, por ejemplo 10, 52 y otros (secuencia A018844 en la OEIS ). [2] El residuo de Lucas-Lehmer calculado con estos valores iniciales alternativos seguirá siendo cero si M p es un primo de Mersenne. Sin embargo, los términos de la secuencia serán diferentes y un residuo de Lucas-Lehmer distinto de cero para M p no primo tendrá un valor numérico diferente del valor distinto de cero calculado cuando s 0 = 4.
También es posible utilizar el valor inicial (2 mod M p )(3 mod M p ) −1 , usualmente denotado por 2/3 para abreviar. [2] Este valor inicial es igual a (2 p + 1) /3, el número de Wagstaff con exponente p .
Valores iniciales como 4, 10 y 2/3 son universales, es decir, son válidos para todos (o casi todos) los p . Hay infinitos valores iniciales universales adicionales. [2] Sin embargo, algunos otros valores iniciales solo son válidos para un subconjunto de todos los p posibles , por ejemplo, s 0 = 3 se puede utilizar si p = 3 (mod 4). [3] Este valor inicial se utilizó a menudo cuando era adecuado en la era del cálculo manual, incluso por Lucas al demostrar que M 127 es primo. [4]
Los primeros términos de la secuencia son 3, 7, 47, ... (secuencia A001566 en la OEIS ).
Signo del penúltimo término
Si s p −2 = 0 mod M p entonces el penúltimo término es s p −3 = ± 2 ( p +1)/2 mod M p . El signo de este penúltimo término se llama símbolo de Lehmer ϵ( s 0 , p ).
En 2000 SY Gebre-Egziabher demostró que para el valor inicial 2/3 y para p ≠ 5 el signo es:
Es decir, ϵ(2/3, p ) = +1 si p = 1 (mod 4) y p ≠ 5. [2]
El mismo autor también demostró la conjetura de Woltman [5] de que los símbolos de Lehmer para los valores iniciales 4 y 10 cuando p no es 2 o 5 están relacionados por:
Es decir, ϵ(4, p ) × ϵ(10, p ) = 1 si p = 5 o 7 (mod 8) y p ≠ 2, 5. [2]
La secuencia OEIS A123271 muestra ϵ(4, p ) para cada primo de Mersenne M p .
Complejidad temporal
En el algoritmo escrito anteriormente, hay dos operaciones costosas durante cada iteración: la multiplicación s × s
y la mod M
operación . La mod M
operación se puede hacer particularmente eficiente en computadoras binarias estándar observando que
Esto dice que los n bits menos significativos de k más los bits restantes de k son equivalentes a k módulo 2 n −1. Esta equivalencia se puede utilizar repetidamente hasta que queden como máximo n bits. De esta manera, el resto después de dividir k por el número de Mersenne 2 n −1 se calcula sin utilizar la división. Por ejemplo,
Además, como s × s
nunca superará M 2 < 2 2p , esta sencilla técnica converge en una suma de 1 p bit como máximo (y posiblemente un acarreo del bit p al 1.º bit), lo que se puede hacer en tiempo lineal. Este algoritmo tiene un pequeño caso excepcional. Producirá 2 n −1 para un múltiplo del módulo en lugar del valor correcto de 0. Sin embargo, este caso es fácil de detectar y corregir.
Con el módulo fuera del camino, la complejidad asintótica del algoritmo solo depende del algoritmo de multiplicación usado para elevar al cuadrado s en cada paso. El algoritmo simple de "primaria" para la multiplicación requiere O ( p 2 ) operaciones a nivel de bit o a nivel de palabra para elevar al cuadrado un número de p -bit. Dado que esto sucede O( p ) veces, la complejidad temporal total es O( p 3 ). Un algoritmo de multiplicación más eficiente es el algoritmo de Schönhage-Strassen , que se basa en la transformada rápida de Fourier . Solo requiere O( p log p log log p ) tiempo para elevar al cuadrado un número de p -bit. Esto reduce la complejidad a O( p 2 log p log log p ) o Õ( p 2 ). [6] Un algoritmo de multiplicación aún más eficiente, el algoritmo de Fürer , solo necesita tiempo para multiplicar dos números de p -bit.
En comparación, la prueba de primalidad aleatoria más eficiente para números enteros generales, la prueba de primalidad de Miller-Rabin , requiere O( k n 2 log n log log n ) [ contradictorias ] operaciones de bits usando la multiplicación FFT para un número de n dígitos, donde k es el número de iteraciones y está relacionado con la tasa de error. Para k constante , esto está en la misma clase de complejidad que la prueba de Lucas-Lehmer. Sin embargo, en la práctica, el costo de hacer muchas iteraciones y otras diferencias conducen a un peor rendimiento para Miller-Rabin. [ aclaración necesaria ] La prueba de primalidad determinista más eficiente para cualquier número de n dígitos, la prueba de primalidad AKS , requiere Õ(n 6 ) operaciones de bits en su variante más conocida y es extremadamente lenta incluso para valores relativamente pequeños.
Ejemplos
El número de Mersenne M 3 = 2 3 −1 = 7 es primo. La prueba de Lucas-Lehmer lo verifica de la siguiente manera. Inicialmente, s se establece en 4 y luego se actualiza 3−2 = 1 vez:
- s ← ((4 × 4) − 2) mod 7 = 0.
Como el valor final de s es 0, la conclusión es que M 3 es primo.
Por otra parte, M 11 = 2047 = 23 × 89 no es primo. Nuevamente, s se establece en 4 pero ahora se actualiza 11−2 = 9 veces:
- s ← ((4 × 4) − 2) mod 2047 = 14
- s ← ((14 × 14) − 2) mod 2047 = 194
- s ← ((194 × 194) − 2) mod 2047 = 788
- s ← ((788 × 788) − 2) mod 2047 = 701
- s ← ((701 × 701) − 2) mod 2047 = 119
- s ← ((119 × 119) − 2) mod 2047 = 1877
- s ← ((1877 × 1877) − 2) mod 2047 = 240
- s ← ((240 × 240) − 2) mod 2047 = 282
- s ← ((282 × 282) − 2) mod 2047 = 1736
Como el valor final de s no es 0, la conclusión es que M 11 = 2047 no es primo. Aunque M 11 = 2047 tiene factores no triviales, la prueba de Lucas-Lehmer no da ninguna indicación sobre cuáles podrían ser.
Prueba de corrección
La prueba de corrección de esta prueba que se presenta aquí es más sencilla que la prueba original dada por Lehmer. Recordemos la definición
El objetivo es demostrar que M p es primo si y solo si
La sucesión es una relación de recurrencia con una solución de forma cerrada . Sea y . Por inducción se deduce que para todo i :
y
El último paso utiliza Esta forma cerrada se utiliza tanto en la prueba de suficiencia como en la prueba de necesidad.
Suficiencia
El objetivo es demostrar que implica que es primo. Lo que sigue es una prueba sencilla que aprovecha la teoría de grupos elemental propuesta por JW Bruce [7] y relatada por Jason Wojciechowski. [8]
Supongamos entonces
para algún entero k , entonces
Multiplicando por da
De este modo,
Para una contradicción, supongamos que M p es compuesto y sea q el factor primo más pequeño de M p . Los números de Mersenne son impares, por lo que q > 2. Sean los enteros módulo q , y sea La multiplicación en se define como
- [nota 1]
Claramente, esta multiplicación es cerrada, es decir, el producto de números de X está en X. El tamaño de X se denota por
Como q > 2, se deduce que y están en X . [nota 2] El subconjunto de elementos en X con inversas forma un grupo, que se denota por X * y tiene tamaño Un elemento en X que no tiene inversa es 0, por lo que
Ahora y , entonces
en X . Entonces por la ecuación (1),
en X , y elevando al cuadrado ambos lados se obtiene
Por lo tanto, se encuentra en X * y tiene inversa Además, el orden de divide Sin embargo , por lo que el orden no divide Por lo tanto, el orden es exactamente
El orden de un elemento es como máximo el orden (tamaño) del grupo, por lo que
Pero q es el factor primo más pequeño del compuesto , por lo que
Esto produce la contradicción . Por lo tanto, es primo.
Necesidad
En la otra dirección, el objetivo es demostrar que la primalidad de implica . La siguiente prueba simplificada es de Öystein J. Rödseth. [9]
Dado que para impar , se deduce de las propiedades del símbolo de Legendre que Esto significa que 3 es un residuo cuadrático módulo . Por el criterio de Euler , esto es equivalente a
Por el contrario, 2 es un residuo cuadrático módulo ya que y por lo tanto Esta vez, el criterio de Euler da
Combinando estas dos relaciones de equivalencia obtenemos
Sea , y definamos X como antes como el anillo. Entonces en el anillo X , se sigue que
donde la primera igualdad utiliza el Teorema del Binomio en un cuerpo finito , que es
- ,
y la segunda igualdad utiliza el pequeño teorema de Fermat , que es
para cualquier entero a . El valor de se eligió de modo que En consecuencia, esto se puede utilizar para calcular en el anillo X como
Todo lo que queda es multiplicar ambos lados de esta ecuación por y usar , lo que da
Como es 0 en X , también es 0 módulo
Aplicaciones
La prueba de Lucas-Lehmer es una de las principales pruebas de primalidad utilizadas por la Gran Búsqueda de Primos de Mersenne en Internet (GIMPS) para localizar primos grandes. Esta búsqueda ha logrado localizar con éxito muchos de los primos más grandes conocidos hasta la fecha. [10] La prueba se considera valiosa porque puede probar de manera demostrable la primalidad de un gran conjunto de números muy grandes en un tiempo razonable. En contraste, la prueba de Pépin, equivalentemente rápida , para cualquier número de Fermat solo se puede utilizar en un conjunto mucho más pequeño de números muy grandes antes de alcanzar los límites computacionales.
Véase también
Notas
- ^ Formalmente, sea y .
- ^ Formalmente, y están en X . Por abuso del lenguaje y se identifican con sus imágenes en X bajo el homomorfismo de anillo natural de a X que envía a T .
Referencias
- ^ Jaroma, John H. (2004). "Nota sobre la prueba de Lucas-Lehmer" (PDF) . Boletín de la Sociedad Matemática Irlandesa . 54 (2). Sociedad Matemática Irlandesa: 63. doi :10.33232/BIMS.0054.63.72. S2CID 16831811.
- ^ abcde Jansen, BJH (2012). Primos de Mersenne y teoría de cuerpos de clases (tesis doctoral). Universidad de Leiden. pp. iii–iv . Consultado el 17 de diciembre de 2018 .
- ^ Robinson, Raphael M. (1954). "Números de Mersenne y Fermat". Proc. Amer. Math. Soc . 5 (5): 842–846. doi : 10.1090/S0002-9939-1954-0064787-4 .
- ^ Haworth, Guy (1990). Números de Mersenne (PDF) (Informe técnico). p. 20. Consultado el 17 de diciembre de 2018 .
- ^ Lenstra, Jr., HW (13 de mayo de 2001). Buhler, J.; Niederreiter, H.; Pohst, ME (eds.). Conjetura de Woltman sobre la prueba de Lucas-Lehmer (PDF) . Algorithms and Number Theory. p. 20 . Consultado el 16 de octubre de 2024 .
- ^ Colquitt, WN; Welsh, L. Jr. (1991), "A New Mersenne Prime", Mathematics of Computation , 56 (194): 867–870, doi : 10.2307/2008415 , JSTOR 2008415,
El uso de la FFT acelera el tiempo asintótico para la prueba de Lucas-Lehmer para M
p
de O(
p
3
) a O(
p
2
log
p
log log
p
) operaciones de bit.
- ^ Bruce, JW (1993). "Una prueba realmente trivial de la prueba de Lucas-Lehmer". The American Mathematical Monthly . 100 (4): 370–371. doi :10.2307/2324959. JSTOR 2324959.
- ^ Jason Wojciechowski. Primos de Mersenne: introducción y descripción general. 2003.
- ^ Rödseth, Öystein J. (1994). "Una nota sobre pruebas de primalidad para N=h·2^n−1" (PDF) . BIT Numerical Mathematics . 34 (3): 451–454. doi :10.1007/BF01935653. S2CID 120438959. Archivado desde el original (PDF) el 6 de marzo de 2016.
- ^ Los diez mejores discos de la historia, The Prime Pages
Enlaces externos
- Weisstein, Eric W. "Prueba de Lucas-Lehmer". MundoMatemático .
- GIMPS (La gran búsqueda de Mersenne Prime en Internet)
- Una prueba de la prueba de Lucas-Lehmer-Reix (para números de Fermat)
- Prueba de Lucas-Lehmer en MersenneWiki