Prueba de primalidad de Lucas-Lehmer

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 ${\displaystyle \{s_{i}\}}$

${\displaystyle s_{i}={\begin{cases}4&{\text{if }}i=0;\\s_{i-1}^{2}-2&{\text{otherwise.}}\end{cases}}}$

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

${\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}.}$

El número s _{p  − 2}  mod  M _p se denomina residuo de Lucas-Lehmer de p . (Algunos autores establecen de manera equivalente s ₁  = 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 Men 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 ₀ 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 ₀  = 4.

También es posible utilizar el valor inicial (2 mod  M _p )(3 mod  M _p ) ⁻¹ , 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 ₀  = 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 ₁₂₇ 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 ₀ ,  p ).

En 2000 SY Gebre-Egziabher demostró que para el valor inicial 2/3 y para p  ≠ 5 el signo es:

${\displaystyle \epsilon ({2 \over 3},\ p)=(-1)^{p-1 \over 2}}$

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:

${\displaystyle \epsilon (10,\ p)=\epsilon (4,\ p)\ \times \ (-1)^{{(p+1)(p+3)} \over 8}}$

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 × sy la mod Moperación . La mod Moperación se puede hacer particularmente eficiente en computadoras binarias estándar observando que

${\displaystyle k\equiv (k\,{\bmod {\,}}2^{n})+\lfloor k/2^{n}\rfloor {\pmod {2^{n}-1}}.}$

Esto dice que los n bits menos significativos de k más los bits restantes de k son equivalentes a k módulo 2 ⁿ −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 ⁿ −1 se calcula sin utilizar la división. Por ejemplo,

Además, como s × snunca superará M ² < 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 ⁿ −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 ² ) 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 ³ ). 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 ² log p log log p ) o Õ( p ² ). ^[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. ${\displaystyle p\log p\ 2^{O(\log ^{*}p)}}$

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 ² 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 ⁶ ) 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 ₃ = 2 ³ −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 ₃ es primo.

Por otra parte, M ₁₁  = 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 ₁₁  = 2047 no es primo. Aunque M ₁₁  = 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

${\displaystyle s_{i}={\begin{cases}4&{\text{if }}i=0;\\s_{i-1}^{2}-2&{\text{otherwise.}}\end{cases}}}$

El objetivo es demostrar que M _p es primo si y solo si ${\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}.}$

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 : ${\displaystyle {\langle }s_{i}{\rangle }}$ ${\displaystyle \omega =2+{\sqrt {3}}}$ ${\displaystyle {\bar {\omega }}=2-{\sqrt {3}}}$ ${\displaystyle s_{i}=\omega ^{2^{i}}+{\bar {\omega }}^{2^{i}}}$

${\displaystyle s_{0}=\omega ^{2^{0}}+{\bar {\omega }}^{2^{0}}=\left(2+{\sqrt {3}}\right)+\left(2-{\sqrt {3}}\right)=4}$

y

${\displaystyle {\begin{aligned}s_{n}&=s_{n-1}^{2}-2\\&=\left(\omega ^{2^{n-1}}+{\bar {\omega }}^{2^{n-1}}\right)^{2}-2\\&=\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}}+2(\omega {\bar {\omega }})^{2^{n-1}}-2\\&=\omega ^{2^{n}}+{\bar {\omega }}^{2^{n}}.\end{aligned}}}$

El último paso utiliza Esta forma cerrada se utiliza tanto en la prueba de suficiencia como en la prueba de necesidad. ${\displaystyle \omega {\bar {\omega }}=\left(2+{\sqrt {3}}\right)\left(2-{\sqrt {3}}\right)=1.}$

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] ${\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}$ ${\displaystyle M_{p}}$

Supongamos entonces ${\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}.}$

${\displaystyle \omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=kM_{p}}$

para algún entero k , entonces

${\displaystyle \omega ^{2^{p-2}}=kM_{p}-{\bar {\omega }}^{2^{p-2}}.}$

Multiplicando por da ${\displaystyle \omega ^{2^{p-2}}}$

