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

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Lucas, Lehmer et Test de Lucas.
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.

Théorème[modifier | modifier le code]

Soit Mp = 2p− 1, le nombre de Mersenne à tester. Si p n'est pas premier, Mp est composé. On suppose donc p premier. On définit la suite la suite (si)i≥0 par :


  s_i=
  \left\{
   \begin{matrix}
    4,\qquad\ \,&&\text{si }i=0;\ \ \,
   \\
    s_{i-1}^2-2&&\text{sinon.}
   \end{matrix}
  \right.

Les premiers termes de cette suite sont 4, 14, 194, 37634 (suite A003010 de l'OEIS). Alors Mp est premier si et seulement si :

s_{p-2}\equiv0\ (M_p) (congruence modulo Mp).

Le nombre sp − 2 mod Mp est appelé résidu de Lucas-Lehmer de p.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

(en) Eric W. Weisstein, « Lucas-Lehmer Test », MathWorld


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