Test de primalité de Lucas-Lehmer pour les nombres de Mersenne

Pour les articles homonymes, voir Lucas, Lehmer, Test de Lucas et Test de primalité de Lucas-Lehmer.

En mathématiques, le test de Lucas-Lehmer est un test de primalité pour les nombres de Mersenne. Le test fut originellement développé par Édouard Lucas en 1878 et amélioré de façon notable par Derrick Henry Lehmer dans les années 1930, grâce à son étude des suites de Lucas^[1],[2].

On définit par récurrence la suite d'entiers (s_i)_i≥0 par^[3] :

${\displaystyle s_{0}=4\quad {\rm {et}}\quad \forall i\in \mathbb {N} \quad s_{i+1}=s_{i}^{2}-2.}$

Les premiers termes de cette suite sont 4, 14, 194, etc. (suite A003010 de l'OEIS).

Soit p un nombre premier différent de 2. Le nombre de Mersenne M_p = 2^p – 1 est premier si et seulement si s_{p – 2} est divisible par M_p^[4].

Le nombre s_{p − 2} mod M_p est appelé le « résidu de Lucas-Lehmer » de p^[5].

• Le nombre de Mersenne M₃ = 7 est premier. Le test de Lucas-Lehmer le vérifie de la manière suivante. À partir de s₀ = 4, on calcule s_{3 − 2} = s₁ = 4² − 2 = 14 ≡ 0 mod 7. Puisque la valeur de s₁ mod 7 est 0, la conclusion est que M₃ est premier.
• En revanche, M₁₁ = 2 047 = 23 × 89 n'est pas premier. Encore une fois, s₀ = 4 mais on calcule maintenant, modulo 2 047, les termes successifs de la suite s jusqu'à l'indice 11 − 2 = 9 :
  • s₁ = 4² − 2 = 14
  • s₂ = 14² − 2 = 194
  • s₃ = 194² − 2 ≡ 788 mod 2 047
  • s₄ ≡ 788² − 2 ≡ 701 mod 2 047
  • s₅ ≡ 701² − 2 ≡ 119 mod 2 047
  • s₆ ≡ 119² − 2 ≡ 1 877 mod 2 047
  • s₇ ≡ 1 877² − 2 ≡ 240 mod 2 047
  • s₈ ≡ 240² − 2 ≡ 282 mod 2 047
  • s₉ ≡ 282² − 2 ≡ 1 736 mod 2 047

Puisque la valeur de s₉ mod 2 047 n'est pas 0, la conclusion est que M₁₁ = 2 047 n'est pas premier.

Remarque préliminaire : Si ${\displaystyle M_{q}=2^{q}-1}$ est premier, alors ${\displaystyle q}$ aussi. En effet, si ${\displaystyle d\mid q}$, alors ${\displaystyle 2^{d}-1\mid 2^{q}-1}$ car ${\displaystyle 2^{q}-1=(2^{d}-1)((2^{d})^{q/d-1}+(2^{d})^{q/d-2}+\dots +1)}$. Nous ne nous intéresserons donc qu'aux nombres de Mersenne ${\displaystyle M_{q}=2^{q}-1}$ pour ${\displaystyle q\geq 3}$ impair (le cas ${\displaystyle q=2}$ étant trivial).

La preuve qui va suivre utilise la théorie des corps finis et notamment le petit théorème de Fermat. Elle est inspirée de celle donnée dans l'ouvrage de Saux-Picard-Rannou^[6].

À partir de maintenant, que ${\displaystyle M_{q}}$ soit premier ou non, on va poser ${\displaystyle {\mathcal {A}}_{q}=(\mathbb {Z} /M_{q}\mathbb {Z} )[T]/(T^{2}-3)}$. On écrit ${\displaystyle {\sqrt {3}}}$ la classe de ${\displaystyle T}$, de sorte que ${\displaystyle T^{2}=3}$. Nous avons donc agrandi l'anneau ${\displaystyle \mathbb {Z} /M_{q}\mathbb {Z} }$ en un anneau contenant une racine carrée de 3.

On prouve tout d'abord la caractérisation suivante :

Théorème : Si ${\displaystyle q\geq 3}$ impair, alors ${\displaystyle M_{q}}$ est premier si et seulement si ${\displaystyle (2+{\sqrt {3}})^{2^{q-1}}=-1}$ dans ${\displaystyle {\mathcal {A}}_{q}}$.

Sa preuve est découpée en la condition nécessaire suivie de la condition suffisante. Elle est suivie de la preuve de la correction du test de Lucas-Lehmer, qui en découlera alors presque immédiatement.

Condition nécessaire à la primalité

On suppose que ${\displaystyle M_{q}}$ est premier.

Etude de carrés modulo ${\displaystyle M_{q}}$ :

D'une part, le nombre 3 n'est pas carré modulo ${\displaystyle M_{q}}$. En effet : comme ${\displaystyle q}$ est impair, ${\displaystyle (-1)^{q}=-1}$ donc ${\displaystyle 2^{q}=2[3]}$. Donc ${\displaystyle M_{q}=1[3]}$ est un carré donc, en écrivant ${\displaystyle p=M_{q}}$, on a ${\displaystyle ({\frac {p}{3}})=1}$ (voir le symbole de Legendre). Or, par le théorème de la réciprocité quadratique, ${\displaystyle ({\frac {3}{p}})=({\frac {p}{3}})(-1)^{{\frac {3-1}{2}}{\frac {M_{q}-1}{2}}}}$. Or, ${\displaystyle {\frac {M_{q}-1}{2}}={\frac {2^{q}-2}{2}}=2^{q-1}-1}$ est impair donc ${\displaystyle ({\frac {3}{p}})=-1}$.

On note la conséquence qui est que, si ${\displaystyle p=M_{q}}$ est premier, alors ${\displaystyle {3}^{\frac {p-1}{2}}=-1}$ d'où ${\displaystyle {\sqrt {3}}^{p-1}=-1}$.

D'autre part, le nombre 2 est carré modulo ${\displaystyle M_{q}}$. En effet : ${\displaystyle M_{q}=0[M_{q}]}$, donc ${\displaystyle 2^{q+1}=2[M_{q}]}$, et sachant que ${\displaystyle q}$ est impair, on écrit ${\displaystyle {\sqrt {2}}=2^{(q+1)/2}}$ qui est une racine de ${\displaystyle 2}$ dans ${\displaystyle \mathbb {Z} /M_{q}\mathbb {Z} }$. Une conséquence est que, quand ${\displaystyle M_{q}=p}$ est premier, on a ${\displaystyle {\sqrt {2}}^{M_{q}}={\sqrt {2}}}$.

Conclusion :

Si ${\displaystyle p=M_{q}}$ est premier, alors ${\displaystyle {\mathcal {A}}_{q}}$ est un corps donc on peut poser ${\displaystyle \rho ={\frac {1+{\sqrt {3}}}{\sqrt {2}}}}$ et ${\displaystyle \rho '={\frac {1-{\sqrt {3}}}{\sqrt {2}}}}$ son ${\displaystyle \mathbb {F} _{M_{q}}}$-conjugué. Alors ${\displaystyle \rho ^{2}=2+{\sqrt {3}}}$ et ${\displaystyle \rho \rho '=-1}$. Alors on est armés pour calculer ce qu'on voulait calculer : $${\displaystyle (2+{\sqrt {3}})^{2^{q-1}}=\rho ^{2^{q}}=\rho ^{M_{q}}\rho =\rho {\frac {1}{{\sqrt {2}}^{M_{q}}}}({\sqrt {3}}^{M_{q}}+1).}$$Mais ${\displaystyle {\sqrt {3}}^{M_{q}}=-{\sqrt {3}}}$, donc ${\displaystyle (2+{\sqrt {3}})^{2^{q-1}}=\rho {\frac {1-{\sqrt {3}}}{\sqrt {2}}}=\rho \rho '=-1}$. Cela conclut la condition nécessaire.

