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

La prueba de Lucas-Lehmer consiste en lo siguiente: sea Mp = 2p− 1 el número de Mersenne a testear con p primo impar.

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