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

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

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

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

Exemple[modifier | modifier le code]

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

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

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

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

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]

(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).

↑ Édouard Lucas, Théorie des nombres, t. 1, 1891 (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, n^o 3,‎ 1927, 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, n^o 3,‎ 1975, 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)

Arithmétique et théorie des nombres

[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).

[1]

[2]

[3]

[4]