Test de primalité de Lucas-Lehmer

test de primalité

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

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

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

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

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
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Lucas primality test » (voir la liste des auteurs).
  1. Édouard Lucas, Théorie des nombres, t. 1, (lire en ligne), p. 441.
  2. (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).
  3. Optimisation par Lehmer 1927 de l'énoncé de Lucas 1891, qui testait sur tous les diviseurs non triviaux q de n – 1.
  4. (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