Test de primalite de Lucas-Lehmer pour les nombres de Mersenne


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 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{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.

Voir aussi

Liens externes

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Test de primalit%C3%A9 de Lucas-Lehmer pour les nombres de Mersenne ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Test de primalite de Lucas-Lehmer pour les nombres de Mersenne de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • 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 …   Wikipédia en Français

  • Test de primalité de Lucas-Lehmer pour les nombres de Mersenne — Pour les articles homonymes, voir Lucas et Lehmer. 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… …   Wikipédia en Français

  • Test de primalite de Lucas-Lehmer — Test de primalité de Lucas Lehmer Le test de primalité de Lucas Lehmer est une méthode pour tester la primalité de certains nombres n ; il requiert que les facteurs premiers de n 1 soient connus. S il existe un a inférieur à n et plus grand… …   Wikipédia en Français

  • Test de primalité de lucas-lehmer — Le test de primalité de Lucas Lehmer est une méthode pour tester la primalité de certains nombres n ; il requiert que les facteurs premiers de n 1 soient connus. S il existe un a inférieur à n et plus grand que 1 tel que et, pour tous les… …   Wikipédia en Français

  • Test de primalité de Lucas-Lehmer — Pour les articles homonymes, voir Lucas et Lehmer. Le test de primalité de Lucas Lehmer est une méthode pour tester la primalité d un nombre entier n pour lequel on suppose connaître les facteurs premiers de n 1. S il existe un a inférieur à n et …   Wikipédia en Français

  • Lehmer — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Lehmer: Derrick Henry Lehmer (1905 1991) Code de Lehmer Conjecture de Lehmer (en) Problème de Lehmer …   Wikipédia en Français

  • Nombres premiers — Nombre premier 7 est un nombre premier car il admet exactement deux diviseurs positifs …   Wikipédia en Français

  • Edouard Lucas — Édouard Lucas François Édouard Anatole Lucas (4 avril 1842 3 octobre 1891) est un mathématicien français. Édouard Lucas Sommaire …   Wikipédia en Français

  • François Édouard Anatole Lucas — Édouard Lucas François Édouard Anatole Lucas (4 avril 1842 3 octobre 1891) est un mathématicien français. Édouard Lucas Sommaire …   Wikipédia en Français

  • Liste Des Matières De La Théorie Des Nombres — Article détaillé : cryptologie. . Sommaire 1 Facteur (mathématiques) 2 Fractions 3 Arithmétique modulaire 4 …   Wikipédia en Français