Test de primalité de Lucas-Lehmer

Page d'aide sur l'homonymie Pour les articles homonymes, voir Lucas, Lehmer et Test de Lucas.

Le test de primalité de Lucas[1]-Lehmer[2] est une méthode pour tester la primalité d'un entier n, connaissant les facteurs premiers de n – 1.

Le test

Un entier n > 2 est premier si et seulement si il existe un entier a, strictement compris entre 1 et n, tel que

et, pour tout facteur premier[3] q de n – 1,