Générateur pseudo-aléatoire

terme

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éfinitionModifier

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érencesModifier