${\displaystyle \left(\omega ^{2^{p-2}}\right)^{2}=kM_{p}\omega ^{2^{p-2}}-(\omega {\bar {\omega }})^{2^{p-2}}.}$

De este modo,

${\displaystyle \omega ^{2^{p-1}}=kM_{p}\omega ^{2^{p-2}}-1.\qquad \qquad (1)}$

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 ${\displaystyle \mathbb {Z} _{q}}$ ${\displaystyle X=\left\{a+b{\sqrt {3}}\mid a,b\in \mathbb {Z} _{q}\right\}.}$ ${\displaystyle X}$

${\displaystyle \left(a+{\sqrt {3}}b\right)\left(c+{\sqrt {3}}d\right)=[(ac+3bd)\,{\bmod {\,}}q]+{\sqrt {3}}[(ad+bc)\,{\bmod {\,}}q].}$^{[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 ${\displaystyle |X|.}$

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 ${\displaystyle \omega }$ ${\displaystyle {\bar {\omega }}}$ ${\displaystyle |X^{*}|.}$ ${\displaystyle |X^{*}|\leq |X|-1=q^{2}-1.}$

Ahora y , entonces ${\displaystyle M_{p}\equiv 0{\pmod {q}}}$ ${\displaystyle \omega \in X}$

${\displaystyle kM_{p}\omega ^{2^{p-2}}=0}$

en X . Entonces por la ecuación (1),

${\displaystyle \omega ^{2^{p-1}}=-1}$

en X , y elevando al cuadrado ambos lados se obtiene

${\displaystyle \omega ^{2^{p}}=1.}$

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 ${\displaystyle \omega }$ ${\displaystyle \omega ^{2^{p}-1}.}$ ${\displaystyle \omega }$ ${\displaystyle 2^{p}.}$ ${\displaystyle \omega ^{2^{p-1}}\neq 1}$ ${\displaystyle 2^{p-1}.}$ ${\displaystyle 2^{p}.}$

El orden de un elemento es como máximo el orden (tamaño) del grupo, por lo que

${\displaystyle 2^{p}\leq |X^{*}|\leq q^{2}-1<q^{2}.}$

Pero q es el factor primo más pequeño del compuesto , por lo que ${\displaystyle M_{p}}$

${\displaystyle q^{2}\leq M_{p}=2^{p}-1.}$

Esto produce la contradicción . Por lo tanto, es primo. ${\displaystyle 2^{p}<2^{p}-1}$ ${\displaystyle M_{p}}$

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] ${\displaystyle M_{p}}$ ${\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}$

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 ${\displaystyle 2^{p}-1\equiv 7{\pmod {12}}}$ ${\displaystyle p>1}$ ${\displaystyle (3|M_{p})=-1.}$ ${\displaystyle M_{p}.}$

${\displaystyle 3^{\frac {M_{p}-1}{2}}\equiv -1{\pmod {M_{p}}}.}$

Por el contrario, 2 es un residuo cuadrático módulo ya que y por lo tanto Esta vez, el criterio de Euler da ${\displaystyle M_{p}}$ ${\displaystyle 2^{p}\equiv 1{\pmod {M_{p}}}}$ ${\displaystyle 2\equiv 2^{p+1}=\left(2^{\frac {p+1}{2}}\right)^{2}{\pmod {M_{p}}}.}$

${\displaystyle 2^{\frac {M_{p}-1}{2}}\equiv 1{\pmod {M_{p}}}.}$

Combinando estas dos relaciones de equivalencia obtenemos

${\displaystyle 24^{\frac {M_{p}-1}{2}}\equiv \left(2^{\frac {M_{p}-1}{2}}\right)^{3}\left(3^{\frac {M_{p}-1}{2}}\right)\equiv (1)^{3}(-1)\equiv -1{\pmod {M_{p}}}.}$

Sea , y definamos X como antes como el anillo. Entonces en el anillo X , se sigue que ${\displaystyle \sigma =2{\sqrt {3}}}$ ${\displaystyle X=\{a+b{\sqrt {3}}\mid a,b\in \mathbb {Z} _{M_{p}}\}.}$

${\displaystyle {\begin{aligned}(6+\sigma )^{M_{p}}&=6^{M_{p}}+\left(2^{M_{p}}\right)\left({\sqrt {3}}^{M_{p}}\right)\\&=6+2\left(3^{\frac {M_{p}-1}{2}}\right){\sqrt {3}}\\&=6+2(-1){\sqrt {3}}\\&=6-\sigma ,\end{aligned}}}$

donde la primera igualdad utiliza el Teorema del Binomio en un cuerpo finito , que es

${\displaystyle (x+y)^{M_{p}}\equiv x^{M_{p}}+y^{M_{p}}{\pmod {M_{p}}}}$,

y la segunda igualdad utiliza el pequeño teorema de Fermat , que es

${\displaystyle a^{M_{p}}\equiv a{\pmod {M_{p}}}}$

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 ${\displaystyle \sigma }$ ${\displaystyle \omega ={\frac {(6+\sigma )^{2}}{24}}.}$ ${\displaystyle \omega ^{\frac {M_{p}+1}{2}}}$

${\displaystyle {\begin{aligned}\omega ^{\frac {M_{p}+1}{2}}&={\frac {(6+\sigma )^{M_{p}+1}}{24^{\frac {M_{p}+1}{2}}}}\\&={\frac {(6+\sigma )(6+\sigma )^{M_{p}}}{24\cdot 24^{\frac {M_{p}-1}{2}}}}\\&={\frac {(6+\sigma )(6-\sigma )}{-24}}\\&=-1.\end{aligned}}}$

Todo lo que queda es multiplicar ambos lados de esta ecuación por y usar , lo que da ${\displaystyle {\bar {\omega }}^{\frac {M_{p}+1}{4}}}$ ${\displaystyle \omega {\bar {\omega }}=1}$

${\displaystyle {\begin{aligned}\omega ^{\frac {M_{p}+1}{2}}{\bar {\omega }}^{\frac {M_{p}+1}{4}}&=-{\bar {\omega }}^{\frac {M_{p}+1}{4}}\\\omega ^{\frac {M_{p}+1}{4}}+{\bar {\omega }}^{\frac {M_{p}+1}{4}}&=0\\\omega ^{\frac {2^{p}-1+1}{4}}+{\bar {\omega }}^{\frac {2^{p}-1+1}{4}}&=0\\\omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}&=0\\s_{p-2}&=0.\end{aligned}}}$

