Le test de primalité de Lucas.-Lehmer. est une méthode pour tester la primalité d'un entier , connaissant les facteurs premiers de .
Le test Un entier est premier si et seulement si il existe un entier , strictement compris entre et , tel que
et, pour tout facteur premierOptimisation par de l'énoncé de , qui testait sur tous les diviseurs non triviaux de . de ,
Exemple
Par exemple, prenons n = 2017, n – 1 = 2016 = 2×3×7.
a = 2 ne convient pas car 2 ≡ 1 (mod n).
a = 3 non plus car 3 ≡ 1 (mod n)
Essayons a = 5 (pour calculer rapidement mod n les puissances voulues, on peut utiliser la méthode d'exponentiation rapide et de plus, calculer d'abord 5) :
Donc 2017 est premier.
Démonstration La première condition signifie que a est inversible modulo n et que son ordre multiplicatif est un diviseur de n – 1. La seconde signifie que cet ordre est exactement n – 1 (et non un diviseur strict). Par conséquent, l'ordre du groupe des inversibles de l'anneau ℤ/nℤ — qui est a priori inférieur ou égal à n – 1 — est divisible par n – 1 donc égal à n – 1, ce qui signifie que n est premier.
Réciproquement, si n est premier, alors il existe φ(n – 1) racines primitives modulo n, et n'importe laquelle satisfera toutes les conditions du test.
Utilisation En théorie de la complexité, ce test donne un , appelé certificat de Pratt, qui montre que le test de primalité est dans NP..
Notes et références
Articles connexes Suite de Lucas Test de primalité de Fermat Test de primalité de Lucas-Lehmer pour les nombres de Mersenne Théorème de Pocklington (une double généralisation du test, où a n'est pas nécessairement le même pour chaque q, et où une factorisation partielle de n – 1 suffit)
Lucas-Lehmer