Test de Lucas-Lehmer
En matemáticas, la prueba de Lucas-Lehmer es una prueba que sirve para determinar si un determinado número de Mersenne Mp es primo. El test fue desarrollado por Edouard Lucas en 1878 y subsecuentemente mejorado por Derrick Henry Lehmer en la década de 1930.
El test
[editar]La prueba de Lucas-Lehmer consiste en lo siguiente: sea Mp = 2p− 1 el número de Mersenne a testear con p primo impar. Defínase la sucesión {si} para todo i ≥ 0 según:
Los primeros términos de esta sucesión son 4, 14, 194, 37634, ... (sucesión A003010 en OEIS). Entonces, Mp es primo si y sólo si
En otro caso, Mp es compuesto. El número sp − 2 mod Mp se llama residuo Lucas–Lehmer de p.
Una implementación que utilice el algoritmo de multiplicación rápida de Schönhage–Strassen, basado a su vez en la transformada rápida de Fourier, da al test de Lucas–Lehmer una complejidad de O(n2 log n log log n), donde n es la longitud del número.
Véase también
[editar]Referencias
[editar]- Richard Crandall y Carl Pomerance (2001). Prime Numbers: A Computational Perspective (1era edición edición). Springer. ISBN 0-387-94777-9. Section 4.2.1: The Lucas–Lehmer test, pp.167–170.
Enlaces externos
[editar]- Weisstein, Eric W. «Test de Lucas–Lehmer». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
- GIMPS (The Great Internet Mersenne Prime Search)
- Una demostración del test de Lucas–Lehmer
- Test de Lucas–Lehmer en MersenneWiki (Inglés)