Como es 0 en X , también es 0 módulo ${\displaystyle s_{p-2}}$ ${\displaystyle M_{p}.}$

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

• Conjetura de Mersenne
• Prueba de Lucas-Lehmer-Riesel

Notas

1. Formalmente, sea y . ${\displaystyle \mathbb {Z} _{q}=\mathbb {Z} /q\mathbb {Z} }$ ${\displaystyle X=\mathbb {Z} _{q}[T]/\langle T^{2}-3\rangle }$
2. 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 . ${\displaystyle \omega +\langle T^{2}-3\rangle }$ ${\displaystyle {\bar {\omega }}+\langle T^{2}-3\rangle }$ ${\displaystyle \omega }$ ${\displaystyle {\bar {\omega }}}$ ${\displaystyle \mathbb {Z} [{\sqrt {3}}]}$ ${\displaystyle {\sqrt {3}}}$

Referencias

1. 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.
2. 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 .
3. 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 .
4. Haworth, Guy (1990). Números de Mersenne (PDF) (Informe técnico). p. 20. Consultado el 17 de diciembre de 2018 .
5. 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 .
6. 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 ³ ) a O( p ² log p log log p ) operaciones de bit.
7. 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.
8. Jason Wojciechowski. Primos de Mersenne: introducción y descripción general. 2003.
9. 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.
10. Los diez mejores discos de la historia, The Prime Pages

• Crandall, Richard ; Pomerance, Carl (2001), "Sección 4.2.1: La prueba de Lucas-Lehmer", Números primos: una perspectiva computacional (1.ª ed.), Berlín: Springer, págs. 167-170, ISBN 0-387-94777-9

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