la veille

[hdrcouchot.git] / 14Secrypt.tex

On  a vu  dans  le chapitre précédent  que  pour avoir
un  générateur à  sortie
uniforme, il est nécessaire que  la matrice d'adjacence du graphe d'itération du
système  soit doublement stochastique.   Nous présentons  dans cette  partie
des méthodes effectives permettant de générer de telles matrices.
La première est basée sur la programmation logique par contraintes
(Section~\ref{sec:plc}).
Cependant celle-ci souffre de ne pas passer à l'échelle et ne fournit pas 
une solution en un temps raisonnable dès que la fonction à engendrer 
porte sur un grand nombre de bits.
Une approche plus pragmatique consiste  à supprimer un cycle hamiltonien dans le
graphe d'itérations $\textsc{giu}(\neg)$ (section~\ref{sec:hamiltonian}). 
Pour obtenir plus rapidement une distribution uniforme, l'idéal serait
de supprimer un cycle hamiltonien qui nierait autant de fois chaque bit. 
Cette forme de cycle est dite équilibré. La section~\ref{sub:gray} établit le
lien avec les codes de Gray équilibrés, étudiés dans la littérature. 
La section suivante présente une démarche de génération automatique de code de Gray équilibré (section~\ref{sec:induction}).
La vitesse avec laquelle l'algorithme de PRNG converge en interne vers 
une distribution uniforme est étudiée théoriquement et pratiquement à la 
section~\ref{sec:mixing}.
L'extension du travail aux itérations généralisées est présentée à la 
section~\ref{sec:prng:gray:general}.
Finalement, des instances de PRNGs engendrés selon les méthodes détaillées dans 
ce chapitre sont présentées en section~\ref{sec:prng;gray:tests}.
Les sections~\ref{sec:plc}  à~\ref{sub:gray} ont été publiées 
à~\cite{chgw+14:oip}.
La section~\ref{sec:mixing} est publiée dans~\cite{ccgh16}.


% This aim of this section is to show 
% that finding DSSC matrices from a hypercube
% is a typical finite domain satisfaction 
% problem, classically denoted as 
% Constraint Logic Programming on Finite Domains (CLPFD). 
% This part is addressed in the first section. Next, we analyse the first
% results to provide a generation of DSSC matrices with small mixing times. 

\section{Programmation logique par contraintes sur des domaines finis}\label{sec:plc}
Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments. 
Pour éviter d'avoir à gérer des fractions, on peut considérer que 
les matrices (d'incidence) à générer ont des lignes et des colonnes dont les 
sommes valent ${\mathsf{N}}$ à chaque fois.  
On cherche ainsi toutes les matrices $M$ de taille  $2^{\mathsf{N}}\times 2^{\mathsf{N}}$ telles que 
  
\begin{enumerate}
\item $M_{ij}$ vaut 0 si $j$ n'est pas un voisin de $i$, \textit{i.e.},
  il n'y a pas d'arc de $i$ à $j$ dans le graphe $\textsc{giu}(f)$;

\item $0 \le M_{ii} \le {\mathsf{N}}$: le nombre de boucles autour de chaque 
configuration $i$ est inférieur à ${\mathsf{N}}$;

\item pour $j \neq i$,  $0 \le M_{ij} \le 1$: on construit l'arc de $i$ à $j$ 
si et seulement si $M_{ij}$ vaut 1 (et 0 sinon);
\item pour chaque indice de ligne  $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$: 
la matrice est stochastique à droite; 
\item pour chaque indice de colonne $j$, 
  $1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$: 
  la matrice est stochastique à gauche;
\item Tous les éléments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positifs, \textit{i.e.}, le graphe $\textsc{giu}(f)$ est fortement connexe;
\end{enumerate}
Ce problème s'exprime sur des domaines finis entiers avec des opérateurs  
arithmétiques simples (sommes et produits). Il pourrait théoriquement être 
traité par des démarches de programmation logique par contrainte
sur des domaines finis (comme en PROLOG).
L'algorithme donné en Figure~\ref{fig:prolog}
est en effet le c{\oe}ur du programme PROLOG 
qui pourrait être utilisé pour instancier toutes les solutions,
ici pour  $\mathsf{N} = 2$. Dans ce code, 
\verb+mmult(+$X,Y,R$\verb+)+ et 
\verb+summ(+$X,Y,R$\verb+)+ 
valent True si et seulement si $R$ 
est le produit matriciel  (ou la somme matricielle) 
entre  $X$ et $Y$ respectivement. 
Il n'est pas difficile d'adapter ce code à n'importe quelle valeur 
entière naturelle  $\mathsf{N}$.  

\begin{figure}[ht]
\begin{scriptsize}
\lstset{language=prolog}
\begin{lstlisting}
bistoc(X):-
  M=[[M0_0, M0_1, 0, M0_3], [M1_0, M1_1, 0, M1_3], 
     [M2_0, 0, M2_2, M2_3], [0, M3_1, M3_2, M3_3]],
  [M0_0, M1_1, M2_2, M3_3] ins 0..2,
  [M0_1, M0_3, M1_0, M1_3, M2_0, M2_3, M3_1, M3_2] 
     ins 0..1,
  M0_0+ M0_1+ M0_2 #=2, M1_0+ M1_1+ M1_3 #=2,
  M2_0+ M2_2+ M2_3 #=2, M3_1+ M3_2+ M3_3 #=2,
  M0_0+ M1_0+ M2_0 #=2, M0_1+ M1_1+ M3_1 #=2, 
  M0_2+ M2_2+ M3_2 #=2, M1_3+ M2_3+ M3_3 #=2,
  mmult(M,M,M2),
  mmult(M,M2,M3),
  mmult(M,M3,M4),
  summ(M,M2,S2),
  summ(S2,M3,S3),
  summ(S3,M4,S4),
  allpositive(S4).
\end{lstlisting}
\end{scriptsize}
\caption{Code PROLOG permettant de trouver toutes les matrices DSSC pour $n=2$}\label{fig:prolog}
\end{figure}

Enfin, on définit la relation $\mathcal{R}$, qui est établie pour les deux 
fonctions  $f$ et $g$ si leurs graphes 
respectifs  $\textsc{giu}(f)$ et $\textsc{giu}(g)$ 
sont isomorphes.
C'est évidemment une relation d'équivalence.



%\subsection{Analyse de l'approche}\label{sub:prng:ana}
Exécutée sur un ordinateur personnel, PROLOG trouve 
en moins d'une seconde les
49 solutions pour  $n=2$, 
dont 2 seulement ne sont pas équivalentes, 
en moins d'une minute les 27642 solutions dont seulement 111 ne 
sont pas équivalentes pour $n=3$.
Cependant, l'approche ne permet pas d'engendrer toutes les solutions 
pour $n=4$.
Cette approche, basée sur une démarche de type \emph{générer, tester} ne peut 
pas être retenue pour $n$ de grande taille, même 
en s'appuyant sur l'efficience de l'algorithme de backtrack natif de PROLOG.

Cependant, pour des petites valeurs de $n$, nous avons 
comparé les fonctions non équivalentes selon leur proportion
à engendrer des temps de mélange petits (cf. équation~(\ref{eq:mt:ex})).




\begin{xpl}\label{xpl:mixing:3}
Le tableau~\ref{table:mixing:3} fournit les 5 fonctions booléennes 
qui ont les temps de mélange les plus petits pour $\varepsilon=10^{-5}$. 
\begin{table}[ht]
\begin{small}
$$
\begin{array}{|l|l|l|}
\hline
\textrm{Name} & \textrm{Image} & \textrm{MT}\\
\hline
f^a &  (x_2 \oplus x_3, x_1 \oplus \overline{x_3},\overline{x_3})  &  16   \\
\hline
f^*  &  (x_2 \oplus x_3, \overline{x_1}.\overline{x_3} + x_1\overline{x_2},
\overline{x_1}.\overline{x_3} + x_1x_2)  &  17   \\
\hline
f^b  &  (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}.\overline{x_3}, &  \\
& \qquad \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2)  &  26   \\
\hline
f^c  &  (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}.\overline{x_3}, & \\
& \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2)  &  29   \\
\hline
f^d  &  (x_1\oplus x_2,x_3(\overline{x_1}+\overline{x_2}),\overline{x_3})  &  30   \\
\hline
% [3, 4, 7, 0, 1, 6, 5, 2], #16
% [3, 4, 7, 0, 2, 6, 5, 1], #17
% [3, 6, 7, 5, 2, 0, 1, 4], #26 
% [3, 4, 7, 5, 2, 6, 1, 0], #29
% [3, 2, 5, 6, 7, 0, 1, 4]] #30
\end{array}
$$
\end{small}
\caption{Les 5 fonctions booléennes $n=3$ aux temps de mélange les plus faibles.}\label{table:mixing:3}
\end{table}
\end{xpl}

