1°) Historique

  • J.v.Neuman: "middle square" sur 20 chiffreX² -> 40 chiffre -> on garde (X >> 10) & (10 << 11)-1
    si X n'a pas la bonne "forme", le générateur dégénaire
  • Algorithme de Knuth : (the art of computer programming)
    algo "complexe", à l'aire aléatoire mais très mauvais (pas de bonne propritété)

2°) Suite aléatoire

définition: une suite infinie "Un" de bits est aléatoire si
∀n: le plus petit programme ui calcule (U0, ..., Un) est de taille > n-c (Kolmogrov)

3°) Application

  1. crypto
  2. simulation numerique
  3. generation d'arbre
  4. jeux

4°) Methode historique : générateur à congruence linéaire

on choisit 3 nombre {a, c, m}
on initialise avec X0 < m
on calcule X(n+1) = (a*Xn+c)%m
remarque: a ≠ 0, a ≠ 1, m est une puissance de 2 -> plus rapide, périodique(au plus m)
theoreme: la période est exactement m si
  • c et m sont premier entre eux
  • (a-1) est un multiple de tout les facteur premier de m
  • (a-1) n'est pas divisible par 4
  • ou bien m est divisible par 4


pour obtenir un bon générateur, il faut une période élever, et passer des tests statistiques

problème: si m est une puissance de 2 alors
les bits de poids faible sont moins aléatoire que les bits de poids fort
remarque: on ne peu pas prendre m = 2 pour générer des bits (période 1 ou 2)

5°) générateur à rétro-action

permet de générer des bits (Bn)

Bn = B(n-3) ^ B(n-31)
B0...B31 sont initialisé avec une seed
! il ne faut pas initialisé à {0}*
theoreme: la période est maximal si on par de B != {0}*
b = ((x >> 2) ^ (x >> 30))&1
x = (x << 1) | b;
remarque: les générateurs congruentiel et à rétroaction ne sont pas sur (ne pas utilisé en crypto)

6°) autres générateurs

glibc: random -> on génaire des entier de 32 bits

xn = x(n-3) ^ x(n-31)
le nombre généré est x >> 1
x0...x30 sont généré à partir d'une seed

mersen twister (plus utilisé) :

x(n+624) =
x(n+397) ^ x >> 1 si x(n+1) == 0
x(n+397) ^ x >> 1 ^ 0x99083b0df sinon

le nombre générer par Xn est (MT19937) :

y = xn >> 11
y = (y<<7) & 0x9d2c5680
y = (y<<15) & 0xefc60000