Les nombres de Mersenne

Dhaouadi Nejib
Introduction
Quand Euclide a prouvé qu'il y a une infinité de nombres premiers, il a fait donc en montrant qu'il ne peut pas y avoir un plus grand nombre premier. Il est remarquable que ce domaine des mathématiques, qui a longtemps été considéré comme un exercice académique quelque peu récréatif, a maintenant s'est avéré avoir des utilisations cryptographiques importantes. La plupart des grands nombres premiers trouvés sont trop grands (et non assez aléatoire) pour les applications cryptographiques, mais ils sont souvent un moyen de tester les algorithmes avancés. Vu la croissance rapide des fonctions exponentielles, il semble raisonnable de rechercher des expressions exponentielles afin de trouver des grands nombres premiers. Telle était la motivation derrière le travail de certains mathématiciens du XVIe siècle, dont les idées sur la génération de grands nombres premiers suscitent encore notre intérêt aujourd'hui. La fonction la plus courante à examiner était $2^{n} - 1$.
Les nombres premiers de cette forme apparaissent dans Euclid’s Elements dans sa discussion sur les nombres parfaits. Beaucoup de gens ont pensé que cette expression est toujours première si n est premier, mais Hudalricus Regius, en 1536, semble avoir été la première personne a réaliser que $2^{11} -1 = 23 \times 89$. (C'était avant les calculatrices, les ordinateurs et la connaissance répandue de l'algèbre. L'affacturage a été très difficile et très lent.) Aujourd'hui, les nombres de la forme $M_n=2^n - 1$ sont appelés les nombres de Mersenne, d'après le français Monk Marin Mersenne qui a vécu de 1588 à 1648.
Marin Mersenne
Marin Mersenne (1588-1648), connu également sous son patronyme latinisé Marinus Mersenius est un religieux français appartenant à l'ordre des Minimes, érudit, mathématicien et philosophe. On lui doit les premières lois de l'acoustique, qui portèrent longtemps son nom. Il établit concomitamment avec Galilée la loi de la chute des corps dans le vide. De Waard dit de lui qu'il était le secrétaire de l'Europe savante de son temps. Ecclésiastique à la culture encyclopédique et aux centres d'intérêt multiples, Mersenne est une des figures les plus marquantes parmi les érudits de son temps.
Source: wikipedia.org
Propriétés des nombres de Mersenne
██
Théorème 1
Pour tous entiers a et n supérieurs ou égaux à 2, $a^n − 1$ est divisible par $a − 1$.

Démonstration

Il suffit de considérer la factorisation $a^n-1=(a-1)(a^{n-1}+a^{n-2}$ $+ \dots +a+1)$
Exemples
Pour tout entiers n non nul, $10^n-1$ est divisible par 9
Pour tout entiers n non nul, $2^{3n}-1$ est divisible par 7 !!
Remarque
Pour tout entier a superieur ou égal à 3 et pour tout entier n supérieur ou égal à 2, $a^n-1$ n'est pas un nombre premier.
Conséquence
Soient a et n deux entiers superieurs à 2
Si un nombre de la forme $a^n-1$ est premier alors $a=2$
██
Théorème 2
Si $2^n − 1$ est premier alors n est premier.

Démonstration

supposons que n n'est pas premier alors $n=pq$ où $p$ et $q$ sont deux entiers tels que $p \ge 2$ et $q \ge 2$ donc on a la factorisation suivante:
$2^{pq}-1= (2^p-1)(2^{p(q-1)}+2^{p(q-2)}$ $+ \dots +2^p+1) $
Et puisque chacun des deux facteurs $2^p-1$ et $2^{p(q-1)}+2^{p(q-2)}+ \dots +2^p+1$ est superieur à 2 donc $2^n-1$ n'est pas premier.
Remarque
La réciproque du théorème n'est pas toujour vraie c'est à dire si n est premier $2^n-1$ n'est pas forcément premier.
Exemple : $2^{11}-1$=2047=89x23 donc n'est pas premier
D'après le théorème précédent, si un nombre de Mersenne $M_n$ est premier alors n est premier ce qui facilite la recherche des nombres de Mersenne premiers
Quelques nombres de Mersenne qui sont premiers
$M_2=3$, $M_3=7$, $M_5=31$, $M_7=127$, $M_{13}=8191$, $M_{17}=131071$, $M_{19}=524287$, $M_{31}=2147483647$, $M_{61}=2305843009213693951$
██
Théorème 3
Soient p un entier superieur ou égal à 2 et n un entier naturel non nul tel que $2^n-1 \equiv 0\;\;(mod\;p)$
Si m est le plus petit entier naturel non nul tel que $2^m-1 \equiv 0 \;\;(mod\;p)$ alors m divise n. On dit que m est l'ordre de 2 modulo p.

Démonstration

Effectuons la division Euclidienne de n par m donc n=qm+r avec 0 ≤ r < m
$2^n-1 \equiv 0 \;\;(mod\;p)$ ⇔ $2^{qm+r} \equiv 1 \;\;(mod\;p)$ ⇔ ${\left({2^{m}}\right)}^q \times 2^r \equiv 1 \;\;(mod\;p)$ ⇔ $2^r \equiv 1 \;\;(mod \;p)$ car $2^m \equiv 1 \;\;(mod\;p)$ donc $r=0$ car m est le plus petit entier naturel non nul tel que $2^m-1 \equiv 0 \;\;(mod\;p)$ et par suite n=qm donc m divise n.
██
Théorème 4
Soient p et q deux nombres premiers tel que p >2 et q >2.
Si $M_q \equiv 0 \;\;(mod\;p)$ alors $p=2kq+1$ où $k\in \Bbb N$

Démonstration

$2^q-1 \equiv 0 \;\;(mod\;p)$ ⇔ avec q premier donc q est l'ordre de 2 modulo p
En plus d'après le théorème de Fermat $2^{p-1}-1 \equiv 0 \;\;(mod\;p)$ car p est un nombre premier qui ne divise pas 2 donc q divise p-1 ou encore p-1=k'q où k' ∈ ℕ et puisque p-1 est pair et q premier tel que q>2 alors k'=2k où k ∈ ℕ ce qui donne finalement p=2kq+1.
Définition
Un nombre brésilien n possède, dans une base b vérifiant 1 < b < n – 1 , une représentation qui s'écrit avec des chiffres tous égaux.
Plus précisément n=$(\underbrace{aaa \dots a}_{c fois})_b$ ou encore $n=a(1+b+ \dots +b^{c-1})$
Exemples
222 est un nombre brésilien car 222 s'écrit 222 en base 10.
171 est un nombre brésilien car 171 s'écrit 333 en base 7.
9 n'est pas un nombre brésilien car 9 = 10012 = 1003 = 214 = 145 = 136 = 127 et aucune de ces écritures n'est brésilienne.
██
Théorème 5
Tous les nombres de Mersenne $M_n$ ≥ 7, premiers ou composés, sont des nombres brésiliens

Démonstration

$M_n=2^n-1=\frac{2^n-1}{2-1}$$=1+1.2+1.2^2+ \dots +1.2^{n-1}$ donc $M_n$ s'écrit 11...1 en base 2 et par suite c'est un nombre brésilien.
Test de primalité de Lucas-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 Derrick Henry Lehmer dans les années 1930, grâce à son étude des suites de Lucas
██
Théorème 6
Soit p un nombre premier différent de 2. Le nombre de Mersenne $M_p = 2^p – 1$ est premier si et seulement si $s_{p-2}$ est divisible par $M_p$ où $s_p$ est la suite définie par:
$s_0=4$ et ∀ p ∈ ℕ $s_{p+1}=s_p^2-2$ (appelée suite de Lucas-Lehmer)

Démonstration

Voir la démonstration sur le site wikiwand.com

Programme en Python


from sys import stdout
from math import sqrt, log
 
def is_prime ( p ):
  if p == 2: return True # Lucas-Lehmer test only works on odd primes
  elif p <= 1 or p % 2 == 0: return False
  else:
    for i in range(3, int(sqrt(p))+1, 2 ):
      if p % i == 0: return False
    return True
 
def is_mersenne_prime ( p ):
  if p == 2:
    return True
  else:
    m_p = ( 1 << p ) - 1
    s = 4
    for i in range(3, p+1):
      s = (s ** 2 - 2) % m_p
    return s == 0
 
precision = 20000   # maximum requested number of decimal places of 2 ** MP-1 #
long_bits_width = precision * log(10, 2)
upb_prime = int( long_bits_width - 1 ) / 2    # no unsigned #
upb_count = 45      # find 45 mprimes if int was given enough bits #
 
print (" Trouver les nombres de Mersenne premiers M[2..%d]:"%upb_prime)
 
count=0
for p in range(2, int(upb_prime+1)):
  if is_prime(p) and is_mersenne_prime(p):
    print("M%d"%p),
    stdout.flush()
    count += 1
  if count >= upb_count: break
print

Output

Trouver les nombres de Mersenne premiers M\[2..33218\]
M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213 M19937 M21701 M23209

Problème ouvert

L

'ensemble des nombres de Mersenne premiers est-il infini?
Le projet GIMPS
Le Great Internet Mersenne Prime Search, ou GIMPS, est un projet de calcul partagé où les volontaires utilisent un logiciel client pour chercher les nombres premiers de Mersenne. Le projet a été fondé par George Woltman, qui est aussi le créateur du logiciel de calcul distribué employé.
L'algorithme utilisé est le test de primalité de Lucas-Lehmer pour les nombres de Mersenne.
Ce projet a permis de trouver les quinze plus grands nombres premiers de Mersenne connus qui sont aussi les quinze plus grands nombres premiers connus. Le plus grand connu depuis Décembre 2018 découvert par Patrick Laroche est $2^{82589933} − 1$, un nombre de 24862048 chiffres.
Nombres de Mersenne premiers découverts par GIMPS
  • 1996-Nov-13 – Joel a découvert le 35ème nombre de Mersenne premier, $2^{1398269}-1$
  • 1997-Aug-24 – Gordon Spence a découvert le 36ème nombre de Mersenne premier, $2^{2976221}-1$
  • 1998-Jan-27 – Roland Clarkson a découvert le 37ème nombre de Mersenne premier, $2^{3021377}-1$
  • 1999-Jun-01 – Nayan Hajratwala a découvert le 38ème nombre de Mersenne premier, $2^{6972593}-1$
  • 2001-Nov-14 – Michael Cameron a découvert le 39ème nombre de Mersenne premier, $2^{13466917}-1$
  • 2003-Nov-17 – Michael Shafer a découvert le 40ème nombre de Mersenne premier, $2^{20996011}-1$
  • 2004-May-15 – Josh Findley a découvert le 41ème nombre de Mersenne premier, $2^{24036583}-1$
  • 2005-Feb-18 – Dr. Martin Nowak a découvert le 42ème nombre de Mersenne premier, $2^{25964951}-1$
  • 2005-Dec-15 – Curtis Cooper and Steven Boone a découvert le 43ème nombre de Mersenne premier, $2^{30402457}-1$
  • 2006-Sep-04 – Curtis Cooper and Steven Boone a découvert le 44ème nombre de Mersenne premier, $2^{32582657}-1$
  • 2008-Sep-06 – Hans-Michael Elvenich a découvert le 45ème nombre de Mersenne premier, $2^{37156667}-1$
  • 2009-Jun-04 – Odd Magnar Strindmo a découvert le 46ème nombre de Mersenne premier, $2^{42643801}-1$
  • 2008-Aug-23 – Edson Smith a découvert le 47ème nombre de Mersenne premier, $2^{43112609}-1$
  • 2013-Jan-25 – Curtis Cooper a découvert le 48ème nombre de Mersenne premier, $2^{57885161}-1$
  • 2016-Jan-07 – Curtis Cooper a découvert le 49ème nombre de Mersenne premier, $2^{74207281}-1$
  • 2017-Dec-26 – Jonathan Pace a découvert le 50ème nombre de Mersenne premier, $2^{77232917}-1$
  • 2018-Dec-07 – Patrick Laroche a découvert le 51ème nombre de Mersenne premier, $2^{82589933}-1$

Autres articles

Connectez vous pour ajouter des commentaires.

Charte d'utilisation --- Plan du site
Copyright © 2010-2024 Dhaouadi Nejib - Tunisia