Une analyse syntaxique de ces fonctions ne permet pas, a priori, 
de déduire des règles permettant de construire de nouvelles
fonctions dont le temps de mélange serait faible.
Cependant, le graphe $\textsc{giu}(f^*)$ 
(donné à la Figure~\ref{fig:iteration:f*})
est le $3$-cube dans lequel le cycle 
$000,100,101,001,011,111,110,010,000$ 
a été enlevé. Dans cette figure, le  graphe $\textsc{giu}(f)$ est
en continu tandis que le cycle est en pointillés.
Ce cycle qui visite chaque n{\oe}ud exactement une fois est un  
\emph{cycle hamiltonien}.
La matrice de Markov correspondante est donnée à 
la figure~\ref{fig:markov:f*}.
On s'intéresse  par la suite à la génération de ce genre de cycles.





\begin{figure}[ht]
  \begin{center}
    \subfigure[Graphe $\textsc{giu}(f^*)$.
    \label{fig:iteration:f*}]{
      \begin{minipage}{0.55\linewidth}
        \centering
        \includegraphics[width=\columnwidth]{images/iter_f0d}%
      \end{minipage}
    }%
    \subfigure[Matrice de Markov associée à $\textsc{giu}(f^*)$
    \label{fig:markov:f*}]{%
      \begin{minipage}{0.35\linewidth}
        \begin{scriptsize}
          \begin{center}

\[
M=\dfrac{1}{3} \left(
\begin{array}{llllllll}
1&1&1&0&0&0&0&0 \\
1&1&0&0&0&1&0&0 \\
0&0&1&1&0&0&1&0 \\
0&1&1&1&0&0&0&0 \\
1&0&0&0&1&0&1&0 \\
0&0&0&0&1&1&0&1 \\
0&0&0&0&1&0&1&1 \\
0&0&0&1&0&1&0&1 
\end{array}
\right)
\]



            % $ \dfrac{1}{4} \left(
            %   \begin{array}{cccccccc}
            %     1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
              
            %     1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
              
            %     0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
              
            %     1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
              
            %     1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
              
            %     0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
              
            %     0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
              
            %     0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
              
            %   \end{array}            \right) $



          \end{center}
        \end{scriptsize}
      \end{minipage}
    }%
    \caption{Représentations de $f^*(x_1,x_2,x_3)=
      (x_2 \oplus x_3, \overline{x_1}.\overline{x_3} + x_1\overline{x_2},
      \overline{x_1}.\overline{x_3} + x_1x_2)$.}\label{fig1}
  \end{center}
\end{figure}




% section{Graphes 
%   $\textsc{giu}(f)$ 
%   $\textsc{gig}(f)$ 
%   fortement connexes et doublement stochastiques}\label{sec:gen:dblstc}
% %
%Secrypt 14




\section{Suppression des cycles hamiltoniens}
\label{sec:hamiltonian}

Dans un premier temps, nous montrons %en section~\ref{sub:removing:theory} 
que la
suppression  d'un  cycle  hamiltonien   produit  bien  des  matrices  doublement
stochastiques.   Nous  établissons  ensuite  le  lien avec  les  codes  de  Gray
équilibrés.

%\subsubsection{Aspects théoriques}
%\label{sub:removing:theory}

Nous donnons  deux résultats complémentaires, reliant la  suppression d'un cycle
hamiltonien  du $n$-cube,  les matrices  doublement stochastiques  et  la forte
connexité du graphe d'itérations.

\begin{theorem}\label{th:supprCH}
  La suppression d'un cycle hamiltonien dans une matrice de Markov $M$, issue du
  $n$-cube, produit une matrice doublement stochastique.
\end{theorem}
\begin{proof}

Un cycle hamiltonien passe par chaque n{\oe}ud une et une seule fois.
Pour chaque n{\oe}ud $v$ dans le $n$-cube $C_1$,
une arête entrante $(o,v)$ et une arête sortante $(v,e)$ 
sont ainsi enlevées.
Considérons un autre  $n$-cube $C_2$ auquel on ajoute les arêtes 
pour le rendre complet. La matrice de Markov $M$ correspondante est
remplie de $\frac{1}{2^n}$ et est doublement stochastique.
Comme on enlève exactement une arête sortante $(v,e)$ 
à chaque n{\oe}ud $v$ dans $C_1$, on enlève ainsi dans 
$C_2$ les $2^{n-1}$ arêtes issues de $v$ et 
relatives aux parties de $\{1,\ldots,n\}$ qui
contiennent $e$. Cela revient à annuler 
dans la matrice $M$ les $2^{n-1}$ coefficients correspondants et ajouter 
$1/2$ à l'élément $M_{vv}$.
La matrice $M$ reste stochastique.
On effectue un raisonnement similaire pour les arêtes entrantes:
comme on enlève exactement une arête entrante $(o,v)$ pour chaque 
n{\oe}ud $v$ dans $C_1$, dans $C_2$, ce sont exactement 
$2^{n-1}$ arêtes menant à $v$ qui sont enlevées. 
Dans $M$ les $2^{n-1}$ coefficients correspondants sont mis à 0 et 
$M_{vv}$ vaut alors $\frac{2^{n-1} +1}{2}$.
$M$ est donc doublement stochastique.
\end{proof}



\begin{theorem}\label{th:grapheFC}
  Le  graphe d'itérations  issu du  $n$-cube,  auquel un  cycle hamiltonien  est
  enlevé, est fortement connexe.
\end{theorem}


