X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/103fee06d77ee199f8956ccb0747b45676c834e5..d33e664452e3655370cbe069e3f6fbd16842c818:/14Secrypt.tex?ds=inline diff --git a/14Secrypt.tex b/14Secrypt.tex index b2ae05d..5e4cafc 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -1,27 +1,40 @@ 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. - - -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} +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é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 +% 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 @@ -42,10 +55,10 @@ 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 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; +\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 +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} @@ -56,8 +69,8 @@ ici pour $\mathsf{N} = 2$. Dans ce code, \verb+summ(+$X,Y,R$\verb+)+ 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 +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] @@ -87,15 +100,15 @@ bistoc(X):- \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} -Exécutée sur un ordinateur personnelle, PROLOG trouve +%\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, @@ -107,14 +120,14 @@ Cette approche, basée sur une démarche de type \emph{générer, tester} ne peu 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 valeurs de $n$ petites, nous avons +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}). +à engendrer des temps de mélange petits (cf. équation~(\ref{eq:mt:ex})). -\begin{xpl} +\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] @@ -126,13 +139,13 @@ $$ \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 \\ +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}, & \\ +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}, & \\ +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 \\ @@ -149,14 +162,14 @@ $$ \end{table} \end{xpl} -Une analyse syntaxique de ces fonctions ne permet pas, à priori, +Une analyse syntaxique de ces fonctions ne permet pas, a priori, de déduire des règles permettant de construire de nouvelles -fonction dont le temps de mélange serait faible. +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 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}. @@ -182,57 +195,80 @@ On s'intéresse par la suite à la génération de ce genre de cycles. \begin{minipage}{0.35\linewidth} \begin{scriptsize} \begin{center} - $ \dfrac{1}{4} \left( - \begin{array}{cccccccc} - 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ + +\[ +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 \\ + % 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ - 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ + % 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ - 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ + % 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ - 1 & 0 & 1 & 0 & 1 & 0 & 1 & 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 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ + % 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ - 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ + % 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ - \end{array} \right) $ + % \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} + (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} -% Secrypt 14 +% section{Graphes +% $\textsc{giu}(f)$ +% $\textsc{gig}(f)$ +% fortement connexes et doublement stochastiques}\label{sec:gen:dblstc} +% % +%Secrypt 14 -\subsection{Suppression des cycles hamiltoniens} +\section{Suppression des cycles hamiltoniens} \label{sec:hamiltonian} -Dans un premier temps, nous montrons en section~\ref{sub:removing:theory} que la +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} +%\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 @@ -242,12 +278,12 @@ connexité du graphe d'itérations. 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. @@ -266,7 +302,7 @@ $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} +\end{proof} @@ -276,7 +312,7 @@ $M$ est donc doublement stochastique. \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 @@ -284,61 +320,59 @@ 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 évidement un cycle hamiltonien et contient tous les n{\oe}uds. -Tous les n{\oe}uds de $C_1$ dans lequel $c$ a été enlevé sont accessibles -depuis n'importe quel n{\oe}ud. Le graphe des itérations $\textsf{giu}$ qui +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} +\end{proof} -Les preuves, relativement directes, sont laissées en exercices au lecteur. Par -contre, ce qui est moins aisé est 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 +%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. -\subsection{Lien avec les codes de Gray cycliques (totalement) équilibrés} +\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{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$. +$\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 @@ -354,50 +388,72 @@ vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$. ce code est totalement équilibré. \end{xpl} -\subsection{Génération de codes de Gray équilibrés par induction} +\section{Génération de codes de Gray équilibrés par induction} \label{sec:induction} -Dans leur article de 2004~\cite{ZanSup04}, Zanten et Suparta proposent un -algorithme inductif pour générer des codes de Gray équilibrés de $n$ bits à -partir de codes de $n-2$ bits. Cependant, leur méthode n'est pas -constructive. En effet, elle effectue des manipulations sur un partitionnement du -code de Gray initial de $n-2$ bits pour obtenir un code de Gray sur $n$ bits, -mais le résultat n'est pas systématiquement équilibré. Il est donc nécessaire -d'évaluer les résultats obtenus à partir de tous les partitionnements réalisables -en suivant les contraintes spécifiées. Or, le nombre de possibilités augmente -exponentiellement (voir~\cite{Mons14} pour l'évaluation détaillée), ce qui rend -déraisonnable tout parcours exhaustif. Une amélioration proposée -dans~\cite{Mons14} permet de réduire le nombre de partitionnements considérés, -mais l'ordre de grandeur reste similaire. On constate donc clairement ici la -nécessité de trouver des algorithmes de génération de codes de Gray équilibrés -plus efficaces. Ce problème représente une des voies que nous souhaitons -explorer dans la suite de nos travaux. - -Le tableau~\ref{table:nbFunc} donne le nombre de fonctions différentes -compatibles avec les codes de Gray équilibrés générés par l'approche précédente -selon le nombre de bits. Il donne donc la taille de la classe des générateurs -pouvant être produits. Les cas 7 et 8 ne sont que des bornes minimales basées -sur des sous-ensembles des partitionnements possibles. - -\begin{table}[ht] - \begin{center} - \begin{tabular}{|l|c|c|c|c|c|} - \hline - $n$ & 4 & 5 & 6 & 7 & 8 \\ - \hline - nb. de fonctions & 1 & 2 & 1332 & $>$ 2300 & $>$ 4500 \\ - \hline - \end{tabular} - \end{center} -\caption{Nombre de codes de Gray équilibrés selon le nombre de bits.}\label{table:nbFunc} -\end{table} - +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}$. -Ces fonctions étant générée, on s'intéresse à étudier à quelle vitesse +\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} +\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 @@ -405,11 +461,11 @@ 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ération est toujours un sous graphe +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 +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. @@ -421,6 +477,8 @@ 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 @@ -428,7 +486,7 @@ probabilités $p$ définie sur l'ensemble des arcs comme suit: $$ p(e) \left\{ \begin{array}{ll} -= \frac{2}{3} \textrm{ si $e=(v,v)$ avec $v \in \Bool^3$,}\\ += \frac{1}{2} + \frac{1}{6} \textrm{ si $e=(v,v)$ avec $v \in \Bool^3$,}\\ = \frac{1}{6} \textrm{ sinon.} \end{array} \right. @@ -451,7 +509,17 @@ P=\dfrac{1}{6} \left( \] \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 @@ -462,7 +530,7 @@ $$\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 on $\Bool^{\mathsf{N}}$, on a +$\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}}$. @@ -475,56 +543,529 @@ $$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 32 {\mathsf{N}}^2+ 16{\mathsf{N}}\ln ({\mathsf{N}}+1) = O(N^2). +\] +\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$ en unaire. Ceci représente un rapport de + $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{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. -Un résultat classique est -$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$ + 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\%$. -Soit $(X_t)_{t\in \mathbb{N}}$ une suite de variables aléatoires de -$\Bool^{\mathsf{N}}$. -une variable aléatoire $\tau$ dans $\mathbb{N}$ est un -\emph{temps d'arrêt} pour la suite -$(X_i)$ si pour chaque $t$ il existe $B_t\subseteq -(\Bool^{\mathsf{N}})^{t+1}$ tel que -$\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$. -En d'autres termes, l'événement $\{\tau = t \}$ dépend uniquement des valeurs -de -$(X_0,X_1,\ldots,X_t)$, et non de celles de $X_k$ pour $k > t$. +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} -Soit $(X_t)_{t\in \mathbb{N}}$ une chaîne de Markov et -$f(X_{t-1},Z_t)$ une représentation fonctionnelle de celle-ci. -Un \emph{temps d'arrêt aléatoire} pour la chaîne de -Markov est un temps d'arrêt pour -$(Z_t)_{t\in\mathbb{N}}$. -Si la chaîne de Markov est irréductible et a $\pi$ -comme distribution stationnaire, alors un -\emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire -(qui peut dépendre de la configuration initiale $X$), -tel que la distribution de $X_\tau$ est $\pi$: -$$\P_X(X_\tau=Y)=\pi(Y).$$ +\caption{Test de NIST pour les fonctions + du tableau~\ref{table:functions} selon les itérations unaires}\label{fig:TEST:unaire} +\end{table} -Un temps d'arrêt $\tau$ est qualifié de \emph{fort} si $X_{\tau}$ -est indépendant de $\tau$. On a les deux théorèmes suivants, dont les -démonstrations sont données en annexes~\ref{anx:generateur}. +\begin{table}[ht] + \centering + \begin{scriptsize} -\begin{theorem} -Si $\tau$ est un temps d'arrêt fort, alors $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}} -\P_X(\tau > t)$. -\end{theorem} +\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 -\begin{theorem} \label{prop:stop} -If $\ov{h}$ is bijective et telle que if for every $X\in \Bool^{\mathsf{N}}$, -$\ov{h}(\ov{h}(X))\neq X$, alors -$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. -\end{theorem} +\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$. -Sans entrer dans les détails de la preuve, on remarque que le calcul -de cette borne ne tient pas en compte le fait qu'on préfère enlever des -chemins hamiltoniens équilibrés. -En intégrant cette contrainte, la borne supérieure pourrait être réduite.