Test de Lucas-Lehmer para números de Mersenne
De Wikipedia, la enciclopedia libre
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.
Tabla de contenidos |
[editar] El test
La prueba de Lucas-Lehmer consiste en lo siguiente: sea Mp = 2p− 1 el número de Mersenne a testear con p primo. 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, ... secuencia A003010 en OEIS. Entonces, Mp es primo sii
En otro caso, Mp es compuesto. El número sp − 2 mod Mp se llama residuo Lucas–Lehmer de p.
Con una implementación FFT, el test de Lucas–Lehmer tiene una complejidad de O(n2 log n), donde es la longitud del número.
[editar] Véase también
- Test de Lucas-Lehmer
- Conjetura de Mersenne
[editar] Referencias
- Richard Crandall y Carl Pomerance (2001). Prime Numbers: A Computational Perspective, 1era edición, Springer. ISBN 0387947779. Section 4.2.1: The Lucas–Lehmer test, pp.167–170.
