Générateur de nombres aléatoires
Pour les articles homonymes, voir GNA.
Un générateur de nombres aléatoires, random number generator (RNG) en anglais, est un dispositif capable de produire une suite de nombres pour lesquels il n'existe aucun lien calculable entre un nombre et ses prédécesseurs, de façon que cette séquence puisse être appelée « suite de nombres aléatoires ».
Général
[modifier | modifier le code]Par extension, on utilise ce terme pour désigner des générateurs de nombres pseudo aléatoires, pour lesquels ce lien calculable existe, mais ne peut pas « facilement » être déduit.
Des méthodes pour obtenir des nombres aléatoires existent depuis très longtemps et sont utilisées dans les jeux de hasard : dés, roulette, tirage au sort, mélange des cartes, etc[1]. Elles peuvent toutefois souffrir (et souffrent généralement) de biais. Actuellement, les meilleures méthodes, censées produire des suites véritablement aléatoires, sont des méthodes physiques qui profitent du caractère aléatoire des phénomènes quantiques.
Ces générateurs ont une utilité dans de nombreux domaines[2]. Outre les jeux, on peut citer :
- la simulation (en particulier les méthodes de Monte-Carlo[3]) ;
- l'analyse ;
- l'échantillonnage (en particulier les sondages d'opinion[4]) ;
- la prise de décision ;
- l'aide à la production de logiciels fiables (génération de jeux de test) ;
- la sécurité informatique (cryptologie).
La nécessité d'obtenir des données aléatoires est présente dans bien d'autres domaines. Certains domaines peuvent se contenter de données pseudo-aléatoires et utilisent des générateurs qui s'approchent plus ou moins d'un aléa parfait.
Première approche du problème
[modifier | modifier le code]L'aléatoire : une notion difficile
[modifier | modifier le code]Produire des nombres aléatoires pose une double difficulté : la production en elle-même bien sûr, mais surtout savoir caractériser le hasard. En effet, le caractère aléatoire est une notion difficile à appréhender, mais des travaux récents ont permis de comprendre comment caractériser une série véritablement aléatoire, notamment les travaux sur la complexité de Kolmogorov de Per Martin-Löf et d'Andreï Kolmogorov[5].
Dans son livre Exposition de la théorie des chances et des probabilités, Augustin Cournot consacre un chapitre de 18 pages à définir le hasard[6]. Il résume ce chapitre en une définition devenue célèbre qui est toujours acceptée de nos jours[7] :
« Les événements amenés par la combinaison ou la rencontre de phénomènes qui appartiennent à des séries indépendantes, dans l'ordre de la causalité, sont ce qu'on nomme des événements fortuits ou des résultats du hasard »
Cette définition est utilisable pour construire de bons générateurs de nombres aléatoires, par le croisement d'un générateur de nombres (ayant de « bonnes » propriétés, notamment la possibilité de générer tous les nombres parmi lesquels on veut faire le tirage) avec un générateur d'arrêt indépendant.
Le bon choix du phénomène
[modifier | modifier le code]Puisque définir l'aléatoire est difficile et est incompatible avec le « calcul », on va profiter du fait que certains phénomènes sont intrinsèquement aléatoires et les exploiter pour former les suites que nous cherchons. Le problème est que la plupart des phénomènes ne sont souvent aléatoires qu'en apparence.
Par exemple, dans l'approche qui prévaut après Laplace, lors du lancement d'un dé, il est potentiellement possible, à condition de connaître la configuration initiale avec une précision extrême, de prédire quelle sera la face supérieure (grâce aux lois de la physique qui s'appliquent au dé, en l'occurrence : la gravitation, le principe fondamental de la dynamique, les lois de Newton...). En contrepartie, les problèmes d'incertitude sur les conditions initiales et la forte dépendance du problème à ces conditions rend le trajet du dé imprévisible, mais pas aléatoire. La théorie du chaos explique cette imprévisibilité en montrant la grande instabilité de l'issue du mouvement en fonction des conditions initiales.
Les problèmes de biais
[modifier | modifier le code]Que le phénomène soit imprévisible plutôt qu'aléatoire ne pose pas un problème pour les exemples qui suivent si tant est que les conditions initiales sont, elles, aléatoires, mais ce n'est pas toujours le cas. Par exemple, dans le cas du pile ou face, un humain aura tendance à mettre l'avers[Où ?] plus souvent que le revers ou vice-versa[réf. nécessaire]. Le phénomène présente donc un biais, dans le sens où, dans une certaine mesure, on peut prédire le résultat que l'on va obtenir.
Exemples
[modifier | modifier le code]Générateurs reposant sur des phénomènes imprévisibles
[modifier | modifier le code]
On ne peut pas toujours les appeler véritablement générateurs de nombres aléatoires, car ils sont souvent biaisés ou insuffisamment sûrs. Mais ce sont des moyens souvent pratiques pour produire une petite quantité de nombres aléatoires « à la main ».
On y trouve, comme dit en introduction :
- les dés,
- la roulette,
- le tirage au sort (loto et autres),
- les différentes méthodes de mélange des cartes,
- le pile ou face,
- l'arrêt à l'aveugle d'un chronomètre,
- la méthode traditionnelle de distribution des parts de galette des rois...
Certaines de ces méthodes répondent bien à la définition de Cournot (et produisent un hasard très satisfaisant), et d'autres moins bien (le mélange des cartes, par exemple).
Générateurs reposant sur des algorithmes
[modifier | modifier le code]Un algorithme est une suite d'opérations prédéfinies que l'on applique à des paramètres pour les modifier. Pour un algorithme déterministe, si l'on applique le même traitement aux mêmes paramètres, les résultats sont identiques. Un algorithme déterministe est à l'opposé de ce que l'on veut obtenir. Pourtant certaines opérations sont suffisamment imprévisibles pour donner des résultats qui semblent aléatoires. Les nombres obtenus sont donc appelés pseudo-aléatoires[8].
La principale raison pour laquelle on utilise de tels nombres est qu'il est plus facile d'en produire et que les méthodes sont plus efficaces. Il existe des domaines où l'utilisation de ces nombres à la place de « vrais » nombres aléatoires est possible. Ceci est possible à condition d'effectuer une étude numérique rigoureuse pour le prouver. On peut citer les traitements de signaux et les télécoms où une séquence pseudo-aléatoire suffisamment longue remplace de façon simple et satisfaisante un trafic réel.
Mais dans certaines circonstances, l'utilisation de nombres pseudo-aléatoires à la place de « vrais » nombres aléatoires peut totalement compromettre l'étude réalisée ou l'application voulue. C'est par exemple le cas en cryptologie où les clefs de chiffrement doivent être parfaitement aléatoires pour garantir une sécurité maximale (si l'on exclut une cryptanalyse de l'algorithme).
Générateurs reposant sur des phénomènes physiques
[modifier | modifier le code]Ils utilisent par exemple les phénomènes physiques suivants[9] :
- radioactivité,
- bruits thermiques,
- bruits électromagnétiques,
- mécanique quantique[10],
- le souffle direct dans un micro,
- une antenne radio pour capter des ondes,
- la comparaison de deux photos sur une scène avec beaucoup de mouvements.
Selon l'interprétation classique de la théorie quantique, les meilleurs générateurs aléatoires (c'est-à-dire ceux qui produiraient de vrais nombres aléatoires), seraient ceux qui utilisent les phénomènes quantiques[10]. Par exemple, le fait qu'un photon traverse ou non une lame semi-réfléchissante constitue un tel générateur[11].
Le site, en ligne Random ((en) « What's this fuss about true randomness? ») utilise des phénomènes météorologiques.
Générateurs mixtes
[modifier | modifier le code]Des systèmes utilisent à la fois une source d'entropie physique et des algorithmes pseudo-aléatoires pour produire un flot parfait d'aléas. En 1996, le cryptologue Landon Noll et son équipe de Silicon Graphics développent et brevètent un système basé sur les lampes à lave. Le mélange des boules de cire dans la lampe est chaotique car plusieurs phénomènes physiques interviennent dans ce système très complexe (turbulences, température variable, non-homogénéité du mélange, etc.)[12].
L'idée est de numériser six lampes de ce type grâce à une caméra. L'image est ensuite hachée grâce à SHA-1 (une fonction de hachage cryptographique). On obtient alors la graine du générateur cryptographique de nombres pseudo-aléatoires Blum Blum Shub[13], celui-ci produit le flot final de données. Le taux de production des graines était de 8000 bits par seconde sur le matériel de l'époque.
La description exacte de la procédure est donnée dans le brevet Patent No 5 732 138.
Tests statistiques
[modifier | modifier le code]
Il est assez difficile de dire si une suite est ou non aléatoire.
D'une part parce qu'on ne peut parler d'une suite aléatoire que si elle est infinie : dans le cas d'une suite finie, toutes les suites possibles ont une certaine probabilité, et si elle n'est pas nulle, la suite doit donc apparaître. Si ce n'était pas le cas, le générateur serait biaisé. En clair, on ne peut pas dire qu'un générateur est biaisé à la vue d'une suite qui ne paraîtrait absolument pas aléatoire ; car cette suite doit bien apparaître avec une certaine fréquence. Seul le fait que la suite apparaisse avec une mauvaise fréquence (trop forte ou trop faible) permet de dire que le générateur possède un défaut.
D'autre part, parce qu'on ne sait pas parfaitement caractériser le hasard.
La première difficulté est une véritable difficulté pratique. En effet, si l'on ne peut prouver qu'une suite est aléatoire que si elle est infinie, alors seuls des calculs théoriques peuvent permettre de prouver qu'une suite possède cette propriété. Mais comme on ne sait pas donner une définition de ce caractère, on ne peut alors rien prouver (du faux on tire tout).
En fait, pour contourner ces difficultés on se dit qu'une suite finie est aléatoire si la taille de cette séquence en mémoire est inférieure à la taille de tout programme pouvant l'engendrer. Cette idée est fortement reliée aux machines de Turing. La taille de la plus petite machine de Turing pouvant calculer cette suite est maximale, donc la complexité de la suite aussi. D'ailleurs, en ce sens, la meilleure compression d'un fichier forme ainsi un fichier aléatoire.
On va donc essayer de tester si les séquences produites par un générateur peuvent être considérées comme aléatoires, afin de pouvoir affirmer que le générateur est aléatoire. Pour cela, on vérifie que les séquences obtenues possèdent bien différentes propriétés constitutives du hasard. Mais, en principe, un générateur peut réussir n tests et échouer au (n+1)ème. De plus aucun générateur ne peut réussir tous les tests que l'on pense constitutif du hasard, car il n'existe aucune suite qui possède toutes les propriétés dont la probabilité est de 100 %.[réf. souhaitée]
Tests d'adéquation
[modifier | modifier le code]Afin de vérifier qu'une suite possède telle ou telle propriété, on va inférer sur une distribution de fréquence des nombres aléatoires (distribution qui est due au fait que la suite satisfait la propriété), puis on va essayer de juger de l'adéquation entre la distribution prévue et celle que la suite satisfait.
Si par exemple on souhaite vérifier qu'un générateur (dont les nombres obtenus sont des entiers compris entre 1 et 6) se comporte comme un dé à 6 faces alors on peut procéder à un test sur la fréquence d'apparition de chaque nombre ; cette fréquence doit s'approcher de 1/6 grâce au test du χ²[pourquoi ?] qui s'applique aux distributions discrètes.
Utilisation
[modifier | modifier le code]Ces générateurs sont utiles dans plusieurs domaines[2] et le nombre de leurs applications sera très certainement amené à évoluer au cours du temps. Ils jouent d’ores et déjà un rôle majeur en physique dans les domaines de la simulation et de l’analyse. Mais ils permettent aussi de calculer des intégrales, une valeur approchée de π grâce aux méthodes d’analyses de Monte-Carlo, ou d'améliorer l'efficacité de certains algorithmes.
Jeux
[modifier | modifier le code]Les jeux de hasard nécessitent, dans le cas d'une mise en œuvre informatique par exemple, de pouvoir produire : des nombres entiers au hasard entre deux bornes (simulation de dé), une permutation (mélange d'un jeu de carte), un échantillonnage (tirage au sort), etc.
Simulation
[modifier | modifier le code]Que ce soit pour simuler un phénomène physique, une expérience, la conduite, le pilotage ou n'importe quel jeu les nombres aléatoires sont nécessaires partout.
Analyse
[modifier | modifier le code]Grâce à un échantillonnage bien choisi, parfaitement aléatoire par exemple, on va pouvoir simplifier les analyses que l'on veut effectuer. La méthode de Monte-Carlo par exemple, est le nom donné aux méthodes utilisant les nombres aléatoires pour calculer des valeurs numériques. Comme une intégrale en dimension supérieure à 1 ou une solution d'équation différentielle.
Prise de décision
[modifier | modifier le code]Reliée à la théorie de la décision, à la théorie des jeux et à la recherche de la stratégie optimale. On peut par exemple faire appel à une décision aléatoire lorsque l'on ne dispose pas (encore) de critère plus pertinent (par exemple, lorsqu'une fonction d'utilité donne des valeurs identiques). De façon plus humoristique, on peut ne pas savoir quelle décision prendre dans une situation et utiliser la méthode du « pile ou face » ou du « plouf-plouf » (formulette d'élimination).
Sécurité informatique
[modifier | modifier le code]Les utilisations sont là aussi nombreuses. Ils interviennent dans des procédures de tests, comme les tests unitaires. En générant des données d'entrées aléatoires et en observant le comportement du logiciel, il est possible de détecter les failles (bugs, erreurs) d'un réseau, d'un logiciel ou d'un système informatique structuré.
Cryptologie
[modifier | modifier le code]On peut vouloir produire une clé de chiffrement pour les méthodes de chiffrement symétriques. L'intérêt est que, si la clé est parfaitement aléatoire, la complexité d'une attaque par recherche exhaustive est maximisée. Les nombres aléatoires sont omniprésents dans ce domaine. Le chiffrement par flot consiste à utiliser un XOR entre les données et une suite aléatoire. En cryptographie asymétrique, il est nécessaire de produire de grands nombres aléatoires avec des contraintes supplémentaires (premier, premier entre eux, etc.). De plus, un texte chiffré doit s'approcher le plus possible d'un fichier au contenu aléatoire pour limiter les fuites d'information.
Algorithmique
[modifier | modifier le code]L'introduction d'un aléa peut servir à produire des algorithmes efficaces.
Parapsychologie
[modifier | modifier le code]Certaines expériences de parapsychologie portant sur la psychokinèse utilisent ce genre de dispositif. Lors de ces expériences, le sujet tente d'influencer par son intention la sortie du générateur aléatoire. De tels générateurs sont par exemple utilisés dans le tychoscope.[Information douteuse]
Voir aussi
[modifier | modifier le code]Bibliographie
[modifier | modifier le code]- Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms - chapitre 3 : « Random Numbers » (Addison-Wesley, Boston, 1998)
Articles connexes
[modifier | modifier le code]- Suite aléatoire
- Générateur de nombres pseudo-aléatoires
- Tests Diehard
- Tirage (mathématiques)
- Algorithme probabiliste
- Méthode de Monte-Carlo
Liens externes
[modifier | modifier le code]- (en) Randomnumbers.info - génère des nombres aléatoires à la demande (Les nombres sont produits à partir d'un processus basé sur la physique quantique)
- (en) Quantis - générateur de nombres aléatoires basé sur la physique quantique
- (en) Random.org – produit des bits aléatoires ou d’autres quantités (Les nombres sont produits à partir des bruits atmosphériques)
- (en) Théorie et générateurs aléatoires (Les nombres sont produits à partir d'un capteur CCD)
- (en) Sélection aléatoire publiquement vérifiable (RFC 3797 est utilisé par exemple pour le choix du préfixe xn dans le Nom de domaine internationalisé)
Notes et références
[modifier | modifier le code]- Dominique Lecourt (dir.) et Thomas, ... Jean Gayon, Dictionnaire d'histoire et philosophie des sciences, Paris, Presses universitaires de France, (ISBN 2-13-054499-1 et 978-2-13-054499-9, OCLC 470598620, lire en ligne), Article Hasard
- « Le hasard et ses lois », La Recherche, , p. 34-75 (lire en ligne)
- (en) Dirk P. Kroese et Reuven Y. Rubinstein, « Monte Carlo methods », Wiley Interdisciplinary Reviews: Computational Statistics, vol. 4, no 1, , p. 48–58 (DOI 10.1002/wics.194, lire en ligne, consulté le )
- Hélène Yvonne Meynaud, Les sondages d'opinion, (ISBN 978-2-7071-6290-8 et 2-7071-6290-6, OCLC 758870987, lire en ligne)
- Sylvain Perifel, Complexité algorithmique, Ellipses, impr. 2014, cop. 2014 (ISBN 978-2-7298-8692-9 et 2-7298-8692-3, OCLC 880368771, lire en ligne)
- Augustin Cournot, Exposition de la théorie des chances et des probabilités, Paris, (lire en ligne)
- Marcel Conche La métaphysique du hasard Paragraphe 11
- (en) Pierre L’Ecuyer, « Random Number Generation », dans Handbook of Computational Statistics: Concepts and Methods, Springer, (ISBN 978-3-642-21551-3, DOI 10.1007/978-3-642-21551-3_3, lire en ligne), p. 35–71
- Roger Dube, Hardware-based computer security techniques to defeat hackers : from biometrics to quantum cryptography, Wiley, (ISBN 978-0-470-42549-7, 0-470-42549-0 et 978-0-470-42547-3, OCLC 264703219, lire en ligne)
- Miguel Herrero-Collantes et Juan Carlos Garcia-Escartin, « Quantum random number generators », Reviews of Modern Physics, vol. 89, no 1, , p. 015004 (DOI 10.1103/RevModPhys.89.015004, lire en ligne, consulté le )
- Conférences d'Alain Cosnes (vidéo sur YouTube)
- (en) « Totally random », Wired, (lire en ligne)
- L. Blum, M. Blum et M. Shub, « A Simple Unpredictable Pseudo-Random Number Generator », SIAM Journal on Computing, vol. 15, no 2, , p. 364–383 (ISSN 0097-5397, DOI 10.1137/0215025, lire en ligne, consulté le )
