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 une
-méthode permettant de générer de telles matrices.
-
-Les approches théoriques basées sur la programmation logique par contraintes sur
-domaines finis ne sont pas envisageables en pratique dès que la taille des
-matrices considérées devient suffisamment grande.
-
+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, ce qui revient à supprimer en chaque n{\oe}ud de ce graphe une
-arête sortante et une arête entrante.
+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 dit é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és en section~\ref{sec:prng;gray:tests}.
+Les sections~\ref{sec:plc} à~\ref{sub:gray} ont été publiées
+à~\cite{chgw+14:oip}.
% This aim of this section is to show
\item Toutes les éléments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positif, \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
+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}
valent True si et seulement si $R$
est le produit matriciel (ou la somme matricielle)
entre $X$ and $Y$ respectivement.
-il n'est pas difficile d'adapter ce code à n'importe quelle valeur
+Il n'est pas difficile d'adapter ce code à n'importe quelle valeur
entière naturelle $\mathsf{N}$.
\begin{figure}[ht]
\end{figure}
Enfin, on définit la relation $\mathcal{R}$, qui est établie pour les deux
-fonctions $f$ et $g$ si leur graphes
-respectifs $\textsf{giu}(f)$ et $\textsf{giu}(g)$
+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 personnelle, PROLOG trouve
+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,
Cependant, pour des valeurs de $n$ petites, nous avons
comparé les fonctions non équivalentes selon leur proportion
-à engendrer des temps de mélange petits (cf. équation~\ref{eq:mt:ex}).
+à engendrer des temps de mélange petits (cf. équation~(\ref{eq:mt:ex})).
(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 le graphe $\textsc{giu}(f)$ est
+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 suppression d'un cycle hamiltonien dans une matrice de Markov $M$, issue du
$n$-cube, produit une matrice doublement stochastique.
\end{theorem}
-\begin{Proof}
+\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)$
-est ainsi enlevé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.
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}
+\end{proof}
\end{theorem}
-\begin{Proof}
+\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
depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsf{giu}$ qui
étend le précédent graphe est ainsi fortement connexe.
-\end{Proof}
+\end{proof}
%Les preuves, relativement directes, sont laissées en exercices au lecteur.
-La génération de cycles hamiltoniens dans le
-$n$-cube, ce qui revient à trouver des \emph{codes de Gray cycliques}. On
-rappelle que les codes de Gray sont des séquences de mots binaires de taille
-fixe ($n$), dont les éléments successifs ne différent que par un seul bit. Un
+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}
-La borne inférieure du nombre de codes de Gray ($\left(\frac{n*\log2}{e \log
+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 $\textsf{giu}(f)$ \emph{uniforme}. Cette uniformité se traduit par des
+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}.
-Un code de Gray équilibré peut être défini de la façon suivante :
-
-\begin{Def}[Code de Gray cyclique équilibré]\label{def:grayequ}
- 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{NT}_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$.
+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{NT}_n(i) - \textit{NT}_n(j)| \le 2$. Il est
- \textbf{totalement équilibré} si $\forall
- i\in\{1,...,n\},~\textit{NT}_n(i)=\frac{2^n}{n}$.
-\end{Def}
+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{NT}_n(i)$ est pair
+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{NT}_n(i)=\lfloor\frac{2^n}{n}\rfloor$ ou
+$\textit{TC}_n(i)=\lfloor\frac{2^n}{n}\rfloor$ ou
$\textit{NT}_n(i)=\lceil\frac{2^n}{n}\rceil, \forall i\in\{1,...,n\}$ et
-vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$.
+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
\section{Génération de codes de Gray équilibrés par induction}
\label{sec:induction}
-De nombreuses approches ont été developpées pour résoudre le problème de construire
+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.
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 autheurs de~\cite{ZanSup04} présentent une extension de l'algorithme de
+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
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.
+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-sequences
+\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 sequences $u_0, u_1, u_2, \ldots, u_{l-2}$
+\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} Contruire les séquences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$. Soit alors $W'$ définie commé étant égale à $W$ sauf pour les
+\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 concatenation $U^R, V, W'$.
+\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é.
-La théoreme suivante montre que c'est possible et sa preuve explique comment le faire.
+La théorème suivante montre que c'est possible et sa preuve,
+donnée en annexes~\ref{anx:generateur}, explique comment le faire.
-
-\begin{theorem}\label{prop:balanced}
+\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
le nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$
sont tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$
pour chaque $i$, $1 \le i \le \mathsf{N}$.
-\end{theorem}
-
-La preuve de ce théorème est donnée en annexes~\ref{anx:generateur}.
+\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}
+\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
\begin{theorem} \label{prop:stop}
-Si $\ov{h}$ is bijective et anti involutive
+Si $\ov{h}$ est bijective et anti involutive
$\ov{h}(\ov{h}(X))\neq X$, alors
$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$.
\end{theorem}
On remarque tout d'abord que la chaîne de Markov proposée ne suit pas exactement
l'algorithme~\ref{CI Algorithm}. En effet dans la section présente,
la probabilité de rester dans une configuration donnée
-est fixée à $frac{1}{2}+\frac{1}{2n}$.
-Dans l'algorithme initial, celle-ci est de ${1}{n}$.
+est fixée à $\frac{1}{2}+\frac{1}{2n}$.
+Dans l'algorithme initial, celle-ci est de $\frac{1}{n}$.
Cette version, qui reste davantage sur place que l'algorithme original,
-a été introduite pour simplifier le calcul de la borne sup
+a été introduite pour simplifier le calcul d'un majorant
du temps d'arrêt.
Sans entrer dans les détails de la preuve, on remarque aussi
-que le calcul de cette borne impose uniquement que
+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, la borne supérieure pourrait être réduite.
+En intégrant cette contrainte, ce majorant pourrait être réduite.
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 é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 algorithm~\ref{algo:stop} retourne le
+$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 fonctionss ont été générées comme dans
+$ 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 resultats. Dans celle-ci, un cercle représente une approximation de
+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 cosntate que l'approximation de $E[\ts]$ est largement inférieure
-à la borne quadratique donnée au thérème~\ref{prop:stop} et que la conjecture
+On constate que l'approximation de $E[\ts]$ est largement inférieure
+à le majorant quadratique donné au théorème~\ref{prop:stop} et que la conjecture
donnée au paragraphe précédent est sensée.
}
\Return{$\textit{nbit}$}\;
%\end{scriptsize}
-\caption{Pseudo Code of stoping time calculus }
+\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{Average Stopping Time Approximation}\label{fig:stopping:moy}
+\caption{Interpolation du temps d'arrêt}\label{fig:stopping:moy}
\end{figure}
-\section{Et les itérations généralisées?}
-Le chaptire précédent a présenté un algorithme de
+\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 à
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)$ vaudraitt $\{3,2\}$.
+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$.
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écroit avec
+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.
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écroit avec $n$ dans le
+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.
-\section{Tests statistiques}
+\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
Les tableau~\ref{fig:TEST:generalise} donnent
une vision synthétique de ces expérimentations.
Nous avons évalué les fonctions préfixées par
-$f$ (respecitvement $g$) avec les générateurs issus des itérations
+$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 succes le test de NIST.
+avec succès le test de NIST.
-Interpréter ces resultats en concluant que ces générateurs sont
+Interpréter ces résultats en concluant que ces générateurs sont
tous équivalents serait erroné: la meilleur des
méthodes basées sur le mode des itérations
généralisées (pour $n=8$ par exemple)
\end{table}
-%
+\section{Conclusion}
+Ce chaptitre 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$.
+
