Générateur pseudo-aléatoire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 à ce 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]