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

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.

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

Théorème

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

$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.

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

Preuve

Ce test a été montré en 1932 par A. E. Western en se plaçant dans le corps ℚ(√3).

On a besoin de $3^{2^{p-1}-1}\equiv -1{\bmod {2}}^{p}-1$ si $2^{p}-1$ est premier, un cas simple de réciprocité quadratique.

On se place dans l'anneau $\mathbb {Z} _{2^{p}-1}[{\sqrt {3}}]=\{a+b{\sqrt {3}}{\bmod {2}}^{p}-1\}$.

Puisque $p\mid 2^{p-1}-1$ on a $2^{2^{p-1}-1}\equiv 1{\bmod {2}}^{p}-1$. Par ailleurs $2+{\sqrt {3}}={\frac {1}{2-{\sqrt {3}}}}={\frac {(2\times 3+2{\sqrt {3}})^{2}}{3\times 2^{3}}}$.

• Si $2^{p}-1$ est premier on a $(2\times 3+2{\sqrt {3}})^{2^{p}-1}\!\!\!\!\!{\underset {\scriptstyle {\text{(formule du binôme)}}}{\equiv }}\!\!\!\!\!(2\times 3)^{2^{p}-1}+\underbrace {(2{\sqrt {3}})^{2^{p}-1}} _{{\sqrt {3}}2^{2^{p}-1}3^{2^{p-1}-1}}\equiv 2\times 3-2{\sqrt {3}}{\bmod {2}}^{p}-1$ donc

$(2+{\sqrt {3}})^{2^{p-1}}={\frac {(2\times 3+2{\sqrt {3}})^{2^{p}}}{(3\times 2^{3})^{2^{p-1}}}}\equiv {\frac {(2\times 3+2{\sqrt {3}})(2\times 3-2{\sqrt {3}})}{-3\times 2^{3}}}\equiv -1{\bmod {2}}^{p}-1\qquad \qquad (1)$

Notons que (1) est vrai si et seulement si $S_{p-2}=(2-{\sqrt {3}})^{2^{p-2}}\left((2+{\sqrt {3}})^{2^{p-1}}+1\right)\equiv 0{\bmod {2}}^{p}-1$ où $S_{0}=4,\,S_{n+1}=S_{n}^{2}-2=(2+{\sqrt {3}})^{2^{n+1}}+(2-{\sqrt {3}})^{2^{n+1}}$.

• Maintenant on suppose que (1) est vrai mais que $2^{p}-1$ n'est pas premier. Soit $q$ son plus petit facteur premier, si bien que $q^{2}\leq 2^{p}-1$. On obtient

$(1)\implies (2+{\sqrt {3}})^{2^{p-1}}\equiv -1{\bmod {q}}$

$2^{p}$ est donc l'ordre de $2+{\sqrt {3}}$ dans le groupe multiplicatif $\mathbb {Z} _{q}[{\sqrt {3}}]^{\times }$. Mais ce groupe a $r$ éléments où $r\leq q^{2}-1$. On aurait donc

$(2+{\sqrt {3}})^{r}\equiv 1{\bmod {q}}$

une contradiction puisque $r\leq q^{2}-1<2^{p}$.

Finalement on se place dans l'anneau $\mathbb {Z} _{2^{p}-1}[\mathrm {i} ,{\sqrt {3}}]$ qui contient la racine 3^e de l'unité $\zeta _{3}=-{\frac {1}{2}}+\mathrm {i} {\frac {\sqrt {3}}{2}}$ qui vérifie $\zeta _{3}-\zeta _{3}^{2}=\mathrm {i} {\sqrt {3}}$ si bien que si $2^{p}-1$ est premier $-\mathrm {i} {\sqrt {3}}\,3^{2^{p-1}-1}=(\zeta _{3}-\zeta _{3}^{2})^{2^{p}-1}\equiv \zeta _{3}^{2^{p}-1}-\zeta _{3}^{2(2^{p}-1)}\equiv \zeta _{3}-\zeta _{3}^{2}\equiv \mathrm {i} {\sqrt {3}}{\bmod {2}}^{p}-1$ et on a donc bien $3^{2^{p-1}-1}\equiv -1{\bmod {2}}^{p}-1$.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Lucas–Lehmer primality test » (voir la liste des auteurs).

Articles connexes

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