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
une classe de fonctions.
Une application
avec
-trompe la classe
si pour tout
:
Avec
la distribution uniforme sur les chaînes binaires de longueur
et
une fonction de
, généralement décroissante.
On peut par exemple choisir P ou L pour la classe
.
Notes et références