LES IRRÉDUCTIBLES NOMBRES PREMIERS

Fétiches des mathématiciens, les nombres premiers obéissent-ils à une règle cachée ?

En science, rares sont les sujets qui piquent encore la curiosité après plus de 2 000 ans de recherche. Les nombres premiers font partie de ces éternels mystères : ils ont tenu en haleine les plus grands mathématiciens et, aujourd’hui, même les ordinateurs les plus puissants se cassent les dents − ou plutôt les circuits − sur les questions qu’on se posait déjà dans l’Antiquité.

La définition de ces nombres est pourtant d’une simplicité désarmante. Un nombre entier est premier s’il n’est divisible que par 1 et par lui-même. Autrement dit, s’il ne peut être « fragmenté » en plus petits éléments. Ainsi, 17 est un nombre premier, mais 15 ne l’est pas, car on peut le décomposer en 3 × 5.

La série commence par 2, 3, 5, 7, 11… et se poursuit à l’infini. « Ce sont les briques fondamentales des mathématiques, l’ADN des nombres entiers », résume Andrew Granville, spécialiste de la théorie des nombres à l’Université de Montréal.

De fait, n’importe quel entier peut se décomposer en une combinaison unique de ces briques de base : 35 est 5 × 7 ; 221 s’écrit 13 × 17 ; et 2 010, 2 × 3 × 5 × 67. Pas autrement. On doit ce « théorème fondamental de l’arithmétique » à Euclide, même s’il n’a été démontré qu’en 1801.

Qu’a-t-on découvert sur ces nombres depuis la Grèce antique ? Pas mal de curiosités, mais l’essentiel nous échappe encore : ils semblent n’obéir à aucune règle, si bien qu’on ne dispose pas de formules simples permettant de révéler tous les nombres premiers, ni d’en énoncer à coup sûr, ni même de trouver celui qui suit ou précède un autre nombre premier.

Si ces trublions sont si durs à cerner, c’est parce qu’ils semblent avoir été semés aléatoirement le long de la ribambelle des entiers, dans l’unique but de torturer les mathématiciens.

Il n’y a qu’à regarder la liste des nombres premiers inférieurs à 100 pour s’en convaincre. Ils sont tous impairs (à l’exception de 2), mais les écarts entre eux n’ont rien de prévisible. Nulle règle ne semble gouverner leur répartition.

Paradoxalement, la distribution des nombres premiers est trop étrange pour n’être due qu’au hasard. Lucile Devin en sait quelque chose. Cette postdoctorante dans l’équipe d’Andrew Granville s’intéresse à un problème simple à formuler, mais difficile à résoudre, « comme tous les problèmes qui concernent les nombres

premiers ». Il se résume comme suit : quel est le reste de la division par 4 d’un nombre premier ? Par exemple, si l’on divise 19 par 4, il reste 3 (4 × 4 = 16 et il reste 3). Si l’on divise 17 par 4, il reste 1. « Dans tous les cas, il n’y a que ces deux réponses, 1 ou 3. Un théorème du 19e siècle dit qu’il n’y a pas de raison pour que l’un ou l’autre se produise plus souvent, indique-t-elle. Or, quand on observe les nombres premiers, il y en a plus qui donnent un reste de 3 et l’on ne sait pas pourquoi. » Armée « d’un papier et d’un crayon », elle essaie de trouver une théorie qui expliquerait ce biais dit de Tchebychev.

En 2016, deux mathématiciens de l’Université Stanford, Kannan Soundararajan et Robert Lemke Oliver, ont trouvé un autre « couac » en passant en revue (par ordinateur) 400 milliards de nombres premiers. Hormis 2 et 5, tous se terminent par le chiffre 1, 3, 7 ou 9. À priori, la probabilité qu’un nombre premier finissant par 1 soit suivi d’un autre se terminant par l’un de ces quatre chiffres est de 25 % pour chaque chiffre si le hasard est respecté. Mais le duo a découvert des irrégularités : ainsi, un nombre premier finissant par 1 a 30 % plus de chances qu’attendu d’être suivi d’un premier se terminant par 3 ou 7. Et il est rare que deux nombres premiers successifs finissent par le même chiffre. « Personne n’avait jamais remarqué cela », s’amuse Andrew Granville.

FAUX CHAOS ?

À première vue, donc, les particules élémentaires de l’arithmétique sont manifestement imprévisibles. Mais si l’on s’éloigne pour observer le tableau d’ensemble, notamment en s’intéressant aux très grands nombres premiers, certaines tendances émergent.

Plus les nombres sont grands, plus la proportion de nombres premiers parmi eux décroît. Cette raréfaction a été mise en équation par Carl Friedrich Gauss au 18e siècle. « À 15 ans, il a remarqué que la densité des nombres premiers autour d’un nombre x est approximativement 1/ln (x) [ ln est le logarithme, une notion bien connue en mathématiques] et cela a été prouvé », détaille Andrew Granville.

