La prova de Lucas-Lehmer és la prova de primalitat que fa servir el [[GIMPS]] (“Great"Great Internet Mersenne Prime Search”Search") per a localitzar nombre primers grans, i ha tingut èxit en la localització de molts del nombres primers més grans coneguts fina a la data.<ref>GIMPS Home Page. Frequently Asked Questions: General Questions: What are Mersenne primes? How are they useful? http://www.mersenne.org/faq.htm#what</ref> Es considera valuós per a trobar nombres primers molt grans perquè es considera que els nombres de Mersenne és més fàcil que siguin primers que no pas els nombres senars triats a l'atzar de la mateixa mida. Addicionalment, es considera que la prova és valuosa perquè es pot fer servir com a [[test de primalitat]] per a nombres molt grans en un temps accessible i (en contrast amb l'equivalent test ràpid de Pépin per a qualsevol [[nombre de Fermat]]) es pot provar en un espai de nombres de cerca gran i amb la forma requerida abans d'assolir el límits computacionals.