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 1856 [ cita requerida ] y posteriormente mejorada por Lucas en 1878 y Derrick Henry Lehmer en la década de 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 primacía de p se puede verificar de manera eficiente con un algoritmo simple como la división de prueba, ya que p es exponencialmente más pequeño que M p . Definir una secuenciapara todo i ≥ 0 por
Los primeros términos de esta secuencia son 4, 14, 194, 37634, ... (secuencia A003010 en la OEIS ). Entonces M p es primo si y solo si
El número s p - 2 mod M p se llama residuo Lucas-Lehmer de p . (Algunos autores establecen de forma 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) mod M si s == 0 devuelve PRIME si no devuelve COMPUESTO
Realizar mod M
en cada iteración asegura que todos los resultados intermedios sean como máximo p bits (de lo contrario, el número 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 ). El residuo de Lucas-Lehmer calculado con estos valores iniciales alternativos seguirá siendo cero si M p es un número 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 , generalmente indicado por 2/3 para abreviar. [1] Este valor inicial es igual a (2 p + 1) / 3, el número de Wagstaff con exponente p .
Los valores iniciales como 4, 10 y 2/3 son universales, es decir, son válidos para todos (o casi todos) p . Hay infinitos valores iniciales universales adicionales. [1] 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 usar si p = 3 (mod 4). [2] Este valor inicial se usó a menudo cuando era adecuado en la era de la computación manual, incluso por Lucas para probar M 127 primo. [3] 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) yp ≠ 5. [1]
El mismo autor también demostró 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 sif p = 5 o 7 (mod 8) yp ≠ 2, 5. [1]
La secuencia OEIS A123271 muestra ϵ (4, p ) para cada prima de Mersenne M p .
Complejidad del tiempo
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 usar la división. Por ejemplo,
916 mod 2 5 −1 | = | 1110010100 2 mod 2 5 −1 |
= | ((916 mod 2 5 ) + int (916 ÷ 2 5 )) mod 2 5 −1 | |
= | (10100 2 + 11100 2 ) mod 2 5 −1 | |
= | 110000 2 mod 2 5 −1 | |
= | (10000 2 + 1 2 ) mod 2 5 −1 | |
= | 10001 2 mod 2 5 −1 | |
= | 10001 2 | |
= | 17. |
Además, dado s × s
que nunca excederá M 2 <2 2p , esta técnica simple converge en una suma de 1 p- bit como máximo (y posiblemente un acarreo desde el p- ésimo bit al 1er 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 utilizado para elevar al cuadrado s en cada paso. El algoritmo simple de la "escuela primaria" para la multiplicación requiere O ( p 2 ) operaciones de nivel de bits o de palabra para elevar al cuadrado un número de p bits. Dado que esto sucede O ( p ) veces, la complejidad del tiempo 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 cuadrar un número de p bits. Esto reduce la complejidad a O ( p 2 log p log log p ) o Õ ( p 2 ). [4] Un algoritmo de multiplicación aún más eficiente, el algoritmo de Fürer , solo necesitaEs hora de multiplicar dos números de p bits.
En comparación, la prueba de primalidad aleatoria más eficiente para enteros generales, la prueba de primalidad de Miller-Rabin , requiere operaciones de bit O ( k n 2 log n log log n ) utilizando 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 la constante k , se encuentra en la misma clase de complejidad que la prueba de Lucas-Lehmer. Sin embargo, en la práctica, el costo de realizar muchas iteraciones y otras diferencias conduce a un peor rendimiento de Miller-Rabin. La prueba de primalidad determinista más eficiente para cualquier número de n dígitos, la prueba de primalidad AKS , requiere operaciones de bits Õ (n 6 ) en su variante más conocida y es extremadamente lenta incluso para valores relativamente pequeños.
Ejemplos de
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.
Dado que el valor final de s es 0, la conclusión es que M 3 es primo.
Por otro lado, 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
Dado que 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 simple que la prueba original dada por Lehmer. Recuerda la definición
El objetivo es demostrar que M p es primo si f
La secuencia es una relación de recurrencia con una solución de forma cerrada . Dejar y . Luego se sigue por inducción quepara todo yo :
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 primordial. Lo que sigue es una demostración sencilla que explota la teoría de grupos elementales dada por JW Bruce [5] según la relata Jason Wojciechowski. [6]
Suponer Luego
para algún entero k , entonces
Multiplicar por da
Por lo tanto,
Para una contradicción, suponga 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. De manera informal, [nota 1] seaser los enteros módulo q , y sea Multiplicación en Se define como
Claramente, esta multiplicación es cerrada, es decir, el producto de los números de X está en X en sí mismo . El tamaño de X se denota por
Dado que q > 2, se sigue que y se encuentran en X . [nota 2] El subconjunto de elementos en X con inversas forma un grupo, que se denota por X * y tiene tamañoUn elemento en X que no tiene una inversa es 0, entonces
Ahora y , entonces
en X . Luego, por la ecuación (1),
en X , y cuadrar ambos lados da
Por lo tanto se encuentra en X * y tiene inversaAdemás, el orden de divide sin emabargo , para que el orden no se divida Por 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, entonces
Esto produce la contradicción . Por lo tanto, es primordial.
Necesidad
En la otra dirección, el objetivo es mostrar que la primordialidad de implica . La siguiente prueba simplificada es de Öystein J. Rödseth. [7]
Desde por extraño , se deduce de las propiedades del símbolo de Legendre queEsto significa que 3 es un módulo cuadrático de no residuosSegún el criterio de Euler , esto equivale a
En contraste, 2 es un módulo de residuo cuadrático desde y entonces Esta vez, el criterio de Euler da
La combinación de estas dos relaciones de equivalencia produce
Dejar , y define X como antes como el anilloLuego, en el anillo X , se sigue que
donde la primera igualdad usa el teorema binomial en un campo finito , que es
- ,
y la segunda igualdad usa el pequeño teorema de Fermat , que es
para cualquier número entero a . El valor de fue elegido para que En consecuencia, esto se puede utilizar para calcular en el ring X como
Todo lo que queda es multiplicar ambos lados de esta ecuación por y use , lo que da
Desde es 0 en X , también es 0 módulo
Aplicaciones
La prueba de Lucas-Lehmer es la prueba de primalidad utilizada por Great Internet Mersenne Prime Search (GIMPS) para localizar números primos grandes. Esta búsqueda ha logrado localizar muchos de los números primos más grandes conocidos hasta la fecha. [8] La prueba se considera valiosa porque probablemente puede probar un gran conjunto de números muy grandes para determinar su primalidad en un período de tiempo asequible. Por el contrario, 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.
Ver también
- Conjetura de Mersenne
- Prueba de Lucas – Lehmer – Riesel
Notas
- ^ Formalmente, dejemos y .
- ^ Formalmente, y se encuentran en X . Por abuso del lenguaje y se identifican con sus imágenes en X bajo el homomorfismo de anillo natural dea X que envíaa T .
Referencias
- ↑ a b c d Jansen, BJH (2012). Primos de Mersenne y teoría del campo de clases (tesis doctoral). Universidad de Leiden. pag. iii . Consultado el 17 de diciembre de 2018 .
- ^ Robinson, Raphael M. (1954). "Números de Mersenne y Fermat" . Proc. Amer. Matemáticas. Soc . 5 : 842–846. doi : 10.1090 / S0002-9939-1954-0064787-4 .
- ^ Haworth, Guy (1990). Números de Mersenne (PDF) (Informe técnico). pag. 20 . Consultado el 17 de diciembre de 2018 .
- ^ Colquitt, WN; Welsh, L., Jr. (1991), "A New Mersenne Prime", Mathematics of Computation , 56 (194): 867–870, doi : 10.2307 / 2008415 ,
El uso de FFT acelera el tiempo asintótico para Lucas –Prueba de Lehmer para M p de operaciones de bit O ( p 3 ) a O ( p 2 log p log log p ).
- ^ 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 .
- ^ Jason Wojciechowski. Mersenne Primes, una introducción y descripción general . 2003.
- ^ 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.
- ^ Los premios récord "Top Ten" , las páginas principales
- 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. 167-170, ISBN 0-387-94777-9
enlaces externos
- Weisstein, Eric W. "Prueba de Lucas-Lehmer" . MathWorld .
- GIMPS (La gran búsqueda de Internet Mersenne Prime)
- Una prueba de la prueba de Lucas-Lehmer-Reix (para números de Fermat)
- Prueba de Lucas-Lehmer en MersenneWiki