Test de primalité de Lucas-Lehmer

Modèle:Voir homonymes Le test de primalité de Lucas-Lehmer est une méthode pour tester la primalité d'un entier Modèle:Math, connaissant les facteurs premiers de Modèle:Math

Le test

Un entier Modèle:Math est premier si et seulement si il existe un entier Modèle:Math, strictement compris entre Modèle:Math et Modèle:Math, tel que

$a^{n-1}\equiv 1(\mathrm{mod}n)$

et, pour tout facteur premier Modèle:Math de Modèle:Math,

$a^{(n-1)/q}\equiv ̸1(\mathrm{mod}n).$

Exemple

Par exemple, prenons n = 2017, n – 1 = 2016 = 2Modèle:5×3Modèle:2×7.

a = 2 ne convient pas car 2Modèle:Exp ≡ 1 (mod n).

a = 3 non plus car 3Modèle:Exp ≡ 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 5Modèle:Exp) :

$5^{1008}\equiv -1\equiv ̸1(\mathrm{mod}n)\text{ et }{5}^{2016}\equiv (-1{)}^2\equiv 1(\mathrm{mod}n)$

$5^{672}\equiv 294\equiv ̸1(\mathrm{mod}n)$

$5^{288}\equiv -138\equiv ̸1(\mathrm{mod}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 Modèle:Lien, appelé certificat de Pratt, qui montre que le test de primalité est dans NP.

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)