X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/8c5f5bb69a77f78225c686a1deeb7b6f365452f2..749714e242c186d9017fa85964d6c67edf1bf4d1:/14Secrypt.tex diff --git a/14Secrypt.tex b/14Secrypt.tex index 597acbb..69fb6d8 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -1,16 +1,29 @@ 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 @@ -45,7 +58,7 @@ la matrice est stochastique à droite; \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} @@ -57,7 +70,7 @@ ici pour $\mathsf{N} = 2$. Dans ce code, 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] @@ -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}\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, @@ -109,7 +122,7 @@ en s'appuyant sur l'efficience de l'algorithme de backtrack natif de PROLOG. 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})). @@ -156,7 +169,7 @@ 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}. @@ -265,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. @@ -289,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} @@ -299,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 @@ -312,56 +325,54 @@ 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 é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 @@ -380,47 +391,69 @@ vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$. \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é. +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{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} extension telle que +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{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 @@ -541,32 +574,96 @@ 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} + +Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction +telle que pour $X \in \Bool^{\mathsf{N}} $, +$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. +La fonction $\ov{h}$ est dite {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$, +$\ov{h}(\ov{h}(X))\neq X$. + + \begin{theorem} \label{prop:stop} -If $\ov{h}$ is bijective et telle que if for every $X\in \Bool^{\mathsf{N}}$, +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} -Sans entrer dans les détails de la preuve, on remarque tout d'abord -que le calcul -de cette borne n'intègre pas 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. - -On remarque ensuite que la chaîne de Markov proposée ne suit pas exactement +Les détails de la preuve sont donnés en annexes~\ref{anx:generateur}. +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 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é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 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 +à 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. -\section{Et les itérations généralisées?} -Le chaptire précédent a présenté un algorithme de +\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 à @@ -599,7 +696,7 @@ 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)$ 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$. @@ -775,7 +872,7 @@ du mode, une fonction peut être optimale pour un mode et ne pas l'être pour l 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. @@ -813,7 +910,7 @@ 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é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. @@ -838,7 +935,7 @@ $$ -\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 @@ -860,13 +957,13 @@ permet de générer la stratégie aléatoire. 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) @@ -986,4 +1083,16 @@ Complexité linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hl \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$. +