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

Introduction

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 approximativement indépendants les uns des autres, et il est potentiellement difficile de repérer des groupes de nombres qui suivent une certaine règle (comportements de groupe).

Cependant, les sorties d'un tel générateur ne sont pas entièrement aléatoires ; elles s'approchent seulement des propriétés idéales des sources complètement aléatoires. John von Neumann insista sur ce fait avec la remarque suivante : « Quiconque considère des méthodes arithmétiques pour produire des nombres aléatoires est, bien sûr, en train de commettre un péché ». De vrais nombres aléatoires peuvent être produits avec du matériel qui tire parti de certaines propriétés physiques stochastiques (bruit d'une résistance par exemple).

La raison pour laquelle on se contente d’un rendu pseudo-aléatoire est : d’une part qu’il est difficile d’obtenir de « vrais » nombres aléatoires et que, dans certaines situations, il est possible d’utiliser des nombres pseudo-aléatoires, en lieu et place de vrais nombres aléatoires ; d’autre part, que ce sont des générateurs particulièrement adaptés à une implantation informatique, donc plus facilement et plus efficacement utilisables.

Les méthodes pseudo-aléatoires sont souvent employées sur des ordinateurs, dans diverses tâches comme la méthode de Monte-Carlo, la simulation ou les applications cryptographiques. Une analyse mathématique rigoureuse est nécessaire pour déterminer le degré d'aléa d'un générateur pseudo-aléatoire. Robert R. Coveyou du Oak Ridge National Laboratory écrivit dans un article que « la génération de nombres aléatoires est trop importante pour être confiée au hasard ».

La plupart des algorithmes pseudo-aléatoires essaient de produire des sorties qui sont uniformément distribuées. Une classe très répandue de générateurs utilise une congruence linéaire. D'autres s'inspirent de la suite de Fibonacci en additionnant deux valeurs précédentes ou font appel à des registres à décalage dans lesquels le résultat précédent est injecté après une transformation intermédiaire. Certains générateurs pseudo-aléatoires sont dits cryptographiques quand certaines contraintes sont satisfaites. Citons entre autres Fortuna, Yarrow ou Blum Blum Shub.

Problèmes expliquant le terme « pseudo-aléatoire »

Utiliser des algorithmes pour créer des nombres aléatoires, sachant ce qu’est un algorithme, peut paraître assez douteux. De plus, étant donné qu’on ne sait pas bien définir le caractère aléatoire, on se demande comment on peut ne serait-ce que vouloir produire une séquence aléatoire à l’aide d’algorithmes.

Ces reproches sont tout à fait fondés et on ne peut les nier. Ce sont les raisons pour lesquelles on parle de générateurs de nombres pseudo-aléatoires. En pratique, il est possible de limiter les conséquences négatives de l’utilisation d’une méthode algorithmique pour générer des nombres aléatoires.

Biais inhérent aux méthodes employées

Comme un générateur de nombres aléatoires est exécuté sur un ordinateur déterministe, il devient de facto un algorithme déterministe. Ses sorties sont inévitablement entachées d'une caractéristique absente d'une vraie suite aléatoire : la périodicité. Avec des ressources limitées (mémoire, nombre de registres, etc.), le générateur retrouvera le même état interne au moins deux fois. Après coup, il entrera obligatoirement dans un cycle. Un générateur non périodique n'est pas impossible, mais nécessite une mémoire croissante pour ne pas se retrouver dans le même état. Pour contourner cet obstacle théorique, le générateur peut commencer dans un état quelconque (la « graine »). Il produira toutefois la même suite si la graine reste identique — ce qui peut être considéré comme un avantage sous certaines conditions, notamment en termes de reproductibilité. De plus, le nombre de graines possibles n'est pas infini et le générateur ne peut produire qu'un nombre limité de séquences différentes.

Pour améliorer la qualité des sorties, on peut introduire des composantes « aléatoires » provenant des imperfections du système, comme par exemple le temps entre deux accès au disque dur ou le nombre de millisecondes depuis le lancement de l'ordinateur. Ces valeurs sont toutefois comprises entre certains intervalles et/ou sont en partie prévisibles. Le système reste pseudo-aléatoire.

Déviation par rapport au hasard parfait

La longueur de la période maximale double à chaque fois qu'un bit est ajouté à l'état interne. Il est facile de construire des générateurs pseudo-aléatoires avec une période plus longue que ce que n'importe quel ordinateur pourrait calculer. Mersenne Twister, un excellent générateur de nombres aléatoires pour les applications non cryptographiques, a une période prouvée mathématiquement de 2¹⁹⁹³⁷ − 1, un nombre astronomique.

La question est ouverte quant à savoir s'il est possible de distinguer une suite pseudo-aléatoire générée algorithmiquement d'une source parfaite d'aléa, et ceci sans connaître la graine du générateur. En cryptographie, la plupart des spécialistes partent du principe que c'est une chose impossible avec la puissance de calcul actuelle. Ce principe est utilisé pour les chiffrements par flot comme RC4 qui procède à un XOR entre une suite pseudo-aléatoire et les données.

En principe, la plupart des générateurs ont des problèmes mathématiques qui peuvent être décelés avec une analyse statistique. La qualité des sorties augmente souvent au détriment de la vitesse de génération et ces paramètres doivent être considérés lors de l'utilisation d'un générateur. Les failles peuvent être les suivantes :

• période plus courte avec certaines graines
• qualité du générateur qui varie fortement selon la graine
• distribution imparfaite, manque d'uniformité
• mauvaise distribution dans un espace de dimension supérieure à 1
• ou au contraire : distribution trop idéale, uniformité trop parfaite
• valeurs successives qui ne sont pas indépendantes (ce qui est toujours le cas, sauf si on injecte des données, issues de sources aléatoires, dans une étape de la génération)
• certains bits dans les sorties sont moins aléatoires (par exemple, le bit n°8 reste souvent à 1)

Les défauts peuvent être importants ou quasiment invisibles. L'algorithme RANDU utilisé pendant plusieurs décennies était biaisé et certains résultats obtenus à l'époque ne peuvent être complètement validés. Il arrive parfois qu'une application pratique permette de déceler le problème (par exemple une simulation physique avec des résultats complètement inattendus), mais il est préférable de faire des tests avant utilisation pour les déceler.