Publicité
Sciences

Pourquoi générer des nombres au hasard est si compliqué

09-07-2020

Générer des nombres au hasard n’est pas de tout repos. Les suites de chiffres aléatoires sont pourtant essentielles en simulation, dans les essais cliniques et en sécurité informatique.

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.

 

LISEZ LA SUITE DE CE REPORTAGE DANS LE NUMÉRO DE JUILLET-AOÛT 2020

Pour accéder à l’article complet, consultez notre numéro de juillet-août 2020. Achetez-le dès maintenant.

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 elles-mê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.

Image: Shutterstock

Les générateurs rétro

Ce n’est pas rien : les générateurs de nombres aléatoires existaient avant même l’écriture des nombres ! Des dés ayant plus de 5 000 ans ont ainsi été découverts en Irak et en Iran.

Le hasard à deux possibilités servait également les Romains : cette bonne vieille pièce de monnaie qu’ils lançaient en l’air pour prendre une décision selon la face sur laquelle elle retombait. (Ils seraient probablement surpris d’apprendre qu’une pièce de monnaie n’a pas autant de chances de tomber d’un côté que de l’autre. La position à partir de laquelle elle est lancée favorise légèrement l’une ou l’autre face, avec 51 % des chances, comme l’a montré le mathématicien Persi Diaconis en 2007…)

Bien plus tard, il y a eu les « tables », comme celle du statisticien Leonard Henry Caleb Tippett en 1927, soit un document contenant 41 600 chiffres glanés dans un rapport de recensement. La première « machine » générant des nombres au hasard est apparue juste après, à la fin des années 1930 : elle était constituée d’un bout de carton qui effectuait des rotations grâce à un petit moteur électrique selon une revue historique réalisée par Pierre L’Ecuyer..

Quand les ordinateurs sont arrivés, il fallait se lever de bonne heure pour réussir à obtenir une séquence aléatoire. « En 1969, pour exécuter un programme sur le CDC 6400 [un ordinateur central] de l’Université de Montréal, il fallait porter notre paquet de cartes perforées à un endroit et l’on revenait quelques heures plus tard, ou le lendemain, pour recueillir le résultat du programme sur une pile de papiers », relate Pierre L’Ecuyer.

Aujourd’hui, ces nombres prisés sont à portée de la main : on peut installer un générateur sur un téléphone intelligent !

Publicité

À lire aussi

Sciences

L’intelligence artificielle vient rapidement à bout du cube Rubik

Après les échecs et le jeu de Go, la machine excelle aussi à résoudre le cube Rubik.
Annie Labrecque 23-07-2019
Sciences

L’infatigable Jane Goodall

La célèbre primatologue qui a bravé les interdits pour documenter les mœurs des chimpanzés met aujourd'hui son zèle et sa détermination au service de la planète.
Sciences

Formule 1? Non, Formule E!

Ils sont de plus en plus nombreux à se passionner pour la Formule E, où se joue l’avenir de l’automobile. Montréal pourrait-elle accueillir un Grand Prix de FE?
Daniel Bastien 14-05-2015