En 1.878 Édouard Lucas propuso dos pruebas para comprobar los números primos de Mersenne pero no realizó ninguna prueba completa. En 1.930 D. H. Lehmer demostró una condición necesaria y suficiente para que N fuese primo, siendo a partir de este momento que a dicha prueba se la denomina de Lucas-Lehmer. Tiene un orden de complejidad O(p3).