Peu importe si le terme logarithme ne vous dit rien : il permet d’estimer les chances qu’un nombre pris au hasard soit premier (et donc d’estimer la proportion de nombres premiers dans un intervalle donné) sans trop se tromper. La preuve qu’il y a bien une sorte d’ordre derrière l’apparent chaos. Par exemple, cette loi prévoit 72 nombres premiers dans l’intervalle entre 1 000 000 et 1 001 000. En réalité, il y en a 75 : pas si mal !

Ce constat est à la base de l’une des plus grandes quêtes des mathématiques : prouver l’hypothèse de Riemann, énoncée par le génie Bernhard Riemann en 1859, qui permettrait de trouver l’emplacement de chaque nombre premier avec une marge d’erreur négligeable. La formule est inexplicable aux communs des mortels (elle repose sur une fonction nommée « zêta »), mais elle pourrait élucider la distribution erratique des nombres premiers, qui se succèdent parfois avec un écart de 2 (les « jumeaux »), de 6 (les « sexy ») ou… de plusieurs millions.

Depuis 160 ans, les mathématiciens essaient sans succès de démontrer cette hypothèse, qui est l’un des sept « problèmes du millénaire » désignés par l’Institut de mathématiques Clay. Cet organisme privé offre une récompense de un million de dollars à quiconque parviendra à résoudre l’énigme…

En attendant, le mystère a du bon. « Quelque part, cela tombe bien qu’il n’y ait pas de formule, sinon tous nos algorithmes de sécurité tomberaient à l’eau ! » indique Lucile Devin. Les transactions par carte bancaire et les échanges de données sur Internet reposent en effet sur une technique de cryptographie qui consiste à trouver les diviseurs premiers d’un nombre immensément grand (plus de 200 chiffres). En l’absence de règles, la seule solution est de tester toutes les combinaisons possibles jusqu’à obtenir le résultat et déchiffrer le message. « Cela prend tellement de temps qu’on peut déceler les attaques avant qu’un pirate y arrive », résume la chercheuse. Grâce à ces nombres irréductibles, nos secrets sont donc bien gardés… pour l’instant.

Ils sont jolis comme tout. Les nombres parfaits sont des entiers égaux à la somme de leurs diviseurs. Ainsi, 6 se divise par 2, 3 et 1. En additionnant 2, 3 et 1, on arrive à 6 ! Même chose pour 28, somme de 1 + 2 + 4 + 7 + 14. N’est-ce pas magnifique? Il sont assurément mythiques depuis des millénaires. Plusieurs textes religieux affirment ainsi que la Terre a été créée en 6 jours. Le cycle lunaire est aussi harmonieux avec ses 28 jours. Deux nombres dits « parfaits », terme élaboré par les pythagoriciens il y a plus de 2 500 ans. « Les mathématiques et la philosophie étaient liées à l’époque, rappelle Chantal David, professeure de mathématiques à l’Université Concordia. Dans les deux cas, on étudiait l’Univers. » Environ 300 ans avant notre ère, Euclide d’Alexandrie s’est intéressé à ces étrangetés de façon mathématique et a découvert une manière de les repérer. Il lui suffisait d’abord de trouver un nombre premier résultant d’une puissance 2 de laquelle on soustrait 1. Par exemple,

2×2=4

4×2=8

8–1=7

En multipliant ce nombre premier (7) par le résultat de la multiplication par 2 précédente (ici le 4), on obtient un nombre parfait : 28. La formule d’Euclide résume cela. Lui-même est parvenu à désigner les quatre plus petits.

Puis, « 2 000 ans plus tard, [le mathématicien suisse] Leonhard Euler a montré que les seuls nombres parfaits pairs sont ceux prévus par la formule d’Euclide, poursuit Chantal David. Cela a donné le théorème d’Euclide-Euler; on l’enseigne à l’université dans les cours de théorie des nombres. »

DES NOMBRES IMMENSES

Plusieurs mystères les entourent toujours. Pour commencer, en existe-t-il un nombre infini? « En utilisant un modèle probabiliste qui englobe toutes nos connaissances actuelles, on en obtient une infinité, explique la mathématicienne. Mais il y a peut-être une relation qu’on n’a pas vue, quelque chose qu’on n’a pas mis dans nos modèles. »

Même si la réponse n’est pas précise, des travaux ont néanmoins révélé que les nombres parfaits ne courent pas les rues. La distance entre deux nombres parfaits croît de façon exponentielle : s’il y en a 2 sous la barre de 100, on n’en compte que 4 sous la barre du million. Au total, on connaît 51 nombres parfaits pour le moment. La grande majorité a été découverte après les années 1950. La dernière trouvaille date de 2018 et comporte pas moins de 49 724 095 chiffres !

