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 \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:

   |Pr[f(U_n)=1] - Pr[f(G(U_{\ell})) = 1]| \leq \epsilon

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.

Références[modifier | modifier le code]