Générateurs de nombres aléatoires

Générateurs de nombres aléatoires

Générateur de nombres aléatoires

Page d'aide sur l'homonymie 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 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

Bibliographie

  • Portail de la physique Portail de la physique
  • Portail de la cryptologie Portail de la cryptologie
  • Portail de l’informatique Portail de l’informatique
Ce document provient de « G%C3%A9n%C3%A9rateur de nombres al%C3%A9atoires ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Générateurs de nombres aléatoires de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • 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… …   Wikipédia en Français

  • Generateur de nombres aleatoires — 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • Nombres premiers — Nombre premier 7 est un nombre premier car il admet exactement deux diviseurs positifs …   Wikipédia en Français

  • Generateur de nombres pseudo-aleatoires — Générateur de nombres pseudo aléatoires Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les… …   Wikipédia en Français

  • Générateur De Nombres Pseudo-Aléatoires — Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple, les nombres sont supposés être… …   Wikipédia en Français

  • Générateur de nombres pseudo-aléatoires — Pour les articles homonymes, voir Générateur. Un générateur de nombres pseudo aléatoires, pseudorandom number generator (PRNG) en anglais, est un algorithme qui génère une séquence de nombres présentant certaines propriétés du hasard. Par exemple …   Wikipédia en Français

  • Caractérisation des nombres premiers — Nombre premier 7 est un nombre premier car il admet exactement deux diviseurs positifs …   Wikipédia en Français

  • Générateur aléatoire — 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… …   Wikipédia en Français

  • RNG — 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… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”