Générateurs de nombres pseudo-aléatoires

Générateurs de nombres pseudo-aléatoires

Les générateurs 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. Les nombres générés sont donc supposés être suffisamment indépendants les uns des autres, et aucune structure évidente ne doit apparaître.

Les suites de nombres aléatoires sont utilisés bien sûr dans les jeux mais aussi dans des applications aussi diverses que le traitement d'image, les tests, les simulations ou la cryptographie.

On attend d'un générateur de nombres pseudo-aléatoires :

La méthode de Von Neumann

La méthode du carré médian (middle-Square method) a été décrite pour la première fois vers 1240 dans un manuscript d'un frère franciscain connu sous le nom de frère Edvin. Elle fut ensuite réinventée par John Von Neumann en 1946 qui l'utilisa pour l'ENIAC (avec 10 chiffres). Elle est très imparfaite (en autre parce qu'elle converge toujours vers 0 ou bien qu'on retrouve très rapidement les mêmes nombres) mais elle fourni tout de même un moyen simple de produire des nombres pseudo-aléatoires. L'algorithme utilisé est trivial :

  1. Commencer par un nombre aléatoire de n chiffres.
  2. L'élever au carré afin d'obtenir un nombre de 2*n chiffres. Ajouter des zéros à droite si nécessaire.
  3. Extraire les n chiffres du milieu. Ce sera le prochain nombre aléatoire.
  4. Recommencer

L'application ci-dessous illustre le fonctionnement de cet algorithme, en partant du nombre

Démonstration de la méthode du carré médian

La méthode de Fibonacci

Cette méthode est basée sur la suite de Fibonacci modulo la valeur maximale désirée. Elle demande peu de ressources et est très simple à implémenter. Toutefois, sa qualité dépend fortement des nombres utilisés pour l'initialiser. On la formalise ainsi :

xn=(xn-1+xn-2) mod M avec x0 et x1 en entrée. C'est à dire que chaque terme de la suite est la somme des deux termes qui le précèdent, modulo un nombre M. C'est donc une congruence additive.

L'application ci-dessous illustre le fonctionnement de cet algorithme, en partant des nombres et ainsi que de comme modulo.

Démonstration de la méthode de Fibonacci

Les générateurs congruentiels linéaires

Il s'agit de l'algorithme le plus utilisé pour produire des nombres aléatoires. Il a été inventé en 1948 par le mathématicien américain Derrick Henry Lehmer.

Pour fabriquer un générateur à congruence linéaire, il faut 4 nombres :

Avec ces quatres nombres, on construit la récurrence :

xn+1=(a*xn+b) modulo M

L'application ci-dessous illustre le fonctionnement de cet algorithme, en partant du germe , du multiplicateur , de l'incrément ainsi que de comme maximum.

Démonstration d'un générateur à congruence linéaire

Avec cet algorithme, le choix de a, b et M sont primordiaux. Pour maximiser la période du générateur, afin qu'elle soit égale à M, on observera les conditions suivantes :

Dans le cas où b est nul, la période est maximale si :

Quelques exemples de générateurs :

Le générateur de Tausworthe

L'algorithme de Tausworthe (aussi appelé linear feedback shift generator) est un algorithme itératif. Il génére un nombre pseudo-aléatoire en construisant sa représentation binaire. Il peut être utilisé en cryptographie.

Son fonctionnement est simple : il choisit k bits (généralement k=2) de la chaine déjà généré pour calculer le suivant. Les deux bits sélectionnés sont toujours à une distance r. Le bit suivant est calculé en faisant un ou exclusif sur les bits sélectionnés. Ensuite, pour chaque nouveau bit il faut reculer de q positions en arrière pour sélectionner le premier bit , et avancer de d positions pour sélectionner le second.

L'application ci-dessous illustre le fonctionnement de cet algorithme, en partant du germe , de la distance d , et du pas q .

Démonstration d'un générateur de Tausworthe