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

Un article de Wikipédia, l'encyclopédie libre.

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.

[modifier] Le test

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\ \,&&\mbox{si }i=0;\ \ \, \\ s_{i-1}^2-2&&\mbox{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 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.

[modifier] Voir aussi

[modifier] Liens externes