$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Nombres de Mersenne, test de Lucas-Lehmer

Définition : Si p est un nombre premier, le nombre de Mersenne d'indice p est le nombre Mp=2p-1.
  Ces nombres de Mersenne ne sont pas tous premiers (ce serait trop facile), et d'ailleurs il y en a relativement peu qui le sont effectivement : on ne sait même pas s'il y en a une infinité. En revanche, on dispose d'un test particulièrement efficace pour tester s'ils sont premiers, le test de Lucas-Lehmer :
Théorème : On définit une suite (Sn) en posant :
  • S2=4.
  • Sn=(Sn-1)2-2.
Alors Mp est premier si et seulement si Mp divise Sp.
Avec des notations plus mathématiques, Mp est premier si, et seulement si, Sp=0 (mod Mp).

  Ce test est polynômial en le nombre de chiffres de Mp, puisqu'il faut calculer p termes de la suite, et que p est justement de l'ordre du nombre de chiffres de Mp. En outre, son implémentation informatique exploitant au mieux les particularités de l'arithmétique binaire est particulièrement efficace. C'est pourquoi le record du plus grand nombre premier jamais obtenu est toujours battu à l'aide de nombres de Mersenne. A titre d'exemple, M13466917 possède 4 053946 chiffres décimaux!

Le minime Marin Mersenne affirme en 1644 que Mp est premier pour p=2,3,5,7,13,17,19,31,67,127,257, et composé (c'est-à-dire non premier) pour les 44 autres valeurs de p inférieures à 257. Il commet en fait 5 erreurs (M61, M89 et M107 sont premiers, M67 et M257 ne le sont pas). La cryptographie, qui fait usage de grands nombres premiers, ne fait jamais appel aux nombres de Mersenne. Ils sont en effet bien trop particuliers, puisque l'on sait que (Mp+1) est une puissance de 2. Les chasseurs de code auraient alors beaucoup trop d'informations!
Consulter aussi...