M44 : découverte du nouveau plus grand nombre premier !

Comme ses prédécesseurs, il s'agit d'un nombre de Mersenne : 2^32.582.657 - 1. Il s'écrit avec 9.808.358 chiffres en base 10 ! C'est le 10^ème nombre de Mersenne premier trouvé par le projet GIMPS et le 44^ème nombre de Mersenne premier connu. On l'appelle : M44. Il a été découvert le 4 septembre par les Docteurs Curtis Cooper et Steven Boone, professeurs à l'Université Centrale de l'Etat du Missouri (CMSU), qui avaient déjà découvert M43 neuf mois auparavant, à Noël (les veinards utilisent les ordinateursordinateurs de leur Université !).

Les participants au GIMPS ont retenu leur souffle jusqu'à ce que la première vérification se termine. En effet, tous se demandaient si M44 allait enfin dépasser la barrière psychologique des 10 millions de chiffres, et s'il allait rapporter à son découvreur une partie du prix de 100.000 $ offert par l'EFF (Electronic Frontier FoundationElectronic Frontier Foundation). Finalement non ! Et tout le monde en est heureux puisque le suspense continue et que tous espèrent devenir cet illustre découvreur. Mais sachez que la probabilité qu'un des nombres de Mersenne actuellement testés soit premier est de 1 sur plus de 300.000 ! Quant à la seconde vérification, elle devrait se terminer avant la fin de la semaine.

Lancé en janvier 1996, le projet GIMPS a pour but de trouver de nouveaux nombres de Mersenne premiers. Des dizaines de milliers de PCPC dans le monde contribuent actuellement au projet. Ils utilisent leur " temps libre " à effectuer des multiplications sur des nombres ayant maintenant plus de 10 millions de chiffres. Certains contributeurs se lancent même à la recherche d'un nombre de Mersenne premier de plus de 100 millions de chiffres (1 million de $ de prime à la clef !), alors qu'il faut environ 150 jours sur le PC équipé du processeur le plus rapide du moment (IntelIntel 5160 " Woodcrest " à 3 GHz) pour vérifier un exposant, et qu'il y en a des millions à vérifier ! Autant chercher une aiguille dans une meule de foin.

Test de Lucas-Lehmer

Un nombre premier est divisible seulement par 1 et par lui-même. Un nombre de Mersenne est de la forme : M_q = 2^q - 1, où q est premier.

La méthode utilisée pour prouver qu'un nombre de Mersenne est premier ou non est très simple et est beaucoup plus rapide que s'il fallait tester tous les diviseurs premiers possibles de M_q : elle consiste à calculer S_i+1 = S_i² - 2 (modmod M_q), en partant de S₀ = 4. Si S_q-2 = 0 (mod M_q) , alors M_q est premier. Cette méthode a été inventée par le français Edouard Lucas à la fin du XIXème siècle et a été améliorée et rigoureusement prouvée par
l'américain DerrickDerrick Lehmer au début du XXème siècle. Elle s'appelle : LLT (Lucas-Lehmer-Test).

Une méthode vraiment simple ! Mais quand même un peu longue pour les exposants testés actuellement. Avec q= 32.582.657, il faudrait environ quinze jours de calcul sur le PC le plus puissant actuellement et travaillant jour et nuit. La vérification que j'ai faite à Grenoble aura duré seulement 5 jours et demi, car elle a utilisé un super-calculateur Bull NovaScale 6160 disposant de 16 processeurs Itanium2 à 1.5 GHz ainsi que le programme Glucas, écrit par Guillermo Ballester Valor de GrenadeGrenade (Espagne), qui parallélise le calcul du carré (FFT) sur les 16 processeurs. GLucas ne tient pas compte de l'architecture NUMA de ce type de grands calculateurs. S'il en tenait compte, la durée de vérification serait divisée par deux !

A quoi sert de chercher et trouver de tels nombres ?

D'abord, leur recherche contribue à l'amélioration des programmes de multiplication de grands nombres. Ensuite, leur recherche permet de vérifier la fiabilité des processeurs et des ordinateurs. De plus, les nombres de Mersenne premiers sont utilisés par AppleApple pour de la cryptologiecryptologie. Enfin, grâce à l'étude des nouveaux nombres de Mersenne premiers trouvés, les amateurs de nombres premiers espèrent découvrir une formule cachée fournissant des indications sur les caractéristiques du prochain nombre de Mersenne premier.

Les participants au projet GIMPS ont eu très peur que M44 soit le premier nombre premier ayant plus de 10 millions de chiffres. Ce monstre sera très probablement un nombre de Mersenne : M45M45, car la preuve de primalité des nombres de Mersenne est la plus simple qui soit, et le programme Prime95 écrit en assembleur par George Woltman est le plus efficace qui soit et s'améliore régulièrement. Il est donc certain que le nombre de participants au projet GIMPS va encore augmenter ! Les paris sur la date de découverte de M45 apparaissent déjà sur le forum du GIMPS. Mais les contributeurs du GIMPS craignent que la veine s'épuise après cinq découvertes successives si rapprochées et qu'il leur faille attendre maintenant plusieurs années avant de retomber sur un " nid " de nombres de Mersenne premiers. Wait & See !

Il faudra sûrement attendre encore plusieurs années pour être certain que M44 est bien le 44^ème nombre de Mersenne premier (et pas seulement connu). En effet, jusqu'à M39, tous les candidats ont été vérifiés 2 fois, 3 fois même pour certains. M40, M41, M42M42, M43 et M44 ont donc peut-être un petit frère qui a échappé à la recherche du GIMPS jusqu'ici. Mais les probabilités sont très faibles.