Un vent de
folie souffle
actuellement autour du
projet
GIMPS (
Great Internet Mersenne
Prime Search). Après 2 ans sans
aucune découverte, le projet vient d'annoncer coup sur coup
la découverte des 45 et 46 ème nombres premiers
de Mersenne, soit les deux plus grands nombres premiers jamais
découvert.
Le 23 Août
2008, un ordinateur reportait au serveur du projet la
découverte d'un nouveau nombre premier de Mersenne. Les
vérifications de ce nombre ont commencé le 26
août, et trois ordinateurs avec des configurations
différentes ont confirmé cette
découverte.
De façon à peine croyable, le 6 septembre, un
nouvel ordinateur rapportait la découverte d'un nouveau
nombre
premier de Mersenne !! Deux vérifications
indépendantes ont confirmé cette
découverte (la troisième
confirmation est en cours).
Le plus étonnant est que cela faisait 2 ans, que le projet
GIMPS restait bredouille. Le
44ème nombre de Mersenne premier, découvert le 4
septembre 2006, avait échoué à
quelques encablures des 10 millions de chiffres (9.808.358 chiffres).
Les noms des découvreurs n'ont pas encore
été divulgués. La seule chose que
l'on peut dire c'est que l'un des deux découvreurs est
allemand.
Les administrateurs du projet GIMPS travaillent actuellement sur la
rédaction d'un communiqué de presse pour annoncer
la
découverte de ces deux nombres premiers de plus de 10
millions de chiffres. Plus de détails seront
communiqués au cours de la prochaine semaine.
Le projet GIMPS
GIMPS est le
père de tous les logiciels de calcul
distribué puisqu'il a été
lancé en 1996, soit 3 ans avant SETI@home. Il
s’agit certainement aussi de la loterie la plus
étrange de l'Internet à
laquelle participent depuis des années des internautes
passionnés de
mathématiques. Après avoir
installé
le
logiciel du projet, le serveur
attribue à votre ordinateur un nombre premier p à
huit chiffres. Comme
chaque nombre premier, celui-ci n’est divisible que par un et
lui-même.
Le programme calcule alors le nombre 2
p
- 1 et vérifie s’il s’agit
également d’un nombre premier. C’est
extrêmement laborieux : Même un PC
moderne est occupé pendant des jours (voire des semaines)
avec de tels calculs.
Le nombre premier à huit chiffres que l’on vous
donne à vérifier en tant que participant au
projet Gimps
est attribué au hasard. Quelqu’un qui a beaucoup
de
chance et qui
découvre un nouveau nombre premier peut gagner 100 000
dollars. C’est
la somme que l'Electronic Frontier Foundation (EFF)
offre pour la
découverte du premier nombre premier ayant au moins dix
millions de chiffres. (l'Electronic Frontier
Foundation est
une organisation non gouvernementale internationale à but
non lucratif, fondée en 1990 aux États-Unis par
Mitch Kapor, John Gilmore, et John Perry Barlow, connu pour
être l'auteur de la
Déclaration
d'indépendance du cyberespace. L'objectif
essentiel de l'EFF est de défendre la liberté
d'expression sur Internet).
La répartition de la récompense devrait se faire
de la manière suivante :
50.000 $ iront au découvreur du premier nombre non divisible
de
plus de 10 millions de chiffres
5.000 $ seront attribués au projet GIMPS pour couvrir les
frais
et préparer les recherches futures (dans l'optique de la
découverte d'un nombre premier de plus de 100 millions de
chiffres, dont la récompense est fixée
à 150.000 $)
25.000 $ iront à George Woltman, le fondateur du projet GIMPS
3.333 $ seront attribués à chacune des personnes
qui ont découvert un des 6
derniers nombres de Mersenne premier sur GIMPS (Michael Cameron,
Michael Shafer, Josh Findley, Dr. Martin Nowak, Curtis Cooper et Steven
Boone)
George Woltman, le créateur du projet GIMPS explique que
"bien que
nous pensons avoir bien compris la loi d'apparition et la distribution
des Nombres de Mersenne Premiers, cela n'a pas
été
prouvé rigoureusement. En trouver un nouveau ajoute 'une
nouvelle pièce au puzzle' qui nous permet de
confirmer nos théories". Il note que par le
passé la recherche de Nombres de Mersenne Premiers a
apporté
des
améliorations importantes de la méthode de
"Transformée de Fourier Rapide" (FFT), qui est
utilisée dans de nombreuses applications (y compris
par le projet SETI@home), et que
cela a permis également de
découvrir des erreurs dans les composants des ordinateurs
grâce à des tests
de
stress draconiens. "Le projet est aussi un bon moyen pour amener les
jeunes participants du GIMPS à s'intéresser aux
Mathématiques".
Les
nombres premiers de Mersenne peuvent être
représentés par la
formule 2p - 1, où
l’exposant p est
également un nombre premier. Ce
sont eux qui intéressent particulièrement les
mathématiciens, car les
nombres premiers de Mersenne disposent d’un avantage
décisif : Ils sont
relativement faciles à trouver (par rapport aux autres types
de nombres premiers)
Tout le monde connaît depuis son passage sur les bancs de
l'Ecole les nombres
premiers à un ou deux chiffres, tels que 3, 5, 7 et 11. La
recherche de grands nombres premiers avec des centaines, des milliers
ou des millions de chiffres est nettement plus difficile. Cela vient du
fait que les grands nombres ne portent tout simplement pas leur
diviseurs - une situation fâcheuse, pas seulement pour les
mathématiciens.
"Il existe une procédure relativement efficace
pour vérifier si un nombre de Mersenne est premier ou non",
explique Florian
Hess, mathématicien à
l’université technique de Berlin. Pour
d’autres
nombres, choisis au hasard, le problème est nettement plus
difficile. On
ne peut alors plus déterminer en quelques jours de calcul -
comme c’est
habituel pour les nombres de Mersenne - si le nombre a
d’autres
diviseurs qu’un et lui-même.
Sécurité
et puissance de calcul
Les nombres premiers
fascinent l'humanité depuis des
millénaires.
Toutefois, et seulement depuis la naissance de la
société informatisée,
il n'existe réellement qu'une seule application possible.
Les nombres
premiers jouent un rôle prépondérant
dans le codage des données. C'est
ce qu'on appelle communément le code RSA utilisé,
par exemple, par les
banques pour crypter les communications internet. RSA utilise le fait
qu'un grand nombre ne peut être divisé qu'au prix
d'un énorme effort.
Le fonctionnement du code RSA n'est pas compliqué
à
comprendre. La banque va multiplier deux nombres premiers de 150, voire
mieux, de 300 chiffres. Cette multiplication va produire une
clé
publique avec laquelle le client de la banque va pouvoir envoyer des
données au serveur de la banque. Cette clé ne
concerne que le
navigateur internet. "90% de toutes les applications de
sécurité sur
Internet reposent sur ce processus" explique le
mathématicien berlinois
Florian Hess. Pour déchiffrer cette clé, il faut
connaître les deux
nombres premiers (que la banque doit garder secret) ou disposer d'un
parc d'ordinateurs gigantesque.
La sécurité de cette forme de cryptographie
repose
exclusivement sur le fait qu'il faudrait
énormément de puissance et de
temps de calcul pour réussir à pirater la
clé. Comme les ordinateurs
sont de plus en plus puissants, les nombres premiers
utilisés pour
crypter les données doivent être toujours plus
grands. C'est pourquoi,
la recherche très théorique de nombres premiers
revêt de plus en plus
un intérêt purement pratique.
"L'un des plus grands
problèmes non résolus des
mathématiques"
Les deux nouveaux
nombres premiers récemment
découverts
rendent-ils les échanges sur Internet moins sûrs ?
Non,
telle est
la réponse de Günter Ziegler, président
de l’
Association
Allemande de
Mathématiciens. "Le record actuel ne met pas en
danger la sécurité des
données sur Internet", explique-t-il. La raison
réside dans la
particularité des
nombres de Mersenne
décrite précedemment : Un ordinateur peut
vérifier
assez rapidement s’ils
sont premiers ou non. Ce n’est pas le cas pour
d’autres nombres,
utilisés par les banques.
Au cours des derniers siècles, les
mathématiciens ont déjà pu
répondre à certaines grandes questions
relatives aux nombres premiers. Ainsi, par exemple, à la
question sur
la quantité de nombres premiers existants, ils
répondent qu'il en existe un nombre
infini.
La démonstration est simple : Admettons qu’il
n’y ait
qu’un nombre fini de nombres premiers p
1,
p
2, p
3,
... p
n. Ensuite,
multiplions tous ces n nombre premiers entre eux et ajoutons 1. Le
résultat est un nombre divisible par aucun des n nombres
premiers. Il
ne pourra donc s’agir que d’un nouveau nombre
premier ou du produit
d’au moins deux nouveaux nombres premiers.
L’hypothèse d’une quantité
finie de nombres premiers est ainsi réfutée.
Un autre problème, jusqu’à
présent irrésolu et dans lequel interviennent des
nombres premiers, est ladite
hypothèse de
Riemann.
Il y a plus de 150 ans, le mathématicien allemand Bernhard
Riemann a
émis l’hypothèse selon laquelle les
zéros non triviaux de ladite fonction zêta de
Riemann
sont
situés sur une droite. "Cette fonction peut être
définie à l’aide de
nombres premiers", explique Florian Hess de
l’université technique de
Berlin. La conjecture de Riemann aurait déjà
été prouvée à
l’aide
d’ordinateurs pour des millions de zéros, mais la
preuve finale reste
encore à apporter. Hess ajoute "qu'il s’agit
d’un des plus grands problèmes
irrésolus
des mathématiques". Sa résolution
constiturait en quelque sorte le Graal des mathématiciens,
puisqu'il reviendrait à comprendre le mystère de
la répartition des nombres premiers.
Sa solution présenterait également un
intérêt
énorme car la fonction zêta permet
d’évaluer les temps de
fonctionnement d’algorithmes - ce qui est d’une
grande aide pour les
calculs complexes. Celui qui démontrera la
conjecture de Riemann ne
sera pas seulement célèbre, mais aussi riche.
L’institut Clay
Mathematics offre une récompense d’un million de
dollars pour quiconque arrivera à le démontrer.
Par
rapport à cela, la recherche de nombres premiers de plus en
plus grands
est mal payée - par contre, le vainqueur n’a pas
à se creuser la tête : le travail est
effectué par le logiciel Gimps.
Les nombres premiers
fascinent les mathématiciens
amateurs et professionnels depuis longtemps. Un entier plus grand que 1
est appelé nombre premier si et seulement si ses
seuls diviseurs sont 1 et lui-même. Les premiers nombres
premiers sont : 2, 3, 5, 7, 11, etc. Par exemple, le nombre 10 n'est
pas premier car il est divisible par 2 et par 5. Un Nombre de Mersenne
Premier est de la forme 2p-1 , où p
est premier. Les premiers Nombres de Mersenne Premiers sont : 3, 7, 31,
et 127 ,
générés par p = 2, 3, 5, et
7. Avant les deux découvertes
réalisées ces dernières semaines, il
n'y avait que 44 nombres de Mersenne connus
Les Nombres
de Mersenne Premiers sont une importante composante de la
branche des
Mathématiques appelée Théorie des
Nombres depuis qu'ils ont été décrits
et étudiés par Euclide en 350 avant JC. L'homme
qui leur a donné son nom, le moine
Français Marin
Mersenne (1588-1648), a formulé une conjecture
célèbre concernant les valeurs de p qui
donneraient un nombre premier. Il aura fallut 300 ans et d'importantes
découvertes Mathématiques pour confirmer cette
conjecture.
Les quatre premiers
nombres premiers de Mersenne
étaient connus dès l'Antiquité. Le
cinquième (213-1) a
été découvert en 1456 par un inconnu.
Les deux suivants ont été trouvés par
le mathématicien italien Cataldi
en 1588. Plus d'un siècle plus tard, en 1750, le
mathématicien suisse Euler en trouva encore un. Le suivant
dans l'ordre chronologique (mais non numérique) a
été trouvé par le français
Lucas en 1876, puis un par le mathématicien russe Pervushin
en 1883. Deux autres ont été trouvés
au début du XXe siècle
par Powers en 1911 et en
1914.
La recherche des nombres
premiers de Mersenne fut ensuite
révolutionnée par l'introduction des calculateurs
électroniques. La première
identification d'un nombre de Mersenne par ce moyen eut lieu
à 22 heures le 30 janvier 1952
par un ordinateur SWAC à l'Institut d'Analyse
Numérique (Institute for Numerical Analysis)
du campus de Université
de Californie - Los Angeles, sous la direction de Derrick
Lehmer, avec un programme écrit par R.M.
Robinson.
C'était le
premier nombre premier de Mersenne
identifié depuis 38
ans. Le suivant fut trouvé moins de deux heures plus tard
par le même
ordinateur, qui en trouva trois de plus dans les mois suivants.
Les
précédentes découvertes
de Nombres de Mersenne Premiers ont toute été
réalisées grâce au logiciel de calcul
partagé GIMPS :
| Numéro |
Date
de
la découverte |
Nombre |
Chiffres |
Temps
de calcul |
Processeur |
Découvreur |
Où |
| 46ème |
6
Sept. 2008 |
? |
? |
|
|
? |
? |
| 45ème |
23
Août 2008 |
? |
? |
|
|
? |
? |
| 44ème |
4
Sept. 2006 |
232.582.657-1 |
9.808.358 |
- |
- |
Curtis
Cooper et Steven Boone |
Université
Centrale
de l'Etat du Missouri (Etats-Unis d'Amérique) -
parc de 700 PC |
| 43ème |
15
Déc. 2005 |
230.402.457-1 |
9.152.052 |
50
jours
|
-
|
Curtis
Cooper et Steven Boone |
Université
Centrale
de l'Etat du Missouri (Etats-Unis d'Amérique) -
parc de 700 PC |
| 42ème |
18
Fév. 2005 |
225.964.951-1 |
7.816.230 |
50
jours |
P
IV à 2,4 Ghz |
Docteur
Martin Nowak |
Allemagne |
| 41ème |
15
Mai
2004 |
224.036.583-1 |
7.235.733 |
14
jours |
P
IV à 2,4 Ghz - Windows XP |
Josh
Findley |
Etats-Unis
d'Amérique |
| 40ème |
17
Nov 2003 |
220.996.011-1 |
6.320.430 |
19
jours |
P
IV à 2 Ghz
Dell Dimension |
Michael
Shafer
(26 ans) |
Etats-Unis
d'Amérique |
| 39ème |
14
Nov. 2001 |
213.466.917-1 |
4.053.946 |
45
jours |
AMD
T-Bird à 800 Mhz |
Michael
Cameron (20 ans) |
Canada |
| 38ème |
1er
Juin 1999 |
26.972.593-1 |
2.098.960 |
111
jours |
P
II à 350 mhz |
Nayan
Hajratwala |
Etats-Unis
d'Amérique |
| 37ème |
27
Jan 1998 |
23.052.377-1 |
909.526 |
46
jours |
P
I à 200 mhz |
Roland
Clarkson |
Etas-Unis
d'Amérique |
| 36ème |
24
Août 1997 |
22.976.221-1 |
895.932 |
15
jours |
P
I à 100 mhz |
Gordon
Spence |
Royaume-Uni |
| 35ème |
13
Nov. 1996 |
21.398.269-1 |
- |
88
heures |
P
I à 90 mhz |
Joël
Armengaud |
France |
Les
algorithmes de calcul utilisés par le projet GIMPS ont une
histoire très particulière. Les
programmes qui ont trouvé les récents nombres de
Mersenne premiers sont basés sur un algorithme
spécifique. Au début des années 1990,
Richard Crandall,
un scientifique distingué travaillant chez Apple, a
découvert le moyen de multiplier par deux la vitesse de
calcul de ce qui est appelé "convolutions" -- en fait
d'énormes multiplications. La méthode ne
s'applique pas seulement à la recherche de nombres premiers
mais aussi à d'autres domaines de l'art du calcul par
ordinateur. Pendant ses travaux, il a aussi breveté le
système "Encryptage Elliptique Rapide", maintenant
détenu par "Apple Computer", qui utilise les Nombres de
Mersenne Premiers pour encrypter et décrypter rapidement les
messages. George Woltman a implémenté
l'algorithme de Crandall en assembleur Intel ia32, ce qui a produit un
programme de recherche de nombres premiers
d'une efficacité sans précédent,
d'où est issu l'actuel projet GIMPS.
Des enseignants de classes du Collège jusqu'au
Lycée ont utilisé le projet GIMPS comme moyen
pour faire aimer les Mathématiques à leurs
étudiants. Les étudiants qui font tourner ce
logiciel libre contribuent à la recherche en
Mathématiques.
Historiquement, la recherche de Nombres de Mersenne Premiers a
été utilisée comme un test exigeant
pour les composants matériels des ordinateurs. Le programme
libre du GIMPS a permis de découvrir des
problèmes matériels cachés dans de
nombreux PCs.
Sources :
-
Zwei
neue Rekord-Primzahlen entdekt : Der spiegel online
-
Nombre
premier de Mersenne : Wikipédia
-
Great Internet
Mersenne Prime Search (GIMPS)
|
|
|
Seul les utilisateurs enregistrés peuvent commenter un article.
|
