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.

Le test[modifier | modifier le code]

Le test de Lucas-Lehmer marche de la façon suivante : Soit Mp = 2p− 1 le nombre de Mersenne à tester (alors p est présumé premier, autrement Mp est composé). Définissons une suite {si} pour tous les 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 ssi

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

autrement, Mp est un composé. Le nombre sp − 2 mod Mp est appelé le « 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)