Diferencia entre revisiones de «Test de Lucas-Lehmer»
Sin resumen de edición |
m Revertidos los cambios de 190.44.16.139 a la última edición de Alpertron |
||
Línea 43: | Línea 43: | ||
[[pl:Test Lucasa-Lehmera]] |
[[pl:Test Lucasa-Lehmera]] |
||
[[ru:Тест Люка — Лемера]] |
[[ru:Тест Люка — Лемера]] |
||
[[zh:卢卡斯-莱默检验法]] |
[[zh:卢卡斯-莱默检验法]] |
Revisión del 20:58 12 may 2010
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
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, ... (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.
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.
Véase también
Referencias
- 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.