Générateur de nombres aléatoires - Définition

Tests statistiques

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 + 1^ieme. 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

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.

Exemples de générateurs de nombres aléatoires

Générateurs reposants sur des phénomènes imprévisibles

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 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,
• 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 reposants sur des algorithmes

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 :

• radioactivité,
• bruits thermiques,
• bruits électromagnétiques,
• mécanique quantique.

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 photon de traverser ou non une lame semi-réfléchissante constitue un tel générateur.

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