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
| Mn | p | Mp | Valeur de Mp en base 10 | Nombre de chiffres en base 10 | Date de découverte | Dé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 | p | Mp | Valeur 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.
- Site officiel du projet GIMPS
