Le dernier des premiers

Drapeau jaune : Cet article demande quelques connaissances mathématiques et un peu d’abstraction pour être entièrement compris

---

Les nombres premiers sont fascinants. Pour rappel, un nombre entier supérieur à 0 est dit premier s’il possède exactement deux diviseurs, à savoir 1 et lui-même. Et ces nombres sont aujourd’hui utiles dans notre quotidien, puisqu’ils sont à la base du système de cryptographie RSA, garant de votre (presque) sécurité informatique.

Dans un précédent article, je vous parlais des théorèmes et conjectures concernant leur répartition au sein de l’ensemble des nombres entiers. En particulier, l’ensemble des nombres premiers est infini : peu importe le nombre premier considéré, il en existe toujours un plus grand.

Et face à ce genre de résultat, les compétitions fusent pour trouver et décrire au mieux les plus grand nombres premiers possibles. Le record a d’ailleurs été battu très récemment, ce 3 janvier 2018 : il est désormais acquis que le nombre suivant est premier :

2^77232917-1

Alors, c’est bien gentil, mais d’où ça vient tout ça ?

Les nombres de Mersenne

Marin Mersenne, religieux français ayant donné son nom aux nombres qui nous intéressent aujourd’hui.

Parmi les nombres premiers, il existe certaines sous-familles plus ou moins remarquables, et parmi celles-ci figurent les nombres de Mersenne premiers.

Un nombre de Mersenne est un nombre qui peut s’écrire sous la forme 2^p – 1, où p est un entier strictement positif. Ce nombre est plus simplement noté M_p. Par exemple, 7 peut s’écrire 7 = 2³ – 1, c’est donc un nombre de Mersenne, et on le notera, conformément à ce que nous avons écrit plus tôt, M₃. Vous l’aurez alors sans doute deviné, un nombre de Mersenne premier est un nombre qui est à la fois de Mersenne et premier. C’est le cas de 7, mais aussi de 3, de 31, où de notre nouveau nombre premier record.

Pour qu’un nombre de Mersenne M_p soit premier, il faut avant tout que l’entier p soit lui-même premier. Par exemple, M₄ ou M₄₂ ne peuvent être des nombres premiers, puisque 4 et 42 ne le sont pas eux-mêmes.

Cette condition est toutefois loin d’être suffisante !
Par exemple, le nombre M₁₁ = 2¹¹ – 1 = 2047 = 23 x 89 et n’est donc pas premier.

Revenons en au nombre qui nous intéresse : 2^77232917-1. Ce nombre est en réalité le 50ème nombre de Mersenne premier qui a été démontré comme étant premier à ce jour. Attention, cela ne signifie pas qu’il y en a exactement 49 qui soient plus petits que celui-ci : d’autres ont pu échappé aux mailles du filet !

Toujours est-il que ce nombres est grand, très grand : pour l’écrire en entier, il vous faudrait écrire pas moins de 23 millions de chiffres (23.249.525 pour être exact). Si vous préférez le binaire, vous pouvez également vous amuser à écrire 77.232.917 fois le chiffre 1.

Pour vous faire passer cette folle envie, sachez que sur un Document Word écrit en Times New Roman, avec une taille de police de 10 et les marges classiques, il vous faudra pas moins de 3845 pages pour en venir à bout… Bon courage !

Et si l’on remonte dans le temps, il s’avère que les précédents nombres premiers records étaient également des nombres de Mersenne. Il doit bien y avoir une raison derrière tout cela !

Le test de Lucas-Lehmer

En effet, inutile de vous cacher la vérité plus longtemps, il y a bien un secret. Naïvement, pour prouver qu’un nombre est premier, on peut regarder tous les entiers entre 2 et ce nombre, et montrer qu’aucun de ceux-ci ne divise notre nombre. Si l’on est un peu plus futé, on arrêtera cet algorithme à la racine carrée du nombre… Mais tout ceci est affreusement long !

C’est d’ailleurs sur cette longueur que repose la cryptographie actuelle : trouver un nombre premier, factoriser un nombre en produit de nombres premiers est faisable mais très long, mais une fois que la solution est donnée, il est très aisé de la vérifier.

Cette difficulté n’est pas la même pour tous les nombres, et en particulier pour les nombres de Mersenne. Pour cela, faisons appel à la suite de Lucas-Lehmer, que nous nommerons S, et définie comme suit :

• S(1) = 4
• Pour tout n>1, S(n + 1) = S(n)² – 2
  

  Edouard Lucas a créé un premier test de primalité…

Autrement dit, le premier terme de cette suite vaut 4, et chaque terme de la suite est égal au carré du terme précédent auquel on retire 2. Les premiers termes sont les suivants :