À quand le 52e ? « Ces nombres sont tellement grands qu’ils n’entrent pas dans le registre [la mémoire interne] de l’ordinateur, alors il faut trouver d’autres façons de les représenter, dit la professeure David. C’est vraiment une science de travailler avec ces nombres. Cela demande des machines très puissantes, mais surtout de bons algorithmes. Moins ils contiennent d’étapes, plus ils sont rapides. »

L’autre question qui taraude les chercheurs : existe-t-il des nombres parfaits impairs ? Certains affirment même que c’est le plus vieux problème mathématique non résolu. À tout le moins, on sait que, s’il y en avait un, ce serait un mastodonte, puisque des calculs laissent croire qu’il n’en existe pas sous la barre de 10300. À titre de comparaison, l’Univers visible compterait 1080 atomes, selon des estimations !

« On est un peu coincés en ce moment ; les méthodes pour s’attaquer à ce problème ont atteint leurs limites, mentionne Paul Pollack, professeur de mathématiques à l’Université de Géorgie, aux États- Unis, qui a publié plusieurs articles scientifiques sur les nombres parfaits. On peut donc tenter plutôt de voir quelles seraient les conditions nécessaires pour obtenir un nombre parfait impair. Pace Nielsen, un mathématicien, a ainsi montré [ en 2010] qu’il faudrait que ce nombre possède au minimum 10 facteurs premiers. »

M. Pollack s’est tourné vers les cousins des nombres parfaits pour éviter le culde-sac. Un nombre peut en effet adopter le slogan « À deux, c’est mieux » et être parfait avec un copain. Il sera alors considéré comme un nombre « amiable » ou « amical ». Pour cela, il faut que la somme de ses diviseurs soit égale à la valeur de son « ami » et que la relation soit réciproque. Cette citation attribuée à Pythagore dit tout : « Un ami est l’autre moi-même comme sont 220 et 284. » L’addition des diviseurs de 220 le démontre bien :

Plusieurs milliers de couples ont été mis au jour au fil des siècles. Fait intéressant : les nombres amiables impairs existent (12 285 et 14 595 sont les premiers).

Il y a ensuite les nombres sociables. Il s’agit de la version à plusieurs amis des amiables. Pensons à un groupe de quatre nombres. La somme des diviseurs du premier donne le second nombre et ainsi de suite jusqu’à ce qu’on revienne au premier nombre ; la boucle est bouclée ! Sans oublier les pseudoparfaits, égaux à la somme de certains de leurs diviseurs. Puis les near-perfect (pour lesquels nous ne risquerons pas de traduction libre !) : égaux à la somme de tous leurs diviseurs, sauf 1. Paul Pollack a fait un Euclide de lui-même et tenté en 2012 de définir des règles pour en construire. Il existe aussi les triparfaits, les sublimes, les quasi-parfaits (différents des near-perfect)… Autant de variations autour d’un même thème.

Il faut continuer la recherche, déclare le professeur Pollack. « En aucun cas je ne prétends que ces nombres sont des problèmes centraux en mathématiques. Mais leur étude peut mener à des découvertes centrales. Pierre de Fermat, par exemple, est parvenu à ses découvertes en partie parce qu’il s’intéressait aux nombres parfaits. » De splendides catalyseurs !

Pour générer des nombres au hasard, on peut très bien jouer à pile ou face, lancer un dé ou encore tirer des boules, à la façon de Loto-Québec. Le mathématicien Pierre L’Ecuyer se rappelle avoir employé des tables, c’est-à-dire des livres contenant uniquement des nombres listés aléatoirement, pour réaliser des études statistiques à la fin des années 1960. « On choisissait dans notre tête deux chiffres pour déterminer quelle page et ensuite quelle ligne on allait utiliser ! »

Ces diverses techniques sont évidemment bien trop longues à exécuter. « Elles ne répondent pas aux besoins d’aujourd’hui, dit le professeur de l’Université de Montréal. Pour vous donner une idée, les simulations de réactions nucléaires au CERN [l’Organisation européenne pour la recherche nucléaire] requièrent plusieurs millions de nombres par seconde. Personne ne peut tirer des boules à cette vitesse ! »

Les nombres aléatoires (ou les suites de bits, des 0 et des 1) sont pourtant essentiels pour désigner quels patients recevront le placébo dans un essai clinique, pour encoder de l’information ou pour perfectionner une chaîne de production dans une usine grâce à la simulation. Deux types de générateurs de nombres comblent cette demande : ceux basés sur des algorithmes et ceux fondés sur des phénomènes physiques.

