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

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

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

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

${\displaystyle a^{({n-1})/q}\not \equiv 1{\pmod {n}}.}$

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^24×3) :

${\displaystyle 5^{1008}\equiv -1\not \equiv 1{\pmod {n}}{\text{ et }}5^{2016}\equiv (-1)^{2}\equiv 1{\pmod {n}}}$

${\displaystyle 5^{672}\equiv 294\not \equiv 1{\pmod {n}}}$

${\displaystyle 5^{288}\equiv -138\not \equiv 1{\pmod {n}}}$

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 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

(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, 1891 (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, n^o 3,‎ 1927, 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, n^o 3,‎ 1975, p. 214-220 (lire en ligne).

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)

• Arithmétique et théorie des nombres