Vote utilisateur: 5 / 5

Etoiles activesEtoiles activesEtoiles activesEtoiles activesEtoiles actives
 

nombres premiers spheres
Historique de la recherche du plus grand nombre premier


Le record du plus grand nombre premier connu a presque toujours été un nombre premier de Mersenne donc de la forme

 $$M_n = 2^n - 1$$

  • M(n) ou Mn, désigne le nième nombre premier de Mersenne.
  • Par contre M indice n, Mn , n est le rang du nombre de Mersenne.

Une utilisation des nombres premiers

Les nombres premiers sont étudiés depuis l'antiquité (voir l'article nombres premiers, toute une histoire) et sont utilisés aujourd'hui dans la plupart des systèmes de cryptographie (internet, bancaires, militaires). La recherche sur leurs propriétés est de fait encore très active, et très encadrée.

La plupart des systèmes de cryptographie actuels fonctionnent sur le fait qu'il est très long et difficile de trouver la décomposition d'un entier en nombres premiers si ce dernier est très grand (plusieurs centaines de chiffres).
Savoir que 15 se décompose en 3 fois 5 est simple, mais si on vous donne un nombre de 1 000 chiffres, c'est une autre histoire.
Notons toutefois que ces nombres premiers titanesques (de plusieurs millions de chiffres) ne sont pas utilisés pour créer des clés publiques en cryptographie en raison de leur rareté, un hacker voyant une clé à plusieurs millions de chiffres n'aurait pas tant de candidats à tester.

 

Date Découvreur Type Désignation Valeur Nb de chiffres
 3 janvier 2018   Projet GIMPS   Nombre
 de Mersenne 
 M77 232 917 (= M50?)  = 277 232 917 - 1 
  23 249 425
 7 janvier 2016   Projet GIMPS   Nombre
 de Mersenne 
 M74 207 281 (= M49?)  = 274 207 281 - 1 
  22 338 618
 25 janvier 2013   Projet GIMPS   Nombre
 de Mersenne 
 M57 885 161 (= M48?)  = 257 885 161 - 1 
  17 425 170
 12 avril 2009   Projet GIMPS   Nombre
 de Mersenne 
 M42 643 801 (= M46?)  = 242 643 801 - 1    12 837 064
 6 septembre 2008   Projet GIMPS   Nombre
 de Mersenne 
 M37 156 667 (= M45?)  = 237 156 667 - 1    11 185 272

 

En février 2016, M44 est le plus grand nombre premier de Mersenne pour lequel on sait qu'il n'y a pas d'autre nombre premier de Mersenne plus petit encore inconnu.

$$\large M44= M_{32~582~657}= 2^{32~582~657}- 1$$

Les recherches actuelles proposées par le projet GIMPS, travail collaboratif de milliers d'ordinateurs, ne donnent pas forcemment les nombres dans l'ordre.

Historique : A la recherche des grands nombres premiers


