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

{{#ifeq:||Un article de Ziki, l'encyclopédie libre.|Une page de Ziki, l'encyclopédie libre.}}
  1. REDIRECT Modèle:Voir homonymes
Fichier:LucasTheorieDesFonctions1878.png
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 Lucas<ref>Modèle:Article.</ref>,<ref>Modèle:Article.</ref>.

Théorème

On définit par récurrence la suite d'entiers (si)i≥0 par<ref>Cette suite est décalée dans les articles originaux de Lehmer et dans Modèle:Lien web et Modèle:Ouvrage : si = Si+1 avec S1 = 4 et Modèle:Nobr La condition s'écrit alors : Sp – 1 est divisible par Mp.</ref> :

<math>s_0=4\quad{\rm et}\quad\forall i\in\N\quad s_{i+1}=s_i^2-2.</math>

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

Modèle:Énoncé

Le nombre sp − 2 mod Mp est appelé le « résidu de Lucas-Lehmer » de p<ref>Modèle:MathWorld.</ref>.

Exemples

  • Le nombre de Mersenne M3 = 7 est premier. Le test de Lucas-Lehmer le vérifie de la manière suivante. À partir de s0 = 4, on calcule s3 − 2 = s1 = 42 − 2 = 14 ≡ 0 mod 7. Puisque la valeur de s1 mod 7 est 0, la conclusion est que M3 est premier.
  • En revanche, M11 = Modèle:Nombre = 23 × 89 n'est pas premier. Encore une fois, s0 = 4 mais on calcule maintenant, modulo Modèle:Nombre, les termes successifs de la suite s jusqu'à l'indice 11 − 2 = 9 :

Puisque la valeur de s9 mod Modèle:Nombre n'est pas 0, la conclusion est que M11 = Modèle:Nombre n'est pas premier.

Preuve

Ce test a été montré en 1932 par A. E. Western en se plaçant dans le corps ℚ(√3)<ref>Modèle:Article.</ref>. Modèle:Section travail inédit On a besoin de <math> 3^{2^{p-1}-1} \equiv -1 \bmod 2^p -1</math> si <math>2^p -1</math> est premier<ref>Modèle:Article</ref>, un cas simple de réciprocité quadratique.

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

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

  • Si <math>2^p -1</math> est premier on a <math>(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</math> donc
<math>(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)</math>
Notons que (1) est vrai si et seulement si <math>S_{p-2} = (2-\sqrt{3})^{2^{p-2}}\left((2+\sqrt{3})^{2^{p-1}} +1\right) \equiv 0 \bmod 2^p-1 </math> où <math>S_0 = 4,\,S_{n+1} = S_n^2-2=(2+\sqrt{3})^{2^{n+1}}+(2-\sqrt{3})^{2^{n+1}}</math>.
  • Maintenant on suppose que (1) est vrai mais que <math>2^p-1</math> n'est pas premier. Soit <math>q</math> son plus petit facteur premier, si bien que <math>q^2 \le 2^p-1</math>. On obtient
<math>(1) \implies (2+\sqrt{3})^{2^{p-1}} \equiv -1 \bmod q</math>
<math>2^{p}</math> est donc l'ordre de <math>2+\sqrt{3}</math> dans le groupe multiplicatif <math>\mathbb{Z}_q[\sqrt{3}]^\times</math>. Mais ce groupe a <math>r</math> éléments où <math>r \le q^2-1</math>. On aurait donc
<math>(2+\sqrt{3})^{r} \equiv 1 \bmod q</math>
une contradiction puisque <math>r \le q^2-1 < 2^p</math>.

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

Notes et références

Modèle:Traduction/Référence Modèle:Références

Articles connexes

Modèle:Palette Modèle:Portail