Les premiers ne fournissent pas réellement de nombres au hasard. Et c’est exactement pour cette raison que certains les apprécient ! Imaginons une suite de 200 bits qui sert de point de départ. Un générateur algorithmique appliquera une fonction sur cette suite. « C’est un bout de code qui va prendre les 200 bits et les brasser, les changer, inverser des 0 et des 1 à certains endroits, explique Pierre L’Ecuyer. À la fin, on obtient un nouveau bloc de 200 bits. Puis on applique une nouvelle fois la même fonction successivement pour obtenir la prochaine suite. » Ainsi, rien n’est plus prévisible que le prochain nombre généré ; c’est un système déterministe.

Cette façon de faire est utile en simulation, dont le but est souvent d’évaluer la performance de différentes politiques de gestion. « Si je simule un centre d’appels, les nombres aléatoires déterminent combien d’appels vont arriver, la durée des appels, etc. Si je veux pouvoir comparer deux façons de distribuer les appels parmi les agents, il faut que j’aie les mêmes nombres aléatoires. »

Mais les suites de nombres en ellesmêmes ont de belles qualités statistiques. Les bons algorithmes sont conçus de sorte qu’une même valeur revienne exactement le même nombre de fois qu’une autre. « On peut faire une analyse mathématique et le prouver avec des théorèmes », indique le professeur L’Ecuyer, qui fait partie des quelques rares chercheurs dans le monde qui perfectionnent les générateurs algorithmiques.

Il déplore le manque d’intérêt pour ce champ d’activité, alors que les propriétés des ordinateurs changent et que les utilisateurs gagneraient à travailler avec des générateurs appropriés. « Les gens qui construisent des logiciels très populaires prennent parfois des algorithmes dans de vieux livres ; ils ne connaissent pas ça et mettent n’importe quoi. » Il prend d’ailleurs un malin plaisir à demander à ses étudiants de tester la qualité d’un générateur qu’il sait médiocre !

LE PHYSIQUE DE L’EMPLOI

Ce similihasard n’est pas optimal en cryptographie ou pour la loterie. Les phénomènes physiques peuvent alors nourrir des générateurs. Attention, la physique est généralement prévisible. « Si je connais les paramètres d’un système, il n’y a pas de hasard possible : on possède les équations pour savoir ce qui va se passer et il ne reste qu’à les résoudre » , souligne le professeur de physique de l’Université de Sherbrooke Bertrand Reulet.

Il faut donc opter pour un système chaotique, c’est-à-dire un phénomène qui peut donner des résultats différents malgré des conditions initiales en tous points similaires.

Une simple lampe à lave peut faire le travail − vous vous souvenez, ces lampes décoratives qui forment des bulles de cire se détachant au fil du temps ? « Prédire à quel moment il va y avoir une bulle est très difficile ! » assure le chercheur. Une entreprise de services de sécurité Internet, Cloudflare, a ainsi créé un mur de 100 lampes scrutées par une caméra pour obtenir des nombres destinés au cryptage. Sans blague ! Mais là encore, on peut finir par repérer des constantes (bien que ce soit plus difficile). « L’intelligence artificielle pourrait trouver ce qui va se passer. »

La physique quantique, celle qui régit l’infiniment petit, vient à la rescousse des chercheurs. Avec elle, tout est aléatoire ! C’est un peu par hasard (quoi d’autre !) que Bertrand Reulet a conçu une nouvelle technique, maintenant brevetée. « Mon sujet de recherche, ce sont les signaux quantiques. C’est de la physique fondamentale ; on ne cherche pas à construire quelque chose. On mesure les fluctuations aléatoires du courant électrique. » Il leur a néanmoins trouvé une utilité.

Le concept est tout simple : il utilise deux métaux séparés par un isolant très fin (un mauvais contact, en somme). « Un électron, c’est une onde. Il n’est pas localisé en un point. Il est capable de “voir” que, de l’autre côté de l’isolant, il y a de la place pour lui. Il peut disparaître pour réapparaître de l’autre côté. C’est ce qu’on appelle l’effet tunnel. » Il est impossible de prédire combien d’électrons franchiront l’obstacle dans la prochaine seconde. Suivre l’intensité du courant électrique dans le temps est donc une façon de produire des bits et des nombres aléatoires. Avec une équipe de l’École de technologie supérieure de Montréal, le professeur Reulet travaille à la construction d’un prototype. Ce dispositif, qu’il souhaite commercialiser, tient sur une puce.

Voilà une solution qui pourrait améliorer la sécurité informatique. « Mais le premier problème, en cryptographie, ce ne sont pas les générateurs. Ce sont plutôt les administrateurs qui utilisent des mots de passe de type “1234” ! » rigole Bertrand Reulet.