Générateur pseudo-aléatoire

Un article de Wikipédia, l'encyclopédie libre.

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[modifier | modifier le code]

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[modifier | modifier le code]