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 :
Une vitesse de génération acceptable,
Qu'il soit reproductible,
Qu'il ressemble bien sûr le plus possible au vrai hasard.
Que la suite crée soit normale.
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 :
Commencer par un nombre aléatoire de n chiffres.
L'élever au carré afin d'obtenir un nombre de 2*n chiffres. Ajouter des zéros à droite si nécessaire.
Extraire les n chiffres du milieu. Ce sera le prochain nombre aléatoire.
Recommencer
L'application ci-dessous illustre le fonctionnement de cet algorithme, en partant du nombre
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.
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 :
Un germe x0 qui doit être un nombre entier positif,
Un multiplicateur a
Un incrément b
qui doit être un nombre entier non nul,
Un nombre M qui définira la taille du plus grand entier possible.
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 :
b doit être premier avec M, c'est à dire PGCD(b,M)=1.
Pour chaque nombre premier p divisant M, (a-1) est un multiple de p.
(a-1) doit être un multiple de 4 si M en est un.
Dans le cas où b est nul, la période est maximale si :
M est premier,
aM-1 est un multiple de M,
aj-1 n'est pas divisible par M pour j=1,j=2..., j=m-2
Quelques exemples de générateurs :
Le générateur xn = (7 5 * xn-1) mod (232 - 1) a été très utilisé dans les années 70/80 par IBM.
Les générateurs xn = (48271 * xn-1) mod (232 - 1) et xn = (69261 * xn-1) mod (232 - 1) ont été considérés par Fishman et Moore en 1986 comme les meilleurs.
Unix utilise ce générateur : xn = (1103515245 * xn-1 + 12345) mod (232)
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 .