Test de primalité de Lucas-Lehmer
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
[modifier | modifier le code]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,
Exemple
[modifier | modifier le code]Par exemple, prenons n = 2017, n – 1 = 2016 = 25×32×7.
a = 2 ne convient pas car 2672 ≡ 1 (mod n).
a = 3 non plus car 31008 ≡ 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 524×3) :
Donc 2017 est premier.
Démonstration
[modifier | modifier le code]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
[modifier | modifier le code]En théorie de la complexité, ce test donne un certificat de primalité (en), appelé certificat de Pratt (en), qui montre que le test de primalité est dans NP[4].
Notes et références
[modifier | modifier le code]- Édouard Lucas, Théorie des nombres, t. 1, (lire en ligne), p. 441.
- (en) D. H. Lehmer, « Tests for primality by the converse of Fermat's theorem », Bull. Amer. Math. Soc., vol. 33, no 3, , p. 327-340 (lire en ligne).
- Optimisation par Lehmer 1927 de l'énoncé de Lucas 1891, qui testait sur tous les diviseurs non triviaux q de n – 1.
- (en) Vaughan Pratt, « Every prime has a succinct certificate », Siam J. Comput., vol. 4, no 3, , p. 214-220 (lire en ligne).
Articles connexes
[modifier | modifier le code]- 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)