\begin{proof}
On considère les deux $n$-cubes $C_1$ et $C_2$ définis 
dans la preuve du théorème~\ref{th:supprCH}.
Dans $C_1$ on considère le cycle inverse $r$ du cycle
hamiltonien $c$.
Aucun arc n'appartient à la fois  à $r$ et à $c$: 
en effet, sinon $c$ contiendrait un n{\oe}ud deux fois.
Ainsi aucune arête de $r$ n'est enlevée dans $C_1$.
Le cycle $r$ est évidemment un cycle hamiltonien et contient tous les n{\oe}uds.
Tous les n{\oe}uds de $C_1$ dans lesquels $c$ a été enlevé sont accessibles 
depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsc{giu}$ qui
étend le précédent graphe est ainsi fortement connexe. 

\end{proof}



%Les preuves, relativement directes, sont  laissées en exercices au lecteur.  
Générer un  cycle hamiltonien dans le
$n$-cube revient à  trouver un  \emph{code de  Gray  cyclique}.  On
rappelle qu'un code de  Gray est une  séquence de mots binaires  de taille
fixe ($\mathsf{N}$),  dont les éléments successifs ne  différent que par un  seul bit. Un
code  de  Gray est  \emph{cyclique}  si  le premier  élément  et  le dernier  ne
différent que par un seul bit.

\section{Lien avec les codes de Gray cycliques (totalement) équilibrés}
\label{sub:gray}

Un minorant du  nombre de codes  de Gray  ($\left(\frac{n*\log2}{e \log
    \log   n}\times(1  -  o(1))\right)^{2^n}$),   donnée  dans~\cite{Feder2009NTB},
indique  une explosion combinatoire  pour notre  recherche.  Afin  de contourner
cette  difficulté,  nous  nous   restreignons  aux  codes  induisant  un  graphe
d'itérations $\textsc{giu}(f)$  \emph{uniforme}.  Cette uniformité se  traduit par des
nombres d'arcs  équilibrés entre les  \emph{dimensions} du graphe,  la dimension
$i$  correspondant aux  seules variations  du  bit $i$  (parmi les  $n$ bits  au
total).   Cette  approche  revient  à  chercher  des  codes  de  Gray  cycliques
\emph{équilibrés}.

On formalise un code de Gray équilibré comme suit.
Soit $L = w_1,  w_2, \dots, w_{2^n}$ la séquence d'un code  de Gray cyclique à
$n$ bits.  Soit $S = s_1,  s_2, \dots, s_{2^n}$ la séquence des transitions où
$s_i$, $1  \le i \le 2^n$  est l'indice du seul  bit qui varie  entre les mots
$w_i$ et  $w_{i+1}$. Enfin, soit  $\textit{TC}_n : \{1,\dots,  n\} \rightarrow
\{0, \ldots, 2^n\}$  la fonction qui au paramètre  $i$ associe le \emph{nombre
  de transitions} présentes dans la séquence $L$ pour le bit $i$, c'est-à-dire
le nombre d'occurrences de $i$ dans $S$.
  
Le      code       $L$      est      \textbf{équilibré}       si      $\forall
i,j\in\{1,...,n\},~|\textit{TC}_n(i)  -  \textit{TC}_n(j)|  \le  2$.   Il  est
\textbf{totalement             équilibré}             si             $\forall
i\in\{1,...,n\},~\textit{TC}_n(i)=\frac{2^n}{n}$.


On peut  donc déjà déduire  qu'il ne peut  exister des codes de  Gray totalement
équilibrés que  pour les  systèmes ayant un  nombre d'éléments $n=2^k,  k>0$. De
plus,  comme  dans tout  code  de  Gray  cyclique, $\textit{TC}_n(i)$  est  pair
$\forall  i\in\{1,...,n\}$,  alors  les  systèmes  ayant  un  nombre  d'éléments
différent  de $2^k$,  ne peuvent  avoir  que des  codes de  Gray équilibrés  avec
$\textit{TC}_n(i)=\lfloor\frac{2^n}{n}\rfloor$                                 ou
$\textit{TC}_n(i)=\lceil\frac{2^n}{n}\rceil,    \forall    i\in\{1,...,n\}$   et
vérifiant $\sum_{i=1}^n\textit{TC}_n(i) = 2^n$.

\begin{xpl}
  Soit  $L^*=000,100,101,001,011,111,110,010$ le code  de Gray  correspondant au
  cycle hamiltonien enlevé de $f^*$.  Sa séquence des transitions est \linebreak
  $S=3,1,3,2,3,1,3,2$  et  les nombres  de  transitions sont  $\textit{TC}_3(1)=
  \textit{TC}_3(2)=2$ et $\textit{TC}_3(3)=4$. Un tel code est équilibré.

  Si l'on  considère maintenant $L^4=$ 0000,  0010, 0110, 1110, 1111,  0111, 0011,
  0001,  0101, 0100,  1100, 1101,  1001,  1011, 1010,  1000,  un  code de  Gray
  cyclique. En construisant la séquence $S=$ 2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4, 
  on constate que  $\forall
  i\in\{1,..,4\},~\textit{TC}_4(i)=4$ et donc que 
  ce code est totalement équilibré.
\end{xpl}

\section{Génération de codes de Gray équilibrés par induction}
\label{sec:induction}

De nombreuses approches ont été développées pour résoudre le problème de construire
un code de Gray dans un $\mathsf{N}$-cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04}, 
selon les propriétés que doit vérifier ce code.

Dans les travaux~\cite{Robinson:1981:CS}, les auteurs 
proposent une approche inductive de construction de code de Gray équilibrés 
(on passe du $\mathsf{N}-2$ à $\mathsf{N}$)
pour peu que l'utilisateur fournisse une sous-séquence possédant certaines 
propriétés à chaque pas inductif.
Ce travail a été renforcé dans ~\cite{DBLP:journals/combinatorics/BhatS96}
où les auteurs donnent une manière explicite de construire une telle sous-séquence.
Enfin, les auteurs de~\cite{ZanSup04} présentent une extension de l'algorithme de
\emph{Robinson-Cohn}. La présentation rigoureuse de cette extension leur permet 
principalement de prouver que si $\mathsf{N}$ est une puissance de 2, 
le code de Gray équilibré engendré par l'extension est toujours totalement équilibré et 
que $S_{\mathsf{N}}$ est la séquence de transition d'un code de Gray de $\mathsf{N}$ bits 
si  $S_{\mathsf{N}-2}$ l'est aussi. 
Cependant les auteurs ne prouvent pas que leur approche fournit systématiquement  
un code de Gray (totalement) équilibré. 
Cette section montre que ceci est vrai en rappelant tout d'abord
l'extension de l'algorithme de \emph{Robinson-Cohn} pour un 
code de Gray avec $\mathsf{N}-2$ bits
défini à partir de la séquence $S_{\mathsf{N}-2}$.

