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

Extrait de la p. 316 du mémoire Théorie des fonctions numériques simplement périodiques d'Édouard Lucas (1878).

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 LucasModèle:,.

Théorème

On définit par récurrence la suite d'entiers (sModèle:Ind)_i≥0 par :

$s_0=4\mathrm{e}\mathrm{t}\mathrm{\forall }i\in \mathbb{N}{s}_{i+1}=s_i^2-2.$

Les premiers termes de cette suite sont 4, 14, 194Modèle:Etc. (Modèle:OEIS).

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

Exemples

• Le nombre de Mersenne M₃ = 7 est premier. Le test de Lucas-Lehmer le vérifie de la manière suivante. À partir de sModèle:Ind = 4, on calcule sModèle:Ind = sModèle:Ind = 4Modèle:2 − 2 = 14 ≡ 0 mod 7. Puisque la valeur de sModèle:Ind mod 7 est 0, la conclusion est que M₃ est premier.
• En revanche, M₁₁ = Modèle:Nombre = 23 × 89 n'est pas premier. Encore une fois, sModèle:Ind = 4 mais on calcule maintenant, modulo Modèle:Nombre, les termes successifs de la suite s jusqu'à l'indice 11 − 2 = 9 :
  • sModèle:Ind = 4Modèle:2 − 2 = 14
  • sModèle:Ind = 14Modèle:2 − 2 = 194
  • sModèle:Ind = 194Modèle:2 − 2 ≡ 788 mod Modèle:Nombre
  • sModèle:Ind ≡ 788Modèle:2 − 2 ≡ 701 mod Modèle:Nombre
  • sModèle:Ind ≡ 701Modèle:2 − 2 ≡ 119 mod Modèle:Nombre
  • sModèle:Ind ≡ 119Modèle:2 − 2 ≡ Modèle:Nombre mod Modèle:Nombre
  • sModèle:Ind ≡ Modèle:NombreModèle:2 − 2 ≡ 240 mod Modèle:Nombre
  • sModèle:Ind ≡ 240Modèle:2 − 2 ≡ 282 mod Modèle:Nombre
  • sModèle:Ind ≡ 282Modèle:2 − 2 ≡ Modèle:Nombre mod Modèle:Nombre

Puisque la valeur de sModèle:Ind mod Modèle:Nombre n'est pas 0, la conclusion est que M₁₁ = Modèle:Nombre n'est pas premier.

Preuve

Remarque préliminaire : Si $M_q=2^q-1$ est premier, alors $q$ aussi. En effet, si $d\mid q$, alors $2^d-1\mid 2^q-1$ car $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 $M_q=2^q-1$ pour $q\ge 3$ impair (le cas $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.

À partir de maintenant, que $M_q$ soit premier ou non, on va poser ${𝒜}_q=(\mathbb{Z}/M_q\mathbb{Z})[T]/(T^2-3)$. On écrit $\sqrt{3}$ la classe de $T$, de sorte que $T^2=3$. Nous avons donc agrandi l'anneau $\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 $q\ge 3$ impair, alors $M_q$ est premier si et seulement si $(2+\sqrt{3}{)}^{2^{q-1}}=-1$ dans ${𝒜}_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 $M_q$ est premier.

Etude de carrés modulo $M_q$ :

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

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

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

Conclusion :

Si $p=M_q$ est premier, alors ${𝒜}_q$ est un corps donc on peut poser $\rho =\frac{1+\sqrt{3}}{\sqrt{2}}$ et ${\rho }^{\prime }=\frac{1-\sqrt{3}}{\sqrt{2}}$ son ${𝔽}_{M_q}$-conjugué. Alors ${\rho }^2=2+\sqrt{3}$ et $\rho {\rho }^{\prime }=-1$. Alors on est armés pour calculer ce qu'on voulait calculer : $$(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 ${\sqrt{3}}^{M_q}=-\sqrt{3}$, donc $(2+\sqrt{3}{)}^{2^{q-1}}=\rho \frac{1-\sqrt{3}}{\sqrt{2}}=\rho {\rho }^{\prime }=-1$. Cela conclut la condition nécessaire.

Condition suffisante à la primalité

Si $p\mid M_q$ est un facteur premier de $M_q$, alors $p$ divise $0$ dans ${𝒜}_q$ donc n'est pas inversible donc il existe un idéal maximal de ${𝒜}_q$ contenant $p$ noté $m$ ($m$ existe car c'est un anneau fini). On a $p\in m$ donc $p=0$ dans $k:={𝒜}_q/m$ donc $k$ est un corps de caractéristique $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 $\alpha =2+\sqrt{3}$, $\beta =2-\sqrt{3}$. On a $\alpha \beta =1$. Or, ${\alpha }^{2^{q-1}}=-1\ne 1$ car $p$ est impair car $M_q$ l'est. Donc l'ordre de $\alpha$ dans $k^{\ast }$ est exactement $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 $-1\ne 1[M_q]$, ça ne peut pas être une puissance inférieure à $2^q$).

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

Test de Lucas-Lehmer

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

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

Comme éléments de ${𝒜}_q$, on pose $\alpha =2+\sqrt{3}$, $\beta =2-\sqrt{3}$, $\alpha \beta =1$. On montre par récurrence que $L_n={\alpha }^{2^n}+{\alpha }^{-2^n}$. $n=0$ : $L_0=4$ et ${\alpha }^1+{\beta }^1=4$. Si $n\ge 0$, si $L_n={\alpha }^{2^n}+{\alpha }^{-2^n}$, alors $L_{n+1}={\alpha }^{2^{n+1}}+{\alpha }^{-2^{n+1}}+2-2$. Donc à présent : $L_{q-2}=0$ si et seulement si ${\alpha }^{2^{q-2}}=-{\alpha }^{-2^{q-2}}$ si et seulement si ${\alpha }^{2^{q-1}}=-1$ donc si et seulement si $M_q$ est premier.

Articles connexes

• Great Internet Mersenne Prime Search
• Prime95
• Modèle:Lien