talk/xplprngyestheorieko.tex

   1 \begin{block}{}
   2 \begin{minipage}{0.19\textwidth}
   3   \includegraphics[width=3.5cm]{../images/Gi.pdf}
   4 \end{minipage}
   5 \begin{minipage}{0.8\textwidth}
   6 \begin{itemize}
   7 \item Seules 16 vérifient les hypothèses du théorème précédent.
   8 \item $b$: nombre d'itérations suffisant pour une déviation p.r. la distribution uniforme inf. à  $10^{-4}$ (temps de mélange).
   9
  10 \begin{center}
  11   \begin{tiny}
  12     \begin{tabular}{|c|c|c|}
  13       \hline
  14       {Nom}& {Définition}&{$b$} \\
  15       \hline
  16       $\mathcal{F}_1$ & 14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 1, 0  & 206\\
  17       \hline
  18       $\vdots$ & $\vdots$ & $\vdots$ \\
  19       \hline
  20       $\mathcal{F}_9$ &14, 15, 12, 13, 10, 11, 9, 8, 7, 6, 5, 4, 3, 2, 0, 1
  21       & 42 \\
  22       \hline
  23       $\vdots$ & $\vdots$ & $\vdots$ \\
  24       \hline
  25       $\mathcal{F}_{16}$ &14, 15, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
  26       & 206 \\
  27       \hline
  28     \end{tabular}
  29   \end{tiny}
  30 \end{center}
  31 \item Succès de tous les PRNGs issus de ces fonctions
  32 aux tests  du \emph{National Institute of Standards and Technology} (NIST).
  33 \end{itemize}
  34 \end{minipage}
  35 \end{block}
  36 \begin{itemize}
  37 \item Erreur de raisonnement:
  38 \begin{itemize}
  39 \item Générateur prouvé chaotique seulement pour $b=1$.
  40 \item Pas compatible avec la pratique: $b \geq 42$ nécessaire
  41   pour suivre une loi uniforme (à $10^{-4}$ près).
  42 \item $\leadsto$ Étendre la théorie.
  43 \end{itemize}
  44 \end{itemize}