Comment un ordinateur peut-il générer du hasard ?
L'aléatoire et le pseudo-aléatoire
Qui ne s'est ou ne s'était pas posé la question ? Comment une machine pourrait-elle avoir une notion de hasard alors qu'elle n'est capable d'effectuer que des opérations logiques qui, a priori n'ont aucun lien avec le hasard.
Il faut être conscient qu'aucun algorithme ni expérience pratique ne donne un résultat parfaitement aléatoire. Ainsi il faut plutôt parler de pseudo-aléatoire pour désigner une expérience ou une fonction qui s'approche d'un aléatoire parfait.
Les générateurs congruentiels linéaires
C'est l'algorithme le plus utilisé pour générer des nombres pseudo-aléatoires. Ils ont l'avantage d'être très rapides et peuvent s'avérer être de très bonne qualité. Leur seule contrainte est qu'il faut les initialiser à partir d'un nombre appelé graine (seed en anglais). Deux graines identiques produiront toujours la même séquence de nombres aléatoires, c'est pourquoi il faut s'assurer que la graine de départ soit différente à chaque exécution. Généralement c'est l'unité de temps qui est utilisé comme graine (heure courante exprimée en nanosecondes par exemple) mais on pourrait très bien additionner à cela d'autres facteurs de hasard comme les mouvements de la souris, les touches du clavier, etc.
Un générateur congruentiel linéaire n'est autre qu'une suite mathématique. Elle est définie par trois paramètres (en plus de la graine de départ qui elle est variable) :
- Le multiplicateur
a - L'incrément
c - Le module
m
En connaissant le terme précédent de la suite (ou le terme initial (la graine) si la suite vient d'être initialisée), le calcul du terme suivant s'effectue de la manière suivante Xn+1 = (a * Xn + c) mod m.
Si les paramètres ont été judicieusement choisis (voir choix du multiplicateur et de l'incrément), les m premiers termes apparaitront chacuns une seule et unique fois.
Passé m la suite se mettra à répéter les termes dans le même ordre : c'est sa période.
Ce qui est intéressant c'est que chaque terme apparait de manière uniforme et c'est à partir de cette propriété notable qu'on va pouvoir retourner un nombre pseudo-aléatoire. On ne va pas utiliser le nombre directement, mais plutôt le tronquer pour ne conserver que les bits de poids fort car « plus » aléatoires. On répète cette opération autant de fois que nécessaire pour obtenir le nombre de bits attendus.
Imaginons maintenant que l'on souhaite retourner un nombre entier compris entre 0 et 2n. C'est très simple puisqu'il suffit de retourner le nombre représenté par n bits aléatoires.
Maintenant qu'en est-il pour un nombre entier quelconque, entre 0 et k ? On va chercher le plus petit entier n tel que 2n ≥ k, autrement dit n = ceil(log2(k)).
On génère 2n bits aléatoires que l'on représente en nombre entier r. Si r < k2, on s'arrête et on retourne ce nombre modulo k.
Dans le cas inverse, on n'a pas le choix : il faut recommencer l'opération jusqu'à ce que l'inégalité soit vérifiée.
Cet algorithme retourne des valeurs pseudo équiprobables ; la seule chose qui n'est pas garantie c'est le nombre de fois que l'on devra répéter l'opération si la valeur aléatoire ne vérifie pas l'inégalité. Mais c'est le prix à payer pour obtenir un nombre pseudo-aléatoire compris dans intervalle quelconque, à partir de bits pseudo-aléatoires.
Limites
Le plus gros danger sur lequel il faut être attentif est la prédiction des termes de la suite. En effet, en connaissant les paramètres utilisés par le générateur ainsi qu'un des termes de la suite il est possible de déduire tous les termes suivants (en appliquant l'inversion modulaire). Aussi, si le module est trop petit les nombres qui vont en découler auront l'air « moins » aléatoires que si le module avait été plus grand.
De ce fait, il ne faut pas les utiliser en cryptographie. D'autres algorithmes plus coûteux mais moins biaisés et surtout pratiquement imprédictibles sont utilisés pour cela.
De la même façon, s'il s'agit d'une plateforme en ligne où le hasard prend une place importante (casino virtuel, MMO), il peut être judicieux de bien choisir son générateur aléatoire.
Petite anecdote
Le jeu PacMan datant de 1980 utilisait déjà un générateur congruentiel linéaire pour diriger les fantômes dans le labyrinthe.
Les paramètres utilisés par le développeur Shigeo Funaki (a = 5, c = 1 et m = 8192) forment un générateur qui a une période de "seulement" 1365 ; cela peut tout à fait s'expliquer par les contraintes de l'époque (un microprocesseur Z80 8-bit cadencé à quelques mégahertz tout au plus) :
- La multiplication est très coûteuse. Alors que l'addition est calculée en quelques cycles d'horloge, la multiplication nécessite environ
log2(n)fois plus de cycles. Ici elle peut facilement se faire par un enchainement d'additions, ce qui est bénéfique. - L'addition de l'incrément est un cas particulier car une instruction processeur (
inc) permet directement d'incrémenter une variable. Cette opération est moins coûteuse qu'une addition de deux registres. - Le modulo est calculé grâce à un ET logique car 8192 et une puissance de 2 (
214). Nécessite aussi très peu de cycles.
Le code source en assembleur (commenté et formaté) qui m'a servi à illustrer cet exemple se trouve ici, en particulier la procédure qui génère des octets pseudo-aléatoires se situe au niveau de l'adresse 0x2a23.