Générateur pseudo-aléatoire

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

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

   
  
    
      
        
          |
        
        P
        r
        [
        f
        (
        
          U
          
            n
          
        
        )
        =
        1
        ]
        −
        P
        r
        [
        f
        (
        G
        (
        
          U
          
            ℓ
          
        
        )
        )
        =
        1
        ]
        
          |
        
        ≤
        ϵ
      
    
    {\displaystyle |Pr[f(U_{n})=1]-Pr[f(G(U_{\ell }))=1]|\leq \epsilon }

Avec U k {\displaystyle U_{k}} la distribution uniforme sur les chaînes binaires de longueur k {\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 A {\displaystyle {\mathcal {A}}} .

Notes et références

  • (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).
  • icône décorative Portail de l'informatique théorique