lundi, janvier 02, 2006

M43: plus de 9 millions de chiffres pour le plus grand nombre premier connu

Le nombre 2^30402457 - 1 (2 puissance 30402457 auquel on retranche 1) est devenu le plus grand nombre premier découvert à ce jour, c'est-à-dire un nombre divisible uniquement par 1 et par lui-même. Ce nombre est un nombre premier de Mersenne, c'est-à-dire dont l'écriture est la suivante: 2 puissance un nombre premier (ici 30402457) auquel on retranche 1.

Ce nombre, baptisé M43 (pour le 43ème nombre premier de Mersenne connu), contient tout de même 9 152 052 chiffres et a été découvert grâce au projet GIMPS (Great Internet Mersenne Prime Search) par les docteurs Curtis Cooper et Steven Boone de l'Université Centrale de l'Etat du Missouri (CMSU). C'est la technique de la grille de calcul (grid computing), c'est-à-dire la distribution de la charge de calcul auprès d'une multitude d'ordinateurs interconnectés, qui a permis cet exploit.


Le projet GIMPS

Le projet GIMPS a pu regrouper au sein d'une grille les ordinateurs de volontaires et bénévoles répartis tout autour de la planète, grâce au réseau Internet. La plupart des projets utilisant le calcul distribué récupèrent la puissance informatique non employée des machines de ses contributeurs, de manière complètement transparente.

Dans le cas présent, ce sont tout de même plus de 200 000 ordinateurs répartis sur les cinq continents, en plus des 700 ordinateurs de l'université CMSU, qui ont permis de découvrir M43 en à peine... 10 mois. L'appartenance de ce nombre à l'ensemble des nombres premiers a été vérifiée bien plus rapidement, en cinq jours à Grenoble par un chercheur de Bull grâce à un supercalculateur.


100 000 dollars pour le premier nombre premier composé de plus de 10 millions de chiffres

M43 est bien plus grand que le précédent plus grand nombre premier connu à ce jour, qui ne comptait "que" entre 7 et 8 millions de chiffres. Mais M43 n'atteint pas encore les dix millions de chiffres, une barre symbolique qui aurait permis au projet GIMPS d'empocher 100 000 dollars, somme promise par l'Electronic Frontier Foundation (EFF) pour ce palier symbolique.

L'EFF est une organisation non lucrative qui vise à encourager la recherche. La découverte du premier nombre premier constitué de plus d'un million de chiffres avait ainsi été récompensée par une somme de 50 000 dollars. Les chercheurs de CMSU estiment que les dix millions de chiffres seront atteints courant 2007.


Les nombres premiers et la cryptographie

La propriété des nombres premiers est particulièrement utilisée dans le cadre de la cryptographie. La difficulté de factorisation par les moyens connus des très grands nombres permet d'assurer une protection certaine.

Dans le cadre de la cryptographie RSA, la sécurité repose sur la multiplication de deux très grands nombres premiers (les clés) afin de former un nombre gigantesque. Si il est simple de multiplier deux grands nombres, l'opération inverse, la factorisation, est très coûteuse en temps de calcul. Ce dernier nombre sera donc très difficile à factoriser, assurant la sécurité des clés et des données.

source : technosciences

1 commentaire:

Anonyme a dit…

M44 est prévu (théoriquement !) en mi 2006. Espérons qu'il arrivera avant fin 2006 !
Tout le monde peut participer au projet GIMPS. C'est facile.
Tony