\begin{enumerate}
\item \label{item:nondet}Soit $l$ un entier positif pair. Trouver des sous-séquences 
$u_1, u_2, \dots , u_{l-2}, v$ (possiblement vides) de $S_{\mathsf{N}-2}$ 
telles que $S_{\mathsf{N}-2}$ est la concaténation de  
$$
s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, \dots , s_{i_l-1}, u_{l-2}, s_{i_l}, v
$$
où $i_1 = 1$, $i_2 = 2$, et $u_0 = \emptyset$ (la séquence vide).
\item\label{item:u'} Remplacer dans $S_{\mathsf{N}-2}$ les séquences $u_0, u_1, u_2, \ldots, u_{l-2}$ 
  par 
  $\mathsf{N} - 1,  u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$
  respectivement, où $u'(u,x,y)$ est la séquence $u,x,u^R,y,u$ telle que 
  $u^R$ est $u$, mais dans l'ordre inverse. La séquence obtenue est ensuite notée $U$.
\item\label{item:VW} Construire les séquences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$. Soit  alors $W'$ définie comme étant égale à $W$ sauf pour les 
deux premiers éléments qui ont été intervertis.
\item La séquence de transition  $S_{\mathsf{N}}$ est la concaténation $U^R, V, W'$.
\end{enumerate} 

L'étape~(\ref{item:nondet}) n'est pas constructive: il n'est pas précisé
comment sélectionner des sous-séquences qui assurent que le code obtenu est équilibré.
Le théorème suivant montre que c'est possible et sa preuve,
donnée en annexe~\ref{anx:generateur}, explique comment le faire. 

\begin{restatable}[Existence d'un code de Gray équilibré]{theorem}{theograyequilibre}
\label{prop:balanced}
Soit $\mathsf{N}$ dans $\Nats^*$, et $a_{\mathsf{N}}$ défini par 
$a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$. 
Il existe une séquence $l$ dans l'étape~(\ref{item:nondet}) de l'extension
de l'algorithme de \emph{Robinson-Cohn}  telle que 
les nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$ 
valent tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$ 
pour chaque  $i$, $1 \le i \le \mathsf{N}$.
\end{restatable}

Ces fonctions étant générées, on s'intéresse à étudier à quelle vitesse 
un générateur les embarquant converge vers la distribution uniforme.
C'est l'objectif de la section suivante. 

\section{Quantifier l'écart par rapport à la distribution uniforme}\label{sec:mixing} 
On considère ici une fonction construite comme à la section précédente.
On s'intéresse ici à étudier de manière théorique les 
itérations définies à l'équation~(\ref{eq:asyn}) pour une 
stratégie donnée.
Tout d'abord, celles-ci peuvent être interprétées comme une marche le long d'un 
graphe d'itérations $\textsc{giu}(f)$ tel que le choix de tel ou tel arc est donné par la 
stratégie.
On remarque que ce graphe d'itérations est toujours un sous graphe 
du   ${\mathsf{N}}$-cube augmenté des 
boucles sur chaque sommet, \textit{i.e.}, les arcs
$(v,v)$ pour chaque $v \in \Bool^{\mathsf{N}}$. 
Ainsi, le travail ci-dessous répond à la question de 
définir la longueur du chemin minimum dans ce graphe pour 
obtenir une distribution uniforme.
Ceci se base sur la théorie des chaînes de Markov.
Pour une référence 
générale à ce sujet on pourra se référer 
au livre~\cite{LevinPeresWilmer2006},
particulièrement au chapitre sur les temps d'arrêt.






\begin{xpl}
On considère par exemple le graphe $\textsc{giu}(f)$ donné à la 
\textsc{Figure~\ref{fig:iteration:f*}.} et la fonction de 
probabilités $p$ définie sur l'ensemble des arcs comme suit:
$$
p(e) \left\{
\begin{array}{ll}
= \frac{1}{2} + \frac{1}{6} \textrm{ si $e=(v,v)$ avec $v \in \Bool^3$,}\\
= \frac{1}{6} \textrm{ sinon.}
\end{array}
\right.  
$$
La matrice $P$ de la chaîne de Markov associée à  $f^*$ 
est  
\[
P=\dfrac{1}{6} \left(
\begin{array}{llllllll}
4&1&1&0&0&0&0&0 \\
1&4&0&0&0&1&0&0 \\
0&0&4&1&0&0&1&0 \\
0&1&1&4&0&0&0&0 \\
1&0&0&0&4&0&1&0 \\
0&0&0&0&1&4&0&1 \\
0&0&0&0&1&0&4&1 \\
0&0&0&1&0&1&0&4 
\end{array}
\right)
\]
\end{xpl}

On remarque que dans cette marche on reste sur place avec une probabilité égale 
à $\frac{1}{2}+\frac{1}{2\mathsf{N}}$ et l'on passe d'un sommet à son voisin
lorsque c'est possible avec une probabilité $\frac{1}{2\mathsf{N}}$.
Les probabilités usuelles que l'on appliquerait aux transitions de 
l'algorithme~\ref{CI Algorithm} seraient quant à elles uniformément égales 
à $\frac{1}{\mathsf{N}}$.
Cette manière paresseuse d'itérer (puisqu'on reste plus souvent sur place) n'est donc pas équivalente à celle issue de l'algorithme. 

Cependant, l'étude théorique de référence~\cite{LevinPeresWilmer2006}
considère cette marche comme cadre. S'inspirant de 
celle-ci, le travail suivant se replace donc dans ce cadre théorique.


Tout d'abord, soit $\pi$ et $\mu$ deux distributions sur 
$\Bool^{\mathsf{N}}$. 
La distance de \og totale variation\fg{} entre  $\pi$ et $\mu$ 
est notée  $\tv{\pi-\mu}$ et est définie par 
$$\tv{\pi-\mu}=\max_{A\subset \Bool^{\mathsf{N}}} |\pi(A)-\mu(A)|.$$ 
On sait que 
$$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$
De plus, si 
$\nu$ est une distribution sur $\Bool^{\mathsf{N}}$, on a 
$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}.$$

Soit $P$ une matrice d'une chaîne de Markov sur $\Bool^{\mathsf{N}}$. 
$P(X,\cdot)$ est la distribution induite par la  $X^{\textrm{ème}}$ colonne
de  $P$. 
Si la chaîne de  Markov induite par 
$P$ a une  distribution stationnaire $\pi$, on définit alors 
$$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}$$

et

$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
 
Intuitivement, $t_{\rm mix}(\varepsilon)$ est le nombre d'itérations nécessaire 
pour être proche de la distribution stationnaire à $\varepsilon$ près, 
peu importe la configuration de départ. On a le théorème suivant démontré en annexe~\ref{anx:generateur}.


\begin{restatable}[Temps de mixage sans chemin hamiltonien]{theorem}{theotpsmix}
\label{theo:tmps:mix}
On considère un $\mathsf{N}$-cube dans lequel un chemin hamiltonien a été supprimé et la fonction de 
probabilités $p$ définie sur l'ensemble des arcs comme suit:
\[
p(e) \left\{
\begin{array}{ll}
= \frac{1}{2} + \frac{1}{2\mathsf{N}} \textrm{ si $e=(v,v)$ avec $v \in \Bool^{\mathsf{N}}$,}\\
= \frac{1}{2\mathsf{N}} \textrm{ sinon.}
\end{array}
\right.  
\]

La chaîne de Markov associée converge vers la distribution uniforme et 

\[
\forall \varepsilon >0,\, t_{\rm mix}(\varepsilon) \le 
x
\leq \lceil\log_2(\varepsilon^{-1})
(32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1)) 
\] 
\end{restatable}



Sans entrer dans les détails de la preuve, on remarque aussi
que le calcul  de ce majorant impose uniquement que 
pour chaque n{\oe}ud du $\mathsf{N}$-cube 
un arc entrant et un arc sortant sont supprimés.
Le fait qu'on enlève un cycle  hamiltonien et que ce dernier 
soit équilibré n'est pas pris en compte.
En intégrant cette contrainte, ce majorant  pourrait être réduit.

En effet, le temps de mixage est en $\Theta(N\ln N)$ lors d'une
marche aléatoire classique paresseuse dans le $\mathsf{N}$-cube.
On peut ainsi conjecturer que cet ordre de grandeur reste le même 
dans le contexte du $\mathsf{N}$-cube privé d'un chemin hamiltonien.

On peut évaluer ceci pratiquement: pour une fonction
$f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ et une graine initiale
$x^0$, le code donné à l'algorithme~\ref{algo:stop} retourne le 
nombre d'itérations suffisant tel que tous les éléments $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ sont équitables. Il permet de déduire une approximation de $E[\ts]$
en l'instanciant un grand nombre de fois: pour chaque nombre $\mathsf{N}$, 
$ 3 \le \mathsf{N} \le 16$, 10 fonctions ont été générées comme dans 
ce chapitre. Pour chacune d'elle, le calcul d'une approximation de $E[\ts]$
est exécuté 10000 fois avec une graine aléatoire. La Figure~\ref{fig:stopping:moy}
résume ces résultats. Dans celle-ci, un cercle  représente une approximation de 
$E[\ts]$ pour un  $\mathsf{N}$ donné tandis que la courbe est une représentation de 
la fonction $x \mapsto 2x\ln(2x+8)$. 
On  constate que l'approximation de $E[\ts]$ est largement inférieure 
au majorant quadratique donné au théorème~\ref{prop:stop} et que la conjecture 
donnée au paragraphe précédent est sensée.


\begin{algorithm}[ht]
%\begin{scriptsize}
\KwIn{a function $f$, an initial configuration $x^0$ ($\mathsf{N}$ bits)}
\KwOut{a number of iterations $\textit{nbit}$}

$\textit{nbit} \leftarrow 0$\;
$x\leftarrow x^0$\;
$\textit{fair}\leftarrow\emptyset$\;
\While{$\left\vert{\textit{fair}}\right\vert < \mathsf{N} $}
{
        $ s \leftarrow \textit{Random}(\mathsf{N})$ \;
        $\textit{image} \leftarrow f(x) $\;
        \If{$\textit{Random}(1) \neq 0$ and $x[s] \neq \textit{image}[s]$}{
            $\textit{fair} \leftarrow \textit{fair} \cup \{s\}$\;
            $x[s] \leftarrow \textit{image}[s]$\;
          }
        $\textit{nbit} \leftarrow \textit{nbit}+1$\;
}
\Return{$\textit{nbit}$}\;
%\end{scriptsize}
\caption{Pseudo-code pour évaluer le temps d'arrêt}
\label{algo:stop}
\end{algorithm}


\begin{figure}
\centering
\includegraphics[width=0.49\textwidth]{images/complexityET}
\caption{Interpolation du temps d'arrêt}\label{fig:stopping:moy}
\end{figure}




\section{Et les itérations généralisées?}\label{sec:prng:gray:general}
Le chapitre précédent a présenté un algorithme de 
PRNG construit à partir d'itérations unaires. 
On pourrait penser que cet algorithme est peu efficace puisqu'il 
dispose d'une fonction $f$ de $\Bool^n$ dans lui même mais il ne modifie à 
chaque itération qu'un seul élément de $[n]$.
On pourrait penser à un algorithme basé sur les itérations généralisées, 
c'est-à-dire qui modifierait une partie des éléments de $[n]$ à chaque 
itération.
C'est l'algorithme~\ref{CI Algorithm:prng:g} donné ci-après.

\begin{algorithm}[ht]
%\begin{scriptsize}
\KwIn{une fonction $f$, un nombre d'itérations $b$, 
une configuration initiale $x^0$ ($n$ bits)}
\KwOut{une configuration $x$ ($n$ bits)}
$x\leftarrow x^0$\;
$k\leftarrow b $\;
\For{$i=1,\dots,k$}
{
$s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$\;
$x\leftarrow{F_{f_g}(s,x)}$\;
}
return $x$\;
%\end{scriptsize}
\caption{PRNG basé sur les itérations généralisées.}
\label{CI Algorithm:prng:g}
\end{algorithm}

Par rapport à l'algorithme~\ref{CI Algorithm} seule 
la ligne $s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$ est différente.
Dans celle-ci la fonction  $\textit{Set}   :    \{1,\ldots,2^n\}   \rightarrow
\mathcal{P}(\{1,\ldots   n\})$   retourne  l'ensemble   dont   la   fonction
caractéristique  serait  représentée par  le  nombre  donné  en argument.
Par exemple, pour $n=3$, l'ensemble $\textit{Set}(6)$ vaudrait $\{3,2\}$.
On remarque aussi que l'argument de la fonction  $\textit{Random}$
passe de $n$ à $2^n$.

On a le théorème suivant qui étend le théorème~\ref{thm:prng:u} aux itérations
généralisées.

\begin{theorem}\label{thm:prng:g}
  Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{gig}(f)$ son 
  graphe des itérations généralisées, $\check{M}$ la matrice d'adjacence
  correspondante à ce graphe 
  et $M$ une matrice  $2^n\times 2^n$  
  définie par 
  $M = \dfrac{1}{2^n} \check{M}$.
  Si $\textsc{gig}(f)$ est fortement connexe, alors 
  la sortie du générateur de nombres pseudo-aléatoires détaillé par 
  l'algorithme~\ref{CI Algorithm:prng:g} suit une loi qui 
  tend vers la distribution uniforme si 
  et seulement si  $M$ est une matrice doublement stochastique.
\end{theorem}

La preuve de ce théorème est la même que celle du théorème~\ref{thm:prng:u}.
Elle n'est donc pas rappelée.

\begin{xpl}

  On reprend l'exemple donné à la section~\ref{sec:plc}.
  On considère le cycle hamiltonien défini par la séquence
  $000,100,101,001,011,111,110,010,000$. En supprimant celui-ci dans 
  le $3$-cube, cela engendre 
  la fonction $f^*$ définie par 
  $$f^*(x_1,x_2,x_3)=
  (x_2 \oplus x_3, \overline{x_1}.\overline{x_3} + x_1\overline{x_2},
\overline{x_1}.\overline{x_3} + x_1x_2).
$$ 

Le graphe  $\textsc{gig}(f^*)$  est représenté à la 
Figure~\ref{fig:iteration:f*}.
La matrice de Markov $M$ correspondante est donnée à 
la figure~\ref{fig:markov:f*}.

\begin{figure}[ht]
  \begin{center}
    \subfigure[Graphe $\textsc{gig}(f^*)$
    \label{fig:iteration:f*}]{
      \begin{minipage}{0.55\linewidth}
        \centering
        \includegraphics[width=\columnwidth]{images/iter_f}%
      \end{minipage}
    }%
    \subfigure[Matrice de Markov associée au $\textsc{gig}(f^*)$
    \label{fig:markov:f*}]{%
      \begin{minipage}{0.35\linewidth}
        \begin{scriptsize}
          \begin{center}
            $ \dfrac{1}{4} \left(
              \begin{array}{cccccccc}
                1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
              
                1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
              
                0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
              
                1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
              
                1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
              
                0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
              
                0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
              
                0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
              
              \end{array}            \right) $
          \end{center}
        \end{scriptsize}
      \end{minipage}
    }%
    \caption{Représentations de $f^*(x_1,x_2,x_3)=
      (x_2 \oplus x_3, \overline{x_1}.\overline{x_3} + x_1\overline{x_2},
      \overline{x_1}.\overline{x_3} + x_1x_2)$.}\label{fig1}
  \end{center}
\end{figure}
\end{xpl}



\begin{table}[ht]
  \begin{center}
    \begin{scriptsize}
      \begin{tabular}{|c|c|l|c|c|}
        \hline
        $n$ & fonction  & $f(x)$, $f(x)$ pour $x \in [0,1,2,\hdots,2^n-1]$                 & $b$ & $b'$ \\ 
        \hline
        4 & $f^{*4}$ & [13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]                          & \textbf{17}  & \textbf{38}   \\
        \hline
         \multirow{4}{0.5cm}{5}& $f^{*5}$  & [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1,        & \textbf{13}  & 48   \\
            &   & 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]     &     &      \\
        \cline{2-5}
         & $g^{*5}$  & [29, 22, 21, 30, 19, 27, 24, 28, 7, 20, 5, 4, 23, 26, 25,                                                                                        & 15  & \textbf{47}   \\
            &   & 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 1, 6, 11, 18, 0, 16
                                                                                           &     &      \\
        
        \hline
        \multirow{8}{0.5cm}{6}& $f^{*6}$  & 
     [55, 60, 45, 56, 58, 42, 61, 40, 53, 50, 52, 54, 59, 34, 33, & \multirow{4}{0.5cm}{\textbf{11}}& \multirow{4}{0.5cm}{55}\\
& & 49, 39, 62, 47, 46, 11, 43, 57, 8, 37, 6, 36, 4, 51, 38, 1, & & \\
& & 48, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, & & \\
& & 16, 24, 13, 12, 29, 44, 10, 14, 41, 0, 15, 2, 7, 5, 35, 3, 9, 32] & &\\    
        \cline{2-5}
&$g^{*6}$ &     [55, 60, 45, 44, 43, 62, 61, 48, 53, 50, 52, 36, 59, 51, 33, & \multirow{4}{0.5cm}{12}&  \multirow{4}{0.5cm}{\textbf{54}}\\
    & & 49, 15, 14, 47, 46, 35, 58, 57, 56, 7, 54, 39, 37, 3, 38, 1, & & \\
    & &  40, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22,  & & \\
    & &  16, 24, 13, 12, 29, 8, 10, 42, 41, 0, 5, 2, 4, 6, 11, 34, 9, 32] & & \\
 \hline
         \multirow{9}{0.5cm}{7}            &$f^{*7}$ & [111, 94, 93, 116, 122, 114, 125, 88, 115, 126, 85, 84, 123,     & \multirow{9}{0.5cm}{\textbf{10}}    & \multirow{9}{0.5cm}{\textbf{63}}     \\ 
                 & & 98, 81, 120, 109, 78, 105, 110, 99, 107, 104, 108, 101, 118,     &     &      \\ 
                 & & 117, 96, 103, 66, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24,     &     &      \\ 
                 & & 119, 22, 69, 20, 87, 18, 17, 112, 77, 76, 73, 12, 74, 106, 72,   &     &      \\ 
                 & & 8, 7, 102, 71, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59,     &     &      \\ 
                 & & 56, 48, 53, 38, 37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42,     &     &      \\ 
                 & & 46, 45, 41, 35, 34, 39, 52, 43, 50, 32, 36, 29, 28, 61, 92,     &     &      \\ 
                 & & 26, 90, 89, 25, 19, 30, 23, 4, 27, 2, 16, 80, 31, 10, 15, 14,     &     &      \\ 
                 & & 3, 11, 13, 9, 5, 70, 21, 68, 67, 6, 65, 1] & & \\
        \hline
         \multirow{20}{0.5cm}{8}   &        $f^{*8}$  &
[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180,& 
\multirow{20}{0.5cm}{9}& 
\multirow{20}{0.5cm}{71}\\ 
& & 227, 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168,& & \\ 
& & 229, 166, 165, 244, 163, 242, 241, 192, 215, 220, 205, 216,& & \\ 
& & 218, 222, 221, 208, 213, 210, 212, 214, 219, 211, 217, 209,& & \\ 
& & 239, 202, 207, 140, 139, 234, 193, 204, 135, 196, 199, 132,& & \\ 
& & 194, 130, 225, 200, 159, 62, 185, 252, 59, 250, 169, 56, 191,& & \\ 
& & 246, 245, 52, 243, 50, 176, 48, 173, 238, 189, 44, 235, 42,& & \\ 
& & 137, 184, 231, 38, 37, 228, 35, 226, 177, 224, 151, 156, 141,& & \\ 
& & 152, 154, 158, 157, 144, 149, 146, 148, 150, 155, 147, 153,& & \\ 
& & 145, 175, 206, 143, 12, 11, 142, 129, 128, 7, 198, 197, 4, 195,& & \\ 
& & 2, 161, 160, 255, 124, 109, 108, 122, 126, 125, 112, 117, 114,& & \\ 
& & 116, 100, 123, 98, 97, 113, 79, 106, 111, 110, 99, 74, 121,& & \\ 
& & 120, 71, 118, 103, 101, 115, 66, 65, 104, 127, 90, 89, 94, 83,& & \\ 
& & 91, 81, 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72,& & \\ 
& & 107, 78, 105, 64, 69, 102, 68, 70, 75, 67, 73, 96, 55, 58, 45,& & \\ 
& & 188, 51, 186, 61, 40, 119, 182, 181, 53, 179, 54, 33, 49, 15,& & \\ 
& & 174, 47, 60, 171, 46, 57, 32, 167, 6, 36, 164, 43, 162, 1, 0,& & \\ 
& & 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16,& & \\ 
& & 24, 13, 10, 29, 14, 3, 138, 41, 136, 39, 134, 133, 5, 131,& & \\ 
& & 34, 9, 8]&&\\
        \hline
      \end{tabular}
    \end{scriptsize}
  \end{center}
\caption{Fonctions avec matrices DSCC et le plus faible temps de mélange}\label{table:functions}
\end{table}

Le  tableau~\ref{table:functions} reprend  une synthèse de 
fonctions qui  ont été  générées selon  la méthode détaillée  
à la  section~\ref{sec:hamiltonian}.
Pour  chaque nombre $n=3$,  $4$, $5$ et $6$,
tous  les cycles  hamiltoniens non isomorphes  ont été générés.   Pour les
valeur de $n=7$ et $8$,  seuls $10^{5}$ cycles ont été évalués.  Parmi
toutes  les fonctions  obtenues en  enlevant du  $n$-cube ces  cycles,  n'ont été
retenues que celles  qui minimisaient le temps de mélange relatif  à une valeur de
$\epsilon$ fixée à $10^{-8}$ et pour un mode donné.  
Ce  nombre d'itérations (\textit{i.e.}, ce temps de mélange) 
est stocké dans la troisième
colonne sous la variable $b$.  
La variable $b'$ reprend le temps de mélange pour
l'algorithme~\ref{CI Algorithm}. 
On note que pour un nombre $n$ de bits fixé et un mode donné d'itérations, 
il peut y avoir plusieurs fonctions minimisant ce temps de mélange. De plus, comme ce temps 
de mélange est construit à partir de la matrice de Markov et que celle-ci dépend 
du mode, une fonction peut être optimale pour un mode et  ne pas l'être pour l'autre
(c.f. pour $n=5$).

Un second  résultat est  que ce nouvel  algorithme réduit grandement  le nombre
d'itérations  suffisant pour  obtenir une  faible  déviation par  rapport à  une
distribution uniforme.  On constate de  plus que ce nombre décroît avec
le nombre d'éléments alors qu'il augmente dans l'approche initiale où 
l'on marche.

Cela s'explique assez simplement. Depuis une configuration initiale, le nombre 
de configurations qu'on ne peut pas atteindre en une itération est de: 
\begin{itemize}
\item $2^n-n-1$ en unaire. Ceci représente un rapport de 
  $\dfrac{2^n-n-1}{2^n} = 1-\dfrac{n-1}{2^n}$ 
  de toutes les configurations; plus $n$ est grand, 
  plus ce nombre est proche de $1$, et plus grand devient le nombre 
  d'itérations nécessaires pour atteinte une déviation faible;
\item $2^n-2^{n-1}$ dans le cas généralisé,
  soit la moitié de toutes les configurations 
  quel que soit $n$; seul 1 bit reste constant tandis que tous les autres peuvent changer. Plus $n$ grandit, plus la proportion de bits constants diminue.
\end{itemize}

Cependant, dans le cas généralisé, chaque itération a une complexité 
plus élevée puisqu'il est nécessaire d'invoquer un générateur
produisant un nombre pseudo-aléatoire dans $[2^{n}]$ tandis qu'il suffit 
que celui-ci soit dans $[n]$ dans le cas unaire.
Pour comparer les deux approches, 
on considère que le générateur aléatoire embarqué est binaire, \textit{i.e.} ne génère qu'un bit (0 ou 1).

Dans le cas généralisé, si l'on effectue $b$ itérations, 
à chacune d'elles, la stratégie génère un nombre entre
$1$ et $2^n$. Elle fait donc $n$ appels à ce générateur.
On fait donc au total $b*n$ appels pour $n$ bits et
donc $b$ appels pour 1 bit généré en moyenne.
Dans le cas unaire, si l'on effectue $b'$ itérations, 
à chacune d'elle, la stratégie génère un nombre entre
$1$ et $n$. 
Elle fait donc $\ln(n)/\ln(2)$ appels à ce générateur binaire en moyenne. 
La démarche fait donc au total $b'*\ln(n)/\ln(2)$ appels pour $n$ bits et
donc $b'*\ln(n)/(n*\ln(2))$ appels pour 1 bit généré en moyenne.
Le tableau~\ref{table:marchevssaute} donne des instances de 
ces valeurs pour $n \in\{4,5,6,7,8\}$ et les fonctions  
données au tableau~\ref{table:functions}.
On constate que le nombre d'appels par bit généré décroît avec $n$ dans le 
cas des itérations généralisées et est toujours plus faible
que celui des itérations unaires.



\begin{table}[ht]
$$
\begin{array}{|l|l|l|l|l|l|}
\hline
\textrm{Itérations} & 4 & 5 & 6 & 7 & 8 \\ 
\hline
\textrm{Unaires}         &  19.0 & 22.3  & 23.7 & 25.3 & 27.0\\  
\hline
\textrm{Généralisées}    &  17   & 13    & 11   & 10   & 9\\
\hline
\end{array}
$$
\caption{Nombre moyen 
  d'appels à un générateur binaire par bit généré}\label{table:marchevssaute}
\end{table}




\section{Tests statistiques}\label{sec:prng;gray:tests}

La qualité des séquences aléatoires produites par 
le générateur des itérations unaires ainsi que 
celles issues des itérations généralisées a été évaluée à travers la suite 
de tests statistiques développée par le 
\emph{National Institute of Standards and Technology} (NIST).
En interne, c'est l'implantation de l'algorithme de Mersenne Twister qui
permet de générer la stratégie aléatoire.




 Pour les 15 tests, le seuil $\alpha$ est fixé à $1\%$:
 une  valeur  
 qui est plus grande que $1\%$  signifie 
 que la chaîne est considérée comme aléatoire avec une confiance de $99\%$.


Les tableaux~\ref{fig:TEST:generalise} donnent
une vision synthétique de ces expérimentations. 
Nous avons évalué les fonctions préfixées par 
$f$ (respectivement $g$) avec les générateurs issus des itérations 
généralisées (resp. unaires).
Quelle que soit la méthode utilisée, on constate que chacun des 
générateurs passe 
avec succès le test de NIST. 

Interpréter ces résultats en concluant que ces générateurs sont 
tous équivalents serait erroné: la meilleure des 
méthodes basées sur le mode des itérations
généralisées (pour $n=8$ par exemple) 
est au moins deux fois plus rapide que la meilleure de celles qui 
sont basées sur les itérations unaires.




%%%%%%%%% Relancer pour n=6, n=7, n=8
%%%%%%%%% Recalculer le MT
%%%%%%%%% Regenerer les 10^6 bits
%%%%%%%%% Evaluer sur NIST
 
\begin{table}[ht]
  \centering
  \begin{scriptsize}


\begin{tabular}{|l|r|r|r|r|}
 \hline 
Test & $f^{*5}$ &$f^{*6}$ &$f^{*7}$ &$f^{*8}$ \\ \hline 
Fréquence (Monobit)& 0.401 (0.97)& 0.924 (1.0)& 0.779 (0.98)& 0.883 (0.99)\\ \hline 
Fréquence ds un bloc& 0.574 (0.98)& 0.062 (1.0)& 0.978 (0.98)& 0.964 (0.98)\\ \hline 
Somme Cumulé*& 0.598 (0.975)& 0.812 (1.0)& 0.576 (0.99)& 0.637 (0.99)\\ \hline 
Exécution& 0.998 (0.99)& 0.213 (0.98)& 0.816 (0.98)& 0.494 (1.0)\\ \hline 
Longue exécution dans un bloc& 0.085 (0.99)& 0.971 (0.99)& 0.474 (1.0)& 0.574 (0.99)\\ \hline 
Rang& 0.994 (0.96)& 0.779 (1.0)& 0.191 (0.99)& 0.883 (0.99)\\ \hline 
Fourier rapide& 0.798 (1.0)& 0.595 (0.99)& 0.739 (0.99)& 0.595 (1.0)\\ \hline 
Patron sans superposition*& 0.521 (0.987)& 0.494 (0.989)& 0.530 (0.990)& 0.520 (0.989)\\ \hline 
Patron avec superposition& 0.066 (0.99)& 0.040 (0.99)& 0.304 (1.0)& 0.249 (0.98)\\ \hline 
Statistiques universelles& 0.851 (0.99)& 0.911 (0.99)& 0.924 (0.96)& 0.066 (1.0)\\ \hline 
Entropie approchée (m=10)& 0.637 (0.99)& 0.102 (0.99)& 0.115 (0.99)& 0.350 (0.98)\\ \hline 
Suite aléatoire *& 0.573 (0.981)& 0.144 (0.989)& 0.422 (1.0)& 0.314 (0.984)\\ \hline 
Suite aléatoire variante *& 0.359 (0.968)& 0.401 (0.982)& 0.378 (0.989)& 0.329 (0.985)\\ \hline 
Série* (m=10)& 0.469 (0.98)& 0.475 (0.995)& 0.473 (0.985)& 0.651 (0.995)\\ \hline 
Complexité linaire& 0.129 (1.0)& 0.494 (1.0)& 0.062 (1.0)& 0.739 (1.0)\\ \hline 

\end{tabular}
  \end{scriptsize}


\caption{Test de NIST pour les fonctions 
  du tableau~\ref{table:functions} selon les itérations généralisées}\label{fig:TEST:generalise}
\end{table}


\begin{table}[ht]
  \centering
  \begin{scriptsize}
\begin{tabular}{|l|r|r|r|r|}
\hline 
Test & $g^{*5}$& $g^{*6}$& $f^{*7}$& $f^{*8}$\\ \hline 
Fréquence (Monobit)& 0.236 (1.0)& 0.867 (0.99)& 0.437 (0.99)& 0.911 (1.0)\\ \hline 
Fréquence ds un bloc& 0.129 (0.98)& 0.350 (0.99)& 0.366 (0.96)& 0.657 (1.0)\\ \hline 
Somme Cumulé*& 0.903 (0.995)& 0.931 (0.985)& 0.863 (0.995)& 0.851 (0.995)\\ \hline 
Exécution& 0.699 (0.98)& 0.595 (0.99)& 0.181 (1.0)& 0.437 (0.99)\\ \hline 
Longue exécution dans un bloc& 0.009 (0.99)& 0.474 (0.97)& 0.816 (1.0)& 0.051 (1.0)\\ \hline 
Rang& 0.946 (0.96)& 0.637 (0.98)& 0.494 (1.0)& 0.946 (1.0)\\ \hline 
Fourier rapide& 0.383 (0.99)& 0.437 (1.0)& 0.616 (0.98)& 0.924 (0.99)\\ \hline 
Patron sans superposition*& 0.466 (0.990)& 0.540 (0.989)& 0.505 (0.990)& 0.529 (0.991)\\ \hline 
Patron avec superposition& 0.202 (0.96)& 0.129 (0.98)& 0.851 (0.99)& 0.319 (0.98)\\ \hline 
Statistiques universelles& 0.319 (0.97)& 0.534 (0.99)& 0.759 (1.0)& 0.657 (0.99)\\ \hline 
Entropie approchée (m=10)& 0.075 (0.97)& 0.181 (0.99)& 0.213 (0.98)& 0.366 (0.98)\\ \hline 
Suite aléatoire *& 0.357 (0.986)& 0.569 (0.991)& 0.539 (0.987)& 0.435 (0.992)\\ \hline 
Suite aléatoire variante *& 0.398 (0.989)& 0.507 (0.986)& 0.668 (0.991)& 0.514 (0.994)\\ \hline 
Série* (m=10)& 0.859 (0.995)& 0.768 (0.99)& 0.427 (0.995)& 0.637 (0.98)\\ \hline 
Complexité linaire& 0.897 (0.99)& 0.366 (0.98)& 0.153 (1.0)& 0.437 (1.0)\\ \hline 

\end{tabular}
\end{scriptsize}


\caption{Test de NIST pour les fonctions 
  du tableau~\ref{table:functions} selon les itérations unaires}\label{fig:TEST:unaire}
\end{table}


\begin{table}[ht]
  \centering
  \begin{scriptsize}

\begin{tabular}{|l|r|r|r|r|}
 \hline 
Test & 5 bits& 6 bits & 7 bits & 8bits  \\ \hline 
Fréquence (Monobit)& 0.289 (1.0)& 0.437 (1.0)& 0.678 (1.0)& 0.153 (0.99)\\ \hline 
Fréquence ds un bloc& 0.419 (1.0)& 0.971 (0.98)& 0.419 (0.99)& 0.275 (1.0)\\ \hline 
Somme Cumulé*& 0.607 (0.99)& 0.224 (0.995)& 0.645 (0.995)& 0.901 (0.99)\\ \hline 
Exécution& 0.129 (0.99)& 0.005 (0.99)& 0.935 (0.98)& 0.699 (0.98)\\ \hline 
Longue exécution dans un bloc& 0.514 (1.0)& 0.739 (0.99)& 0.994 (1.0)& 0.834 (0.99)\\ \hline 
Rang& 0.455 (0.97)& 0.851 (0.99)& 0.554 (1.0)& 0.964 (0.99)\\ \hline 
Fourier rapide& 0.096 (0.98)& 0.955 (0.99)& 0.851 (0.97)& 0.037 (1.0)\\ \hline 
Patron sans superposition*& 0.534 (0.990)& 0.524 (0.990)& 0.508 (0.987)& 0.515 (0.99)\\ \hline 
Patron avec superposition& 0.699 (0.99)& 0.616 (0.95)& 0.071 (1.0)& 0.058 (1.0)\\ \hline 
Statistiques universelles& 0.062 (0.99)& 0.071 (1.0)& 0.637 (1.0)& 0.494 (0.98)\\ \hline 
Entropie approchée (m=10)& 0.897 (0.99)& 0.383 (0.99)& 0.366 (1.0)& 0.911 (0.99)\\ \hline 
Suite aléatoire *& 0.365 (0.983)& 0.442 (0.994)& 0.579 (0.992)& 0.296 (0.993)\\ \hline 
Suite aléatoire variante *& 0.471 (0.978)& 0.559 (0.992)& 0.519 (0.987)& 0.340 (0.995)\\ \hline 
Série* (m=10)& 0.447 (0.985)& 0.298 (0.995)& 0.648 (1.0)& 0.352 (0.995)\\ \hline 
Complexité linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hline 

\end{tabular}










  \end{scriptsize}


\caption{Test de NIST pour l'algorithme de Mersenne Twister}\label{fig:TEST:Mersenne}
\end{table}


\section{Conclusion}
Ce chapitre a montré comment construire un PRNG chaotique, notamment à partir 
de codes de Gray équilibrés. Une méthode complètement automatique de
construction de ce type de codes a été présentée étendant les méthodes 
existantes. 
Dans le cas des itérations unaires, 
l'algorithme qui en découle a un temps de mélange qui a 
un majorant quadratique de convergence vers la distribution uniforme. 
Pratiquement,  ce temps de mélange se rapproche de $N\ln N$.
Les expérimentations au travers de la batterie de test de NIST ont montré
que toutes les propriétés statistiques sont obtenues pour
 $\mathsf{N} = 4, 5, 6, 7, 8$.