Article original : Random Number Generator: How Do Computers Generate Random Numbers?
Par Alexander Arobelidze
Les gens utilisent des nombres aléatoires depuis des millénaires, donc le concept n'est pas nouveau. Des loteries dans l'ancienne Babylone, aux tables de roulette à Monte Carlo, aux jeux de dés à Vegas, le but est de laisser le résultat final au hasard.
Mais en dehors des jeux de hasard, l'aléatoire a de nombreuses utilisations en science, en statistique, en cryptographie et plus encore. Pourtant, l'utilisation de dés, de pièces de monnaie ou de médias similaires comme dispositif aléatoire a ses limites.
En raison de la nature mécanique de ces techniques, la génération de grandes quantités de nombres aléatoires nécessite beaucoup de temps et de travail. Grâce à l'ingéniosité humaine, nous disposons d'outils et de méthodes plus puissants.
Méthodes pour générer des nombres aléatoires
Nombres vraiment aléatoires
_Image d'un dispositif de traitement analogique-entrée numérique-sortie. Photo par Harrison Broadbent_
Considérons deux méthodes principales utilisées pour générer des nombres aléatoires. La première méthode est basée sur un processus physique et tire sa source d'aléatoire d'un phénomène physique qui est supposé être aléatoire.
Un tel phénomène se produit en dehors de l'ordinateur. Il est mesuré et ajusté pour d'éventuels biais dus au processus de mesure. Les exemples incluent la désintégration radioactive, l'effet photoélectrique, le rayonnement de fond cosmique, le bruit atmosphérique (que nous utiliserons dans cet article), et plus encore.
Ainsi, les nombres aléatoires générés sur la base de cette aléatoire sont dits être des nombres "vraiment" aléatoires.
Techniquement, la partie matérielle se compose d'un dispositif qui convertit l'énergie d'une forme à une autre (par exemple, le rayonnement en un signal électrique), d'un amplificateur et d'un convertisseur analogique-numérique pour transformer la sortie en un nombre numérique.
Qu'est-ce que les nombres pseudo-aléatoires ?
_Image de code informatique s'écoulant à travers un écran d'ordinateur. Photo par Markus Spiske._
En alternative aux nombres "vraiment" aléatoires, la deuxième méthode de génération de nombres aléatoires implique des algorithmes computationnels qui peuvent produire des résultats apparemment aléatoires.
Pourquoi apparemment aléatoires ? Parce que les résultats finaux obtenus sont en fait complètement déterminés par une valeur initiale également connue sous le nom de valeur seed ou clé. Par conséquent, si vous connaissiez la valeur de la clé et le fonctionnement de l'algorithme, vous pourriez reproduire ces résultats apparemment aléatoires.
Les générateurs de nombres aléatoires de ce type sont fréquemment appelés générateurs de nombres pseudo-aléatoires et, par conséquent, produisent des nombres pseudo-aléatoires.
Même si ce type de générateur ne collecte généralement aucune donnée à partir de sources de randomisation naturellement présentes, une telle collecte de clés peut être rendue possible lorsque cela est nécessaire.
Comparons quelques aspects des générateurs de nombres vraiment aléatoires ou TRNG et des générateurs de nombres pseudo-aléatoires ou PRNG.
Les PRNG sont plus rapides que les TRNG. En raison de leur nature déterministe, ils sont utiles lorsque vous devez rejouer une séquence d'événements aléatoires. Cela aide beaucoup dans les tests de code, par exemple.
D'autre part, les TRNG ne sont pas périodiques et fonctionnent mieux dans les rôles sensibles à la sécurité tels que le chiffrement.
Une période est le nombre d'itérations qu'un PRNG effectue avant de commencer à se répéter. Ainsi, toutes choses étant égales par ailleurs, un PRNG avec une période plus longue nécessiterait plus de ressources informatiques pour être prédit et craqué.
Exemple d'algorithme pour générateur de nombres pseudo-aléatoires
Un ordinateur exécute du code basé sur un ensemble de règles à suivre. Pour les PRNG en général, ces règles tournent autour des points suivants :
- Accepter un nombre initial, c'est-à-dire une seed ou une clé.
- Appliquer cette seed dans une séquence d'opérations mathématiques pour générer le résultat. Ce résultat est le nombre aléatoire.
- Utiliser ce nombre aléatoire résultant comme seed pour l'itération suivante.
- Répéter le processus pour émuler l'aléatoire.
Maintenant, regardons un exemple.
Le générateur congruentiel linéaire
Ce générateur produit une série de nombres pseudo-aléatoires. Étant donné une seed initiale X0 et des paramètres entiers a comme multiplicateur, b comme incrément, et m comme module, le générateur est défini par la relation linéaire : Xn ≡ (aXn-1 + b)mod m. Ou en utilisant une syntaxe plus adaptée à la programmation : Xn = (a * Xn-1 + b) % m.
Chacun de ces membres doit satisfaire les conditions suivantes :
- m > 0 (le module est positif),
- 0 < a < m (le multiplicateur est positif mais inférieur au module),
- 0 ≤ b < m (l'incrément est non négatif mais inférieur au module), et
- 0 ≤ X0 < m (la seed est non négative mais inférieure au module).
Créons une fonction JavaScript qui prend les valeurs initiales comme arguments et retourne un tableau de nombres aléatoires d'une longueur donnée :
// x0=seed; a=multiplicateur; b=incrément; m=module; n=longueur de tableau souhaitée;
const linearRandomGenerator = (x0, a, b, m, n) => {
const results = []
for (let i = 0; i < n; i++) {
x0 = (a * x0 + b) % m
results.push(x0)
}
return results
}
Le générateur congruentiel linéaire est l'un des plus anciens et des plus connus des algorithmes PRNG.
En ce qui concerne les algorithmes de génération de nombres aléatoires exécutables par des ordinateurs, ils remontent aux années 1940 et 1950 (la méthode du carré médian et le générateur de Lehmer, par exemple) et continuent d'être écrits aujourd'hui (Xoroshiro128+, Squares RNG, et plus).
Un exemple de générateur de nombres aléatoires
Lorsque j'ai décidé d'écrire cet article sur l'intégration d'un générateur de nombres aléatoires dans une page web, j'avais un choix à faire.
J'aurais pu utiliser la fonction Math.random() de JavaScript comme base et générer une sortie en nombres pseudo-aléatoires comme je l'ai fait dans des articles précédents (voir Table de multiplication - Codez votre propre table de multiplication).
Mais cet article lui-même traite de la génération de nombres aléatoires. J'ai donc décidé d'apprendre à collecter des données basées sur une "vraie" aléatoire et de partager ma découverte avec vous.
Voici donc le générateur de nombres "vraiment" aléatoires. Définissez les paramètres et cliquez sur Générer.
Le code récupère les données de l'une des API, grâce à Random.org. Cette ressource en ligne dispose d'une pléthore d'outils utiles et personnalisables et est accompagnée d'une excellente documentation.
L'aléatoire provient du bruit atmosphérique. J'ai pu utiliser des fonctions asynchrones. C'est un énorme avantage pour l'avenir. La fonction principale ressemble à ceci :
// Génère un nombre aléatoire dans l'intervalle indiqué par l'utilisateur
const getRandom = async (min, max, base) => {
const response = await fetch("https://www.random.org/integers/?num=1&min="+min+"
&max="+max+"&col=1&base="+base+"&format=plain&rnd=new")
return response.text()
}
Les paramètres qu'elle prend permettent à un utilisateur de personnaliser la sortie des nombres aléatoires. Par exemple, min et max vous permettent de définir des limites inférieure et supérieure sur la sortie générée. Et base détermine si la sortie est imprimée en binaire, décimal ou hexadécimal.
Encore une fois, j'ai choisi cette configuration, mais il y en a beaucoup d'autres disponibles à la source.
Lorsque vous cliquez sur le bouton Générer, la fonction handleGenerate() est appelée. Elle invoque à son tour la fonction asynchrone getRandom(), gère les erreurs et produit les résultats :
// Gestion de la sortie
const handleGenerate = () => {
handleActive(generateButton)
const base = binary.checked ? 2 : decimal.checked ? 10 : 16
if (!minimum.value || !maximum.value) {
prompter.style.color = 'red'
prompter.textContent = "Entrez les valeurs Min & Max"
} else {
getRandom(minimum.value, maximum.value, base).then((data) => {
resultValue.textContent = data
prompter.textContent = ""
}).catch((error) => {
resultValue.textContent = 'ERREUR'
prompter.textContent = 'Erreur de connexion. Impossible de générer';
})
handleRestart()
}
}
Le reste du code traite de la structure HTML, de l'apparence et du style.
Le code est prêt à être intégré et utilisé dans cette page web. Je l'ai séparé en parties composantes et l'ai fourni avec des commentaires détaillés. Il peut être facilement modifié. Vous pouvez également modifier la fonctionnalité et les styles selon vos besoins.
Voici le lien vers le dépôt GitHub du code complet : https://github.com/sandroarobeli/random-generator