Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] \| Liste Catégories \| Une page au hasard \| Pages liées

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 Edouard Lucas en 1878 et amélioré de façon conséquente 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\ \,&&\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 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

This site support the Wikimedia Foundation. This Article originally from Wikipedia. All text is available under the terms of the