- Générateurs de nombres aléatoires
-
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 séquence de nombres dont on ne peut pas « facilement » tirer des propriétés déterministes, de façon à ce que cette séquence puisse être appelée : suite de nombres aléatoires.
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. 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 apparemment aléatoire des phénomènes quantiques.
Ces générateurs ont une utilité dans de nombreux domaines. Outre les jeux, on peut citer :
- la simulation
- l’analyse
- l'échantillonnage
- la prise de décision
- 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.
Sommaire
Première approche du problème
L'aléatoire : une notion difficile
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. Et ce deuxième point est encore aujourd'hui un véritable problème ! En effet, même pour les mathématiciens, le caractère aléatoire est une notion difficile à appréhender. Comment donner une définition satisfaisante ? Est-il raisonnable de le définir en donnant une liste infinie de tout ce que l'aléatoire n'est pas ?
Le bon choix du phénomène
Puisque l'on ne peut pas définir l'aléatoire, on va profiter du fait que certains phénomènes sont intrinsèquement aléatoires ; et les exploiter pour former les nombres que nous cherchons. Le problème est que ces phénomènes ne sont souvent aléatoires qu'en apparence.
Par exemple : lors du lancement d'un dé, il est possible 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, l'action réaction...). 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. Imprévisible mais non pas aléatoire. On notera bien la différence. On est en fait ici dans le domaine de la théorie du chaos.
Les problèmes de biais
Que le phénomène soit imprévisible plutôt qu'aléatoire ne pose pas un problème pour la suite 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, on a tendance à mettre une face au dessus plus souvent que l'autre. Or il se trouve que la face qui était au-dessus au début a 20% de chance de plus que l'autre d'être la face obtenue.[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 de générateurs de nombres aléatoires
Générateurs reposants sur des phénomènes imprévisibles
On ne peut pas 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 des 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...
Générateurs reposants sur des algorithmes
- article détaillé : générateur de nombres pseudo-aléatoires
Un algorithme est une suite d'opérations prédéfinies que l'on applique à des paramètres pour les modifier. Si l'on applique le même traitement aux mêmes paramètres, les résultats sont donc identiques. En ce sens, un algorithme est donc déterministe, à 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.
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.
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
Ce sont les meilleurs générateurs. Ils utilisent par exemple les phénomènes physiques suivants :
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. Par exemple, le choix d'un électron de traverser ou non une lame semi-réfléchissante constitue un tel générateur. Toutefois, certains chercheurs prétendent qu'une fonction pseudo-aléatoire pourrait tout aussi bien expliquer les résultats observés.[réf. souhaitée] Dans ce cas, il n'y aurait pas de sens à parler de « vrai » nombre aléatoire.
Générateurs mixtes
Des systèmes utilisent à la fois une source d'entropie physique et des algorithmes pseudo-aléatoires pour produire un flot d'aléa parfait. 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éinité du mélange, etc.).
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, 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 l'algorithme est donnée dans le brevet : Patente N°5 732 138
Tests statistiques
- article détaillé : Test (statistique)
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 que l'on obtient avec un générateur peuvent être considérées comme aléatoires, afin de dire si le générateur est lui-même aléatoire ou non. Pour cela, on vérifie que les séquences obtenues possèdent bien différentes propriétés constitutives du hasard. Cependant, il faut retenir qu'un générateur peut toujours réussir n tests et échouer au n + 1ieme. 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%.
Tests d'adéquation
- articles détaillés : Test du χ² ~ Test de Kolmogorov-Smirnov
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 réellement obtenue par la suite.
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 procède à un test sur la fréquence d'apparition de chaque nombre, celle-ci doit s'approcher de 1/6 grâce au test du χ² qui s'applique aux distributions discrètes.
Si l'on veut tester qu'une distribution continue suit bien une loi normale ou exponentielle ou toute autre loi, on utilisera alors le test de Kolmogorov-Smirnov.
Utilisation des générateurs de nombres aléatoires
Ces générateurs sont utiles dans plusieurs domaines 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.
Jeux
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
Que se 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
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
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
Les utilisations sont là aussi nombreuses, dans des procédures de tests, comme les tests unitaires, et autres méthodes afin de permettre de percer les failles d'un système informatique structuré. Réseau, logiciel, ...
Cryptologie
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.
Parapsychologie
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.
Voir aussi
Liens internes
Liens externes
- (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)
Bibliographie
- Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms - chapitre 3 : Random Numbers (Addison-Wesley, Boston, 1998).
Portail de la physique
Portail de la cryptologie
Portail de l’informatique
Catégorie : Nombre aléatoire
Wikimedia Foundation. 2010.
