Test de primalité de Lucas-Lehmer pour les nombres de Mersenne
# 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^,.$

## 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_3$ = 7 est premier. Le test de Lucas-Lehmer le vérifie de la manière suivante. À partir de $s_0$ = 4, on calcule $s_{3−2}$ = $s_1$ = $4^2$ − 2 = 14 ≡ 0 mod 7. Puisque la valeur de $s_1$ mod 7 est 0, la conclusion est que $M_3$ est premier.
* En revanche, $M_{11}$ = 2 047 = 23 × 89 n'est pas premier. Encore une fois, $s_0$ = 4 mais on calcule maintenant, modulo 2 047, les termes successifs de la suite s jusqu'à l'indice 11 − 2 = 9 :
   * $s_1$ = $4^2$ − 2 = 14
   * $s_2$ = $14^2$ − 2 = 194
   * $s_3$ = $194^2$ − 2 ≡ 788 mod 2 047
   * $s_4$ ≡ $788^2$ − 2 ≡ 701 mod 2 047
   * $s_5$ ≡ $701^2$ − 2 ≡ 119 mod 2 047
   * $s_6$ ≡ $119^2$ − 2 ≡ 1 877 mod 2 047
   * $s_7$ ≡ 1 $877^2$ − 2 ≡ 240 mod 2 047
   * $s_8$ ≡ $240^2$ − 2 ≡ 282 mod 2 047
   * $s_9$ ≡ $282^2$ − 2 ≡ 1 736 mod 2 047

Puisque la valeur de $s_9$ mod 2 047 n'est pas 0, la conclusion est que $M_{11}$ = 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 3e 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$.

