talk/prnggeneralise.tex

   1 \begin{block}{}
   2  \begin{algorithm}[H]
   3 \KwIn{une fonction $f$, un nombre d'itérations $b$,
   4 une configuration initiale $x^0$ (${\mathsf{N}}$ bits)}
   5 \KwOut{une configuration $x$ (${\mathsf{N}}$ bits)}
   6 $x\leftarrow x^0$\;
   7 $k\leftarrow b $\;
   8 \For{$i=1,\dots,k$}
   9 {
  10 $s\leftarrow{\textit{Set}(\textit{Random}(2^{\mathsf{N}}))}$\;
  11 $x\leftarrow{F_{f_g}(x,s)}$\;
  12 }
  13 return $x$\;
  14 \end{algorithm}
  15 \end{block}
  16
  17 \begin{theorem}[Uniformité de la sortie ds le cas généralisé]
  18   Soit $f: \Bool^{{\mathsf{N}}} \rightarrow \Bool^{{\mathsf{N}}}$ et
  19   $\check{M}$ sa matrice d'adjacence.
  20   Si $\textsc{gig}(f)$ est fortement connexe, alors
  21   la sortie du PRNG suit une loi qui
  22   tend vers la distribution uniforme si
  23   et ssi  $\dfrac{1}{2^{\mathsf{N}}} \check{M}
  24 $ est une matrice doublement stochastique.
  25 \end{theorem}
  26