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 M_p es primo. El test fue desarrollado por Edouard Lucas en 1878 y subsecuentemente mejorado por Derrick Henry Lehmer en la década de 1930.

La prueba de Lucas-Lehmer consiste en lo siguiente: sea M_p = 2^p− 1 el número de Mersenne a testear con p primo impar. Defínase la sucesión {s_i} para todo i ≥ 0 según:

${\displaystyle s_{i}=\left\{{\begin{matrix}4,\qquad \ \,&&{\mbox{si }}i=0;\ \ \,\\s_{i-1}^{2}-2&&{\mbox{en caso contrario.}}\end{matrix}}\right.}$

Los primeros términos de esta sucesión son 4, 14, 194, 37634, ... (sucesión A003010 en OEIS). Entonces, M_p es primo si y sólo si

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

En otro caso, M_p es compuesto. El número s_{p − 2} mod M_p 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(n² log n log log n), donde n es la longitud del número.

• Test de Lucas
• Conjetura de Mersenne

• 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.

• 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)