4 ; 14 ; 194 ; 37.634 ; 1.416.317.954…

Pour vérifier si un nombre nombre de Mersenne M_p est premier, nous allons regarder le (p-1)-ième terme de cette suite, S(p-1). Si M_p divise S(p-1), alors M_p est premier ! Et réciproquement, si M_p ne divise pas S(p-1), alors M_p n’est pas premier.

Par exemple, 7 = 2³ – 1 = M₃. Nous regardons le deuxième terme de la suite de Lucas-Lehmer, celui-ci vaut 14 et est bien un multiple de 7 : M₃ divise S(2), M₃ est bien premier.

.. Un test de primalité amélioré plus tard par Derrick Lehmer.

Cependant, les nombres de la suite de Lucas-Lehmer grandissent très vite, trop vite pour être utilisés ainsi. Ainsi, il sera bien plus efficace d’utiliser seulement les « restes » de la suite de Lucas-Lehmer, modulo le nombre qui nous intéresse. Cette notion, si vous avez déjà parcouru le blog, vous l’avez rencontrée à plusieurs reprises, mais je vais tout de même en rajouter une couche.

Considérons par exemple M₁₃ = 8191. On se pose alors la question « Est-ce que le 12 ème terme de la suite de Lucas-Lehmer est un multiple de 8191 ou pas ? ». Que ce soit le cas ou non, lui ajouter ou lui retirer 8191 ne changera pas la conclusion : nous allons donc lui retirer un maximum de fois le nombre 8191, jusqu’à obtenir un nombre plus petit que celui-ci.

Une autre manière de l’imaginer, c’est de se dire que nous comptons en boucle : après 8190 vient 0, et on recommence ainsi. C’est ce que l’on nomme l’arithmétique modulaire. Et plutôt que de le faire seulement au 12ème nombre, nous allons faire ce calcul à toute la suite : nous allons exprimer la suite de Lucas-Lehmer modulo 8191.

• S(1) = 4, cela ne change pas. De même, S(2) = 14 et S(3) = 194
• En revanche, S(4) = 37.634, ce qui est plus grand que 8191. Nous allons donc réduire ce nombre modulo 8191, et le calcul nous donnera S(4) = 4870 (modulo 8191)
• Nous repartons alors de ce nombre-ci ! S(5) = 4870² – 2 = 23716898. Un petit coup de modulo 8191 et nous avons notre 5ème terme, S(5)= 3953 (modulo 8191)
• Et ainsi de suite, notre suite vaudra 5970, 1857, 36, 1294, 3470, 128…
• Jusqu’au douzième terme qui vaut 0, ce qui signifie que le nombre de la suite « classique » était en effet un multiple de 8191
• Finalement, M₁₃ est premier !

Vous n’avez peut-être pas tout compris, et ce n’est pas bien grave : l’important est que nous disposons, pour les nombres de Mersenne, d’une méthode simple et efficace pour déterminer si oui ou non, un nombre de Mersenne est premier.

Chasseur de « primes »

(Oui, alors, en anglais, un nombre premier se dit « prime number ». Du coup, je jugeais opportun de placer ce petit jeu de mot, mais le fait de devoir l’expliquer tend à montrer le contraire !)

Bref, nous avons une méthode efficace pour déterminer si un nombre donné est premier ou pas : pas étonnant que ce soient les nombres de Mersenne qui battent des records !

D’ailleurs, le programme qui permet de déterminer si un nombre de Mersenne est premier est en libre service : vous pouvez, avec votre propre ordinateur, partir à la recherche de nombres premiers toujours plus grands [voir liens plus bas]. Mieux, vous pouvez même être récompensés, histoire d’arrondir les fins de mois. Comptez toutefois un certain temps, plus ou moins long, avant d’arriver à destination.

Finissons sur une note plus rabat-joie : hormis le fait de dire « Ouah, on a découvert un super grand nombre premier », l’arrivée de ce nouveau nombre de Mersenne ne bouleverse pas le paysage mathématique. En effet, vu la « simplicité » de ce nombre, il n’y a absolument aucune chance de le voir utiliser en cryptographie par exemple… Mais peut-être son utilité sera-t-elle revue un jour !

Pour compléter

• Envie de lecture ? Regardez cette vidéo de Numberphile qui présente l’ancien plus grand nombre premier connu.
• L’annonce de la découverte du 50ème nombre de Mersenne premier
• Vous aussi, découvrez des nombres premiers toujours plus grand avec le logiciel du Great Internet Mersenne Prime Research (GIMPS)
• Trouver des grands nombres premiers, un problème de tous les jours, sur Science étonnante

Publicité