Générateur pseudo-aléatoire

Soit ${\displaystyle {\mathcal {A}}=\{A:\{0,1\}^{n}\to \{0,1\}\}}$ une classe de fonctions. Une application ${\displaystyle G:\{0,1\}^{\ell }\to \{0,1\}^{n}}$ avec ${\displaystyle \ell \leq n}$ ${\displaystyle \epsilon }$-trompe la classe ${\displaystyle {\mathcal {A}}}$ si pour tout ${\displaystyle f\in {\mathcal {A}}}$:

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

Avec ${\displaystyle U_{k}}$ la distribution uniforme sur les chaînes binaires de longueur ${\displaystyle k}$ et ${\displaystyle \epsilon }$ une fonction de ${\displaystyle \ell }$, généralement décroissante.
On peut par exemple choisir P ou L pour la classe ${\displaystyle {\mathcal {A}}}$.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Pseudorandom generator » (voir la liste des auteurs).

• Portail de l'informatique théorique