Test de Lucas-Lehmer

Fragmento en francés del 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.

El test

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:

$s_i=\{\begin{array}{ccc}4,& & \text{si }i=0;\\ s_{i-1}^2-2& & \text{en caso contrario.}\end{array}$

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

$s_{p-2}\equiv 0(\mathrm{mod}{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.

Véase también

• Test de Lucas
• Conjetura de Mersenne

Referencias

• Plantilla:Cita libro Section 4.2.1: The Lucas–Lehmer test, pp.167–170.

Enlaces externos

• Plantilla:MathWorld
• GIMPS (The Great Internet Mersenne Prime Search)
• Una demostración del test de Lucas–Lehmer
• Test de Lucas–Lehmer en MersenneWiki (Inglés)