Test de primalite 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.

Le test

Le test de Lucas-Lehmer marche de la façon suivante : Soit M_p = 2^p− 1 le nombre de Mersenne à tester (alors p est présumé premier, autrement M_p est composé). Définissons une suite {s_i} pour tous les i ≥ 0 par

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

Les premiers petits termes de cette suite sont 4, 14, 194, 37634, ... (suite A003010 dans l'encyclopédie électronique des suites entières). Alors M_p est premier ssi

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

autrement, M_p est un composé. Le nombre s_{p − 2} mod M_p est appelé le résidu de Lucas-Lehmer de p.

Voir aussi

• Test de primalité de Lucas-Lehmer

Liens externes

• (en) MathWorld : le test de Lucas-Lehmer
• (en) GIMPS : The Great Internet Mersenne Prime Search (la grande recherche internet du nombre premier de Mersenne)
• (en) Une démonstration du test de Lucas-Lehmer

Ce document provient de « Test de primalit%C3%A9 de Lucas-Lehmer pour les nombres de Mersenne ».