title: Générateur pseudo-aléatoire
text: # Générateur pseudo-aléatoire
  
  En informatique théorique, un générateur pseudo-aléatoire (pour une classe de tests statistiques) est une procédure déterministique qui, donnée une chaîne aléatoire, en renvoie une plus longue de manière qu'aucun test de la classe correspondante puisse distinguer la chaîne retournée d'une chaîne aléatoire.
  
  ## Définition
  
  Soit ${\mathcal {A}}=\{A:\{0,1\}^{n}\to \{0,1\}\}$ une classe de fonctions. Une application $G:\{0,1\}^{\ell }\to \{0,1\}^{n}$ avec $\ell \leq n$ $\epsilon$-trompe la classe ${\mathcal {A}}$ si pour tout $f\in {\mathcal {A}}$:
  
  Avec $U_{k}$ la distribution uniforme sur les chaînes binaires de longueur $k$ et $\epsilon$ une fonction de $\ell$, généralement décroissante. On peut par exemple choisir P ou L pour la classe ${\mathcal {A}}$.
  
  