Test de primalité de Lucas-Lehmer

1. REDIRECT Modèle:Voir homonymes

Le test de primalité de Lucas<ref>Modèle:Ouvrage.</ref>-Lehmer<ref>Modèle:Article.</ref> 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

<math>a^{n-1}\equiv1\pmod n</math>

et, pour tout facteur premier<ref>Optimisation par Modèle:Harvsp de l'énoncé de Modèle:Harvsp, qui testait sur tous les diviseurs non triviaux Modèle:Math de Modèle:Math.</ref> Modèle:Math de Modèle:Math,

<math>a^{({n-1})/q}\not\equiv1\pmod n.</math>

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

<math>5^{1008}\equiv-1\not\equiv1\pmod n\text{ et }5^{2016}\equiv(-1)^2\equiv1\pmod n</math>

<math>5^{672}\equiv294\not\equiv1\pmod n</math>

<math>5^{288}\equiv-138\not\equiv1\pmod n</math>

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 Modèle:Lien, qui montre que le test de primalité est dans NP<ref>Modèle:Article.</ref>.

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)