Condition suffisante à la primalité

Si ${\displaystyle p\mid M_{q}}$ est un facteur premier de ${\displaystyle M_{q}}$, alors ${\displaystyle p}$ divise ${\displaystyle 0}$ dans ${\displaystyle {\mathcal {A}}_{q}}$ donc n'est pas inversible donc il existe un idéal maximal de ${\displaystyle {\mathcal {A}}_{q}}$ contenant ${\displaystyle p}$ noté ${\displaystyle m}$ (${\displaystyle m}$ existe car c'est un anneau fini). On a ${\displaystyle p\in m}$ donc ${\displaystyle p=0}$ dans ${\displaystyle k:={\mathcal {A}}_{q}/m}$ donc ${\displaystyle k}$ est un corps de caractéristique ${\displaystyle p}$ (dès qu'un nombre premier est nul dans un corps, ça veut dire que ce corps l'a pour caractéristique). On pose ${\displaystyle \alpha =2+{\sqrt {3}}}$, ${\displaystyle \beta =2-{\sqrt {3}}}$. On a ${\displaystyle \alpha \beta =1}$. Or, ${\displaystyle \alpha ^{2^{q-1}}=-1\neq 1}$ car ${\displaystyle p}$ est impair car ${\displaystyle M_{q}}$ l'est. Donc l'ordre de ${\displaystyle \alpha }$ dans ${\displaystyle k^{\ast }}$ est exactement ${\displaystyle 2^{q}=M_{q}+1}$ (en effet, en mettant au carré, on voit que l'ordre est une puissance de 2, et en utilisant le fait que ${\displaystyle -1\neq 1[M_{q}]}$, ça ne peut pas être une puissance inférieure à ${\displaystyle 2^{q}}$).

On pose, dans ${\displaystyle k[X]}$, ${\displaystyle Q(X)=(X-\alpha )(X-\beta )=X^{2}-4X+1}$ qui est donc à coefficients dans ${\displaystyle \mathbb {F} _{p}\hookrightarrow k}$ (cette flèche signifie l'existence d'un morphisme d'inclusion). Donc ${\displaystyle Q}$ est invariant par le morphisme de Frobenius dans ${\displaystyle k}$ donc ses racines sont permutées par celui-ci, donc ${\displaystyle \alpha ^{p}=\alpha }$ ou ${\displaystyle \beta }$. Dans le cas où ${\displaystyle \alpha ^{p}=\alpha }$, on trouve que ${\displaystyle 2^{q}\mid p-1}$ vu son ordre ce qui est contradictoire car ${\displaystyle p-1<2^{q}}$. Ainsi, ${\displaystyle \alpha ^{p}=\beta =\alpha ^{-1}}$ donc ${\displaystyle 2^{q}\mid p+1=2^{q}}$ d'où l'égalité donc ${\displaystyle M_{q}}$ est premier. Cela conclut la condition suffisante.

Test de Lucas-Lehmer

Soit ${\displaystyle q\geq 3}$ impair fixé. On pose ${\displaystyle L_{0}=4\in \mathbb {Z} /M_{q}\mathbb {Z} }$ et, pour ${\displaystyle n\geq 0}$, ${\displaystyle L_{n+1}=L_{n}^{2}-2}$.

Nous allons prouver le théorème de Lucas-Lehmer : ${\displaystyle M_{q}}$ est premier si et seulement si ${\displaystyle L_{q-2}=0}$.

Comme éléments de ${\displaystyle {\mathcal {A}}_{q}}$, on pose ${\displaystyle \alpha =2+{\sqrt {3}}}$, ${\displaystyle \beta =2-{\sqrt {3}}}$, ${\displaystyle \alpha \beta =1}$. On montre par récurrence que ${\displaystyle L_{n}=\alpha ^{2^{n}}+\alpha ^{-2^{n}}}$. ${\displaystyle n=0}$ : ${\displaystyle L_{0}=4}$ et ${\displaystyle \alpha ^{1}+\beta ^{1}=4}$. Si ${\displaystyle n\geq 0}$, si ${\displaystyle L_{n}=\alpha ^{2^{n}}+\alpha ^{-2^{n}}}$, alors ${\displaystyle L_{n+1}=\alpha ^{2^{n+1}}+\alpha ^{-2^{n+1}}+2-2}$. Donc à présent : ${\displaystyle L_{q-2}=0}$ si et seulement si ${\displaystyle \alpha ^{2^{q-2}}=-\alpha ^{-2^{q-2}}}$ si et seulement si ${\displaystyle \alpha ^{2^{q-1}}=-1}$ donc si et seulement si ${\displaystyle M_{q}}$ est premier.

• Great Internet Mersenne Prime Search
• Prime95
• Test de Lucas-Lehmer-Riesel (en)

v · m Nombres premiers
Donnés par une formule	combinatoire factoriel (n!±1) primoriel (pn#±1) Euclide (pn#+1) polynomiale Pythagore (4n + 1) cubain (x3 − y3)/(x − y) quatrain (x4 + y4) exponentielle Fermat (22n + 1) Mersenne (2p – 1) Double de Mersenne (22p–1 –1) Pierpont (2u3v + 1) Carol ((2n – 1)2 – 2) Kynea ((2n + 1)2 – 2) Thebit (3·2n – 1) Wagstaff ((2p + 1)/3) Proth (k2n + 1) Cullen (n2n + 1) Woodall (n2n – 1) Mills (⌊A3n⌋)
Appartenant à une suite	Fibonacci Lucas Motzkin Bell Pell Perrin Newman-Shanks-Williams
Ayant une propriété remarquable	bon chanceux fortuné Higgs illégal Pillai Ramanujan régulier Stern super supersingulier Wall-Sun-Sun Wieferich Paire de Wieferich Wilson Wolstenholme
Ayant une propriété dépendant de la base	diédral palindrome Reimerp répunit (10n − 1)/9 permutable circulaire délicat tronquable minimal long unique Smarandache-Wellin partie entière de puissances de constante troncature de constante
Propriétés mettant en jeu plusieurs nombres	singleton Chen {p ; p+2 premier ou semi-premier} équilibré (faible, fort) {pn ; pn = (<, >) (pn–1 + pn+1)/2} Sophie Germain {p ; 2p + 1 premier} sûr {p ; (p – 1)/2 premier} n-uplet jumeaux (p, p + 2) cousins (p, p + 4) sexy (p, p + 6) triplet (p, p + 2 ou p + 4, p + 6) quadruplet (p, p + 2, p + 6, p + 8) quintuplet (p – 4, p, p + 2, p + 6, p + 8) ou (p, p + 2, p + 6, p + 8, p + 12) sextuplet (p – 4, p, p + 2, p + 6, p + 8, p + 12) suite progression arithmétique (p + an) chaîne de Cunningham (p, 2p ± 1, etc.)
Classement par taille	titanesque (1 000+ chiffres) gigantesque (10 000+) méga (1 000 000+) record
Généralisations (entier quadratique)	Eisenstein Gauss
Nombre composé	pseudo-premier presque premier semi-premier interpremier
Nombre connexe	probable (NPP)
Test de primalité	Crible d'Ératosthène Test de Fermat Test de Lucas-Lehmer Test de Lucas-Lehmer pour les nombres de Mersenne Test de Pépin Test de Miller-Rabbin Test de Solovay-Strassen Test AKS
Conjectures et théorèmes de théorie des nombres	Conjecture d'Agoh-Giuga Conjecture d'Artin Conjecture de Bateman-Horn Conjecture de Bouniakovski Conjecture de Brocard Conjecture de Cramér Conjecture de Dickson Conjecture d'Elliott-Halberstam Conjecture de Firoozbakht Conjecture de Goldbach forte faible Conjecture de Grimm Conjecture de Hardy-Littlewood première seconde Conjecture de Legendre Conjecture de Lemoine Conjecture des nombres premiers de Waring Conjecture d'Oppermann Conjecture de Polignac Conjecture de Redmond-Sun Fonction de compte des nombres premiers Formules pour les nombres premiers Hypothèse H de Schinzel Nouvelle conjecture de Mersenne Théorème de Green-Tao Théorème des nombres premiers Théorème de la progression arithmétique Théorème de Rosser Théorème de Vinogradov
Constantes liées aux nombres premiers	Constante de Brun Constante de Legendre Constante de Mills Constante des nombres premiers Constante de Copeland-Erdős
Prime Pages Liste de nombres premiers Liste de suites de nombres premiers

• Arithmétique et théorie des nombres