Test de Lucas-Lehmer
# 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}=\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

    $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^2$ log n log log n), donde n es la longitud del número.