Liste des nombres premiers de Mersenne connus (Février 2016)
MnpMpValeur de Mp en base 10Nombre
de chiffres
en base 10
Date de découverteDécouvreur(s)
M1 2 M2 3 1 Antiquité Les mathématiciens grecs
M2 3 M3 7 1
M3 5 M5 31 2
M4 7 M7 127 3
M5 13 M13 8 191 4 Moyen Âge (XIIIe siècle) Ibn Fallus (1194-1239)
M6 17 M17 131 071 6 1588 Cataldi
M7 19 M19 524 287 6 1588 Cataldi
M8 31 M31 2 147 483 647 10 1750 Euler
M9 61 M61 2 305 843 009 213 693 951 19 1883 Pervushin
M10 89 M89 618970019…449562111 27 1911 Powers (en)
M11 107 M107 162259276…010288127 33 1914 Powers
M12 127 M127 170141183…884105727 39 1876 Lucas
M13 521 M521 686479766…115057151 157 30 janvier 1952 Robinson (SWAC (en))
M14 607 M607 531137992…031728127 183 30 janvier 1952 Robinson (SWAC)
M15 1 279 M1279 104079321…168729087 386 25 juin 1952 Robinson (SWAC)
M16 2 203 M2203 147597991…697771007 664 7 octobre 1952 Robinson (SWAC)
M17 2 281 M2281 446087557…132836351 687 9 octobre 1952 Robinson (SWAC)
M18 3 217 M3217 259117086…909315071 969 8 septembre 1957 Riesel (BESK (en))
M19 4 253 M4253 190797007…350484991 1 281 3 novembre 1961 Hurwitz (IBM)
M20 4 423 M4423 285542542…608580607 1 332 3 novembre 1961 Hurwitz (IBM)
M21 9 689 M9689 478220278…225754111 2 917 11 mai 1963 Gillies (en) (ILLIAC II)
M22 9 941 M9941 346088282…789463551 2 993 16 mai 1963 Gillies (ILLIAC II)
M23 11 213 M11213 281411201…696392191 3 376 2 juin 1963 Gillies (ILLIAC II)
M24 19 937 M19937 431542479…968041471 6 002 4 mars 1971 Tuckerman (en) (IBM)
M25 21 701 M21701 448679166…511882751 6 533 30 octobre 1978 Noll (en) et Nickel (CDC)
M26 23 209 M23209 402874115…779264511 6 987 9 février 1979 Noll (CDC)
M27 44 497 M44497 854509824…011228671 13 395 8 avril 1979 Nelson (en) et Slowinski (en)
(Cray Research)
M28 86 243 M86243 536927995…433438207 25 962 25 septembre 1982 Slowinski (Cray)
M29 110 503 M110503 521928313…465515007 33 265 28 janvier 1988 Colquitt et Welsh (NEC)
M30 132 049 M132049 512740276…730061311 39 751 19 septembre 1983 Slowinski (Cray)
M31 216 091 M216091 746093103…815528447 65 050 1er septembre 1985 Slowinski (Cray)
M32 756 839 M756839 174135906…544677887 227 832 19 février 1992 Slowinski et Gage
M33 859 433 M859433 129498125…500142591 258 716 10 janvier 1994 Slowinski et Gage
M34 1 257 787 M1257787 412245773…089366527 378 632 3 septembre 1996 Slowinski et Gage
M35 1 398 269 M1398269 814717564…451315711 420 921 13 novembre 1996 GIMPS / Joel Armengaud
M36 2 976 221 M2976221 623340076…729201151 895 932 24 août 1997 GIMPS / Gordon Spence
M37 3 021 377 M3021377 127411683…024694271 909 526 27 janvier 1998 GIMPS / Roland Clarkson
M38 6 972 593 M6972593 437075744…924193791 2 098 960 1er juin 1999 GIMPS / Nayan Hajratwala
M39 13 466 917 M13466917 924947738…256259071 4 053 946 14 novembre 2001 GIMPS / Michael Cameron
M40 20 996 011 M20996011 125976895…855682047 6 320 430 17 novembre 2003 GIMPS / Michael Shafer
M41 24 036 583 M24036583 299410429…733969407 7 235 733 15 mai 2004 GIMPS / Josh Findley
M42 25 964 951 M25964951 122164630…577077247 7 816 230 18 février 2005 GIMPS / Martin Nowak
M43 30 402 457 M30402457 315416475…652943871 9 152 052 15 décembre 2005 GIMPS / Cooper et Boone
M44 32 582 657 M32582657 124575026…053967871 9 808 358 4 septembre 2006 GIMPS / Cooper et Boone
M45 ? 37 156 667 M37156667 202254405…308220927 11 185 272 6 septembre 2008 GIMPS / Elvenich
M46 ? 42 643 801 M42643801 169873516…562314751 12 837 064 12 avril 2009 GIMPS / Odd Magnar Strindmo
M47 ? 43 112 609 M43112609 316470269…697152511 12 978 189 23 août 2008 GIMPS / Smith
M48 ? 57 885 161 M57885161 581887266…724285951 17 425 170 25 janvier 2013 GIMPS / Cooper
M49 ? 74 207 281 M74 207 281 300376418…086436351 22 338 618 7 janvier 2016 GIMPS / Cooper

Liste de nombres de Mersenne non premiers

Les neuf plus petits nombres de Mersenne non premiers mais d'indices premiers (venant s'intercaler entre les premiers et neuvième nombres de Mersenne premiers, connus à la fin du XIXe siècle) sont les suivants :

No pMpValeur de Mp
en base 10
Nombre de
chiffres
en base 10
Décomposition
1 11 M11 2 047 4 23 × 89
2 23 M23 8 388 607 7 47 × 178 481
3 29 M29 536 870 911 9 233 × 1 103 × 2 089
4 37 M37 137 438 953 471 12 223 × 616 318 177
5 41 M41 2 199 023 255 551 13 13 367 × 164 511 353
6 43 M43 8 796 093 022 207 13 431 × 9 719 × 2 099 863
7 47 M47 140 737 488 355 327 15 2 351 × 4 513 × 13 264 529
8 53 M53 9 007 199 254 740 991 16 6 361 × 69 431 × 20 394 401
9 59 M59 576 460 752 303 423 487 18 179 951 × 3 203 431 780 337

 

Great Internet Mersenne Prime Search, ou 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. Cela permet en fait d'utiliser la puissance de calcul de milliers d'ordinateurs simultanément. 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.

L'Electronic Frontier Foundation offre des prix de calcul coopératif pour encourager les internautes à contribuer à la résolution de problèmes scientifiques par le calcul distribué. Le GIMPS a ainsi reçu 100 000 dollars pour sa découverte en 2008 du premier nombre premier d'au moins 10 millions de chiffres décimaux. L'EFF offre encore 150 000 et 250 000 dollars respectivement pour la découverte du premier nombre premier de 100 millions et 1 milliard de chiffres décimaux.

Sources.


Articles Connexes