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

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.

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

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

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

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

• Si ${\displaystyle 2^{p}-1}$ est premier on a ${\displaystyle (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

${\displaystyle (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 ${\displaystyle 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ù ${\displaystyle 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 ${\displaystyle 2^{p}-1}$ n'est pas premier. Soit ${\displaystyle q}$ son plus petit facteur premier, si bien que ${\displaystyle q^{2}\leq 2^{p}-1}$. On obtient

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

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

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

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

Finalement on se place dans l'anneau ${\displaystyle \mathbb {Z} _{2^{p}-1}[\mathrm {i} ,{\sqrt {3}}]}$ qui contient la racine 3^e de l'unité ${\displaystyle \zeta _{3}=-{\frac {1}{2}}+\mathrm {i} {\frac {\sqrt {3}}{2}}}$ qui vérifie ${\displaystyle \zeta _{3}-\zeta _{3}^{2}=\mathrm {i} {\sqrt {3}}}$ si bien que si ${\displaystyle 2^{p}-1}$ est premier ${\displaystyle -\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 ${\displaystyle 3^{2^{p-1}-1}\equiv -1{\bmod {2}}^{p}-1}$.

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