Comment fonctionne un générateur de nombres aléatoires ?

Un ordinateur est une machine qui suit des instructions à la lettre. Alors comment peut-il lancer une pièce, jeter un dé ou tirer un prénom au hasard ? Réponse courte : la plupart du temps, il ne produit pas du tout de vrais nombres aléatoires. Il produit des nombres qui en ont seulement l’air, et pour la plupart des usages, cela suffit. Voici comment fonctionne un générateur de nombres aléatoires, comment il peut se tromper et comment les outils de ce site choisissent leurs résultats.

Deux sortes de hasard

• Les vrais nombres aléatoires viennent d’un phénomène physique que personne ne peut prévoir : le bruit électrique dans un circuit, la désintégration radioactive, les parasites radio de l’atmosphère. Random.org, par exemple, utilise le bruit atmosphérique.
• Les nombres pseudo-aléatoires viennent d’une formule. On part d’un nombre appelé graine, on le passe dans la formule et on obtient le nombre suivant, puis le suivant. Le résultat a l’air aléatoire, mais la même graine donne toujours la même suite.

Le pseudo-aléatoire ressemble à de la triche, mais c’est ce qu’utilisent presque tous les jeux, applications et simulations. C’est rapide, et une bonne formule réussit les tests statistiques que réussit le vrai hasard.

La première méthode informatique et son défaut

Vers 1949, le mathématicien John von Neumann a proposé la méthode du carré médian : on élève un nombre au carré, on garde les chiffres du milieu et on recommence. En partant de 1234, le carré vaut 01522756, donc le nombre suivant est 5227, puis viennent 3215, 3362, 3030, etc.

Cela a l’air aléatoire, mais la méthode tombe dans des boucles. En partant de 2916, on obtient 5030, 3009, 0540, 2916, puis les quatre mêmes nombres à l’infini. Von Neumann le savait. Il utilisait la méthode parce qu’elle était rapide, et il vérifiait les résultats pour repérer les problèmes. Selon sa célèbre boutade, quiconque essaie de produire des nombres aléatoires par l’arithmétique se trouve « en état de péché ».

Avant les ordinateurs : des livres de nombres aléatoires

Les scientifiques avaient tant besoin de nombres aléatoires qu’on les imprimait dans des livres. En 1955, la RAND Corporation a publié A Million Random Digits with 100,000 Normal Deviates, produit à l’aide d’une roulette électronique. Les chercheurs ouvraient le livre à une page au hasard et y lisaient les chiffres. Bien avant cela, on se servait de dés, de pièces et de tirages au sort, comme le raconte notre article sur l’oracle des dés dans l’Antiquité.

Comment fonctionnent les générateurs modernes

Les générateurs pseudo-aléatoires actuels sont bien meilleurs. Parmi les plus courants :

• Mersenne Twister : le générateur par défaut de Python et de nombreux autres outils. Il ne se répète qu’au bout de 2¹⁹⁹³⁷ − 1 nombres, un nombre d’environ 6 000 chiffres.
• xorshift128+ : le générateur derrière Math.random() dans Chrome et les autres navigateurs fondés sur le moteur V8. Très rapide, il convient bien aux jeux et aux animations.
• Les générateurs cryptographiques : ceux qu’on utilise pour les mots de passe et les clés de chiffrement. Le système d’exploitation y mêle des événements physiques imprévisibles, comme de minuscules écarts de temps dans le matériel, si bien que même quelqu’un qui connaît la formule ne peut pas prévoir le nombre suivant.

Les générateurs ordinaires suffisent pour un jeu. Mais si quelqu’un voit assez de leurs résultats, il peut parfois en déduire la suite. Dès que l’équité ou la sécurité compte, c’est le générateur cryptographique qu’il faut choisir.

Un piège caché : le biais du modulo

Même un générateur parfait peut donner des résultats injustes s’il est mal utilisé. Imaginons un octet aléatoire, c’est-à-dire un nombre de 0 à 255, dont on veut tirer un lancer de dé. Le plus simple est de diviser par 6 et de garder le reste. Mais 256 n’est pas divisible par 6, donc quatre des faces reçoivent une chance de plus :

L’écart est faible, mais sur des milliers de lancers, il se voit. La solution est simple : si le nombre aléatoire tombe dans la partie restante inégale, on le jette et on en tire un autre. C’est ce qu’on appelle l’échantillonnage par rejet.

Comment nos outils choisissent

Nos outils Pile ou face, Lancer de dés, Nombre aléatoire, Tirage au sort de prénoms et les autres outils qui partagent le même code utilisent le générateur cryptographique de votre navigateur, appelé crypto.getRandomValues. Ils appliquent aussi l’échantillonnage par rejet, si bien que chaque face, chaque nombre et chaque prénom a exactement la même chance. Les anciens navigateurs qui n’ont pas cette fonction se rabattent sur Math.random(). Tout se passe dans votre propre navigateur ; rien n’est décidé sur notre serveur.

Alors, est-ce vraiment du hasard ?

Pour un pile ou face ou un lancer de dé, un bon générateur vaut mieux que l’objet réel. Les vraies pièces ont un très léger penchant pour la face sur laquelle elles partent, comme l’explique notre article sur la probabilité à pile ou face, et les vrais dés peuvent être légèrement irréguliers. Un bon générateur n’a aucun de ces deux problèmes.

Le plus grand risque, c’est la personne qui lit les résultats. Nous voyons des motifs dans les séries et nous attendons à ce que le résultat « manquant » finisse par tomber. C’est le sophisme du joueur, et il trompe les gens bien plus souvent qu’aucun ordinateur. Pour voir à quel point nous sommes mauvais pour inventer nous-mêmes des nombres au hasard, lisez « Peut-on être aléatoire ? ».

Questions fréquentes

Un ordinateur peut-il générer de vrais nombres aléatoires ?

Pas avec une formule seule. Les formules donnent des nombres pseudo-aléatoires qui ont seulement l’air aléatoires. Pour obtenir du vrai hasard, les ordinateurs mesurent des phénomènes physiques imprévisibles comme le bruit électrique, et beaucoup d’appareils ont du matériel prévu pour cela.

Qu’est-ce que la graine d’un générateur de nombres aléatoires ?

C’est le nombre de départ de la formule. La même graine donne toujours la même suite, ce qui est utile pour les tests et pour les jeux qui permettent de partager un monde ou un niveau grâce à sa graine.

Math.random() est-il vraiment aléatoire ?

Non. C’est un générateur pseudo-aléatoire rapide, très bien pour les jeux mais pas pour ce qui doit rester secret ou quand de l’argent est en jeu. Pour cela, les navigateurs proposent crypto.getRandomValues.

Les pile ou face et les dés en ligne sont-ils équitables ?

Oui, s’ils sont bien faits. Nos outils de pile ou face et de lancer de dés utilisent le générateur cryptographique du navigateur avec l’échantillonnage par rejet, si bien que chaque résultat a exactement la même chance.

Qu’est-ce que le biais du modulo ?

Une petite injustice qui apparaît quand on ramène un nombre aléatoire dans un intervalle plus petit en prenant le reste d’une division, et que le compte ne tombe pas juste. L’échantillonnage par rejet la supprime.