talk/prnggeneralise.tex

   1 \begin{block}{}
   2  \begin{algorithm}[H]
   3 \ldots\For{$i=1,\dots,k$}
   4 {
   5 $s\leftarrow{\textit{Set}(\textit{Random}(2^{\mathsf{N}}))}$\;
   6 $x\leftarrow{F_{f_g}(x,s)}$\;
   7 }\ldots
   8 \end{algorithm}
   9 \end{block}
  10
  11 \begin{theorem}[Uniformité de la sortie ds le cas généralisé]
  12   % Soit $f: \Bool^{{\mathsf{N}}} \rightarrow \Bool^{{\mathsf{N}}}$ et
  13   % $\check{M}$ sa matrice d'adjacence.
  14   Si $\textsc{gig}(f)$ est fortement connexe, alors
  15   la sortie du PRNG suit une loi qui
  16   tend vers la distribution uniforme
  17   ssi  $\dfrac{1}{2^{\mathsf{N}}} \check{M}
  18 $ est une matrice doublement stochastique.
  19 \end{theorem}
  20
  21 \begin{block}{Nombre moyen d'appels à un générateur binaire par bit généré}
  22 \begin{itemize}
  23 \item Unaires:$\nearrow$
  24 \item Généralisées: $\searrow$
  25 \end{itemize}
  26
  27
  28
  29
  30 \end{block}