From d81b15b2024adaf639e9d4a85934a5b5722c1bf1 Mon Sep 17 00:00:00 2001 From: couchot Date: Mon, 5 Sep 2016 17:14:37 +0200 Subject: [PATCH] jusqu'au chpitre 6 --- 14Secrypt.tex | 134 +++++++++++++++++------------------ 15RairoGen.tex | 77 ++++++++++---------- annexePreuveDistribution.tex | 50 +++++-------- annexePreuveMixage.tex | 8 +-- annexePromelaProof.tex | 20 +++--- annexesccg.tex | 12 ++-- caracgeneralise.tex | 8 +-- caracunaire.tex | 8 +-- main.tex | 3 +- modelchecking.tex | 4 +- 10 files changed, 154 insertions(+), 170 deletions(-) diff --git a/14Secrypt.tex b/14Secrypt.tex index 10a4f85..76e635b 100644 --- a/14Secrypt.tex +++ b/14Secrypt.tex @@ -13,12 +13,12 @@ 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 litérature. +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 unifiorme est étduiée théoriquement et pratiquement à la +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é à la +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}. @@ -58,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} @@ -70,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] @@ -100,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, @@ -122,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})). @@ -169,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}. @@ -278,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. @@ -302,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} @@ -312,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 @@ -325,15 +325,15 @@ 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. @@ -344,37 +344,35 @@ La borne inférieure du nombre de codes de Gray ($\left(\frac{n*\log2}{e \lo \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 @@ -393,7 +391,7 @@ 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} -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. @@ -404,7 +402,7 @@ 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 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 @@ -414,43 +412,43 @@ Cependant les auteurs ne prouvent pas que leur approche fournit systématiquemen 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} 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 +de l'algorithme de \emph{Robinson-Cohn} 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{theorem} -La preuve de ce théorème est donnée en annexes~\ref{anx:generateur}. - 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. @@ -585,7 +583,7 @@ $\ov{h}(\ov{h}(X))\neq X$. \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} @@ -594,8 +592,8 @@ 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 du temps d'arrêt. @@ -616,17 +614,17 @@ 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 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 +à la borne quadratique donnée au théorème~\ref{prop:stop} et que la conjecture donnée au paragraphe précédent est sensée. @@ -650,7 +648,7 @@ $\textit{fair}\leftarrow\emptyset$\; } \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} @@ -658,14 +656,14 @@ $\textit{fair}\leftarrow\emptyset$\; \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?}\label{sec:prng:gray:general} -Le chaptire précédent a présenté un algorithme de +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 à @@ -698,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$. @@ -874,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. @@ -912,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. @@ -959,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) @@ -1087,7 +1085,7 @@ Complexité linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hl \section{Conclusion} Ce chaptitre a montré comment construire un PRNG chaotique, notamment à partir -de codes de Gray équilibrés. Une méthode completement automatique de +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, diff --git a/15RairoGen.tex b/15RairoGen.tex index 06f84b1..d905e51 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -6,25 +6,17 @@ le mot $x^b$ devrait \og sembler ne plus dépendre\fg{} de $x^0$. On peut penser à exploiter une de ces fonctions $G_f$ comme un générateur aléatoire. -Ce chapitre présente une application directe +Ce chapitre présente donc une application directe de la théorie développée ci-avant à la génération de nombres pseudo aléatoires. +La section~\ref{sub:prng:algo} +présente tout d'abord l'algorithme de PRNG. La contrainte de +distribution uniforme de la sortie est discutée dans cette section. +La chaoticité du générateur est ensuite étudiée en +section~\ref{prng:unaire:chaos}. +La section~\ref{sub:prng:algo} a été publiéeà~\cite{bcgw11:ip,bcgr11:ip}. -La suite de ce document donnera -une condition nécessaire est suffisante pour que -cette propriété soit satisfaite. - - -On présente tout d'abord le générateur -basé sur des fonctions chaotiques (section~\ref{sub:prng:algo}), -puis comment intégrer la contrainte de distribution uniforme -de la sortie -dans le choix de la fonction à itérer (section~\ref{sub:prng:unif}). -L'approche est évaluée dans la dernière section. -\JFC{plan à revoir} - - \section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo} @@ -304,7 +296,7 @@ ait une distribution suffisamment proche de la distribution uniforme. On énonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}. -\begin{theorem}\label{thm:prng:u} +\begin{restatable}[Uniformité de la sortie de l'algorithme~\ref{CI Algorithm}]{theorem}{PrngCIUniforme}\label{thm:prng:u} Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son graphe d'itérations , $\check{M}$ sa matrice d'adjacence et $M$ une matrice $2^n\times 2^n$ @@ -315,7 +307,7 @@ On énonce directement le théorème suivant dont la preuve est donnée en annex l'algorithme~\ref{CI Algorithm} suit une loi qui tend vers la distribution uniforme si et seulement si $M$ est une matrice doublement stochastique. -\end{theorem} +\end{restatable} \subsection{Quelques exemples} @@ -454,7 +446,7 @@ Montrer que les sous-séquences de suites chaotiques ainsi générées demeuren est l'objectif de la section suivante. -\section{Un PRNG basé sur des itérations unaires qui est chaotique } +\section{Un PRNG basé sur des itérations unaires qui est chaotique }\label{prng:unaire:chaos} Cette section présente un espace métrique adapté au générateur de nombres pseudo-aléatoires présenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente @@ -661,9 +653,11 @@ la séquence. On a la proposition suivante, qui est démontrée en annexes~\ref{anx:generateur}. -\begin{lemma} + + +\begin{restatable}[Une distance dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$]{theorem}{distancedsxnp} $d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. -\end{lemma} +\end{restatable} \subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant $\textsc{giu}(f)$} @@ -743,24 +737,33 @@ Le dernier donnerait le comportement d'un générateur qui s'autoriserait Le théorème suivant, similaire à ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$ est prouvé en annexes~\ref{anx:generateur}. -\begin{theorem} +\begin{restatable}[Conditions pour la choticité de $G_{f_u,\mathcal{P}}$]{theorem}{thmchoticitgfp} La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si -graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ +le graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ est fortement connexe. -\end{theorem} -On alors corollaire suivant - -\begin{corollary} - Le générateur de nombre pseudo aléatoire détaillé - à l'algorithme~\ref{CI Algorithm} - n'est pas chaotique - sur $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ pour la fonction négation. -\end{corollary} -\begin{proof} - Dans cet algorithme, $\mathcal{P}$ est le singleton $\{b\}$. - Que $b$ soit pair ou impair, $\textsc{giu}_{\{b\}}(f)$ - n'est pas fortement connexe. -\end{proof} - +\end{restatable} +% On alors corollaire suivant + +% \begin{corollary} +% Le générateur de nombre pseudo aléatoire détaillé +% à l'algorithme~\ref{CI Algorithm} +% n'est pas chaotique +% sur $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ pour la fonction négation. +% \end{corollary} +% \begin{proof} +% Dans cet algorithme, $\mathcal{P}$ est le singleton $\{b\}$. +% Que $b$ soit pair ou impair, $\textsc{giu}_{\{b\}}(f)$ +% n'est pas fortement connexe. +% \end{proof} + + +\section{Conclusion} +Ce chapitre a proposé un algorithme permettant de construire un +PRNG chaotique à partir d'un PRNG existant. Pour ce faire, il est nécessaire +et suffisant que la fonction $f$ qui est itérée un nombre $b$ de fois +possède un $\textsc{giu}_{\{b\}}(f)$ fortement connexe et que sa matrice de Markov assosiée soit doublement stochastique. +Le chapitre suivant montre comment construire une telle fonction. + + diff --git a/annexePreuveDistribution.tex b/annexePreuveDistribution.tex index f53e3b9..ea5f4f1 100644 --- a/annexePreuveDistribution.tex +++ b/annexePreuveDistribution.tex @@ -1,4 +1,5 @@ - + +\section{Chaînes de Markov associées à $\textsc{giu}(f)$} Considérons le lemme technique suivant: \begin{lemma}\label{lem:stoc} Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\textsc{giu}(f)$, et $M$ la matrice @@ -8,7 +9,7 @@ Alors $M$ est une matrice stochastique régulière si et seulement si $\textsc{giu}(f)$ est fortement connexe. \end{lemma} -\begin{Proof} +\begin{proof} On remarque tout d'abord que $M$ est une matrice stochastique par construction. Supposons $M$ régulière. @@ -28,22 +29,11 @@ on peut conclure que, si $k$ est le plus petit multiple commun de $\{k_{ij} \big/ i,j \in \llbracket 1, 2^n \rrbracket \}$ alors $\forall i,j \in \llbracket 1, 2^n \rrbracket, \check{M}_{ij}^{k}>0$. Ainsi, $\check{M}$ et donc $M$ sont régulières. -\end{Proof} - -Ces résultats permettent formuler et de prouver le théorème suivant: - -\begin{theorem} - Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son - graphe d'itérations , $\check{M}$ sa matrice d'adjacence - et $M$ une matrice $2^n\times 2^n$ définie comme dans le lemme précédent. - Si $\textsc{giu}(f)$ est fortement connexe, alors - la sortie du générateur de nombres pseudo aléatoires détaillé par - l'algorithme~\ref{CI Algorithm} suit une loi qui - tend vers la distribution uniforme si - et seulement si $M$ est une matrice doublement stochastique. -\end{theorem} - -\begin{Proof} +\end{proof} + +Ces résultats permettent formuler et de prouver le théorème annoncé. +\PrngCIUniforme* +\begin{proof} $M$ est une matrice stochastique régulière (Lemme~\ref{lem:stoc}) qui a un unique vecteur de probabilités stationnaire (Théorème \ref{th}). @@ -53,14 +43,13 @@ Ces résultats permettent formuler et de prouver le théorème suivant: la somme des valeurs de chaque colonne de $M$ est 1, \textit{i.e.} si et seulement si $M$ est doublement stochastique. -\end{Proof} - +\end{proof} +\section{Chaoticité de la fonction $G_{f_u,\mathcal{P}}$ dans +$(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$} -Montrons que -\begin{lemma} -$d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. -\end{lemma} +Montrons le théorème +\distancedsxnp* \begin{proof} @@ -172,15 +161,8 @@ $$a_0^0, ...,a_{k_2}^{|a_{k_2}|}...),(v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,v est un point périodique dans le voisinage $\mathcal{B}(x,\varepsilon)$ de $x$. \end{proof} -$G_{f_u,\mathcal{P}}$ étant topologiquement transitive and regulière, -on peut conclure le théorème: - - -\begin{theorem} -La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur - $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si -graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ -est fortement connexe. -\end{theorem} +$G_{f_u,\mathcal{P}}$ étant topologiquement transitive and régulière, +on peut démontrer le théorème: +\thmchoticitgfp* diff --git a/annexePreuveMixage.tex b/annexePreuveMixage.tex index 12c3223..8132c68 100644 --- a/annexePreuveMixage.tex +++ b/annexePreuveMixage.tex @@ -12,7 +12,7 @@ s'il existe un chemin de longueur $\alpha$ élément $i\in$ \class{p} et $j \in$ \class{q} tel que $i \le j$ si et seulement si \class{p} $\preceq$ \class{q}. - \begin{Proof} + \begin{proof} Tout d'abord, soit \class{p_1}, \ldots, \class{p_l} des classes contenant respectivement les éléments $n_1$,\ldots, $n_l$ @@ -59,7 +59,7 @@ s'il existe un chemin de longueur $\alpha$ \class{p} $\preceq$ \class{q'} et pour chaque $i$, $k$ tels que $i \in$ \class{p} et $k \in$ \class{q'}, $i \le k$ et le résultat est établi. - \end{Proof} + \end{proof} \end{lemma} On peut remarquer que ce processus de renommage est inspiré des \emph{graphes @@ -70,7 +70,7 @@ On peut remarquer que ce processus de renommage est inspiré des \emph{graphes % Processes numbers are already compliant with the order $\preceq$. % \end{xpl} -\begin{Proof}[du théorème~\ref{th:cvg}] +\begin{proof}[du théorème~\ref{th:cvg}] Le reste de la preuve est fait par induction sur le numéro de classe. Considérons la première classe \class{b_1} de $n_1$ éléments @@ -98,7 +98,7 @@ On peut remarquer que ce processus de renommage est inspiré des \emph{graphes où tous les éléments de \class{b_j}, $1 \le j \le k$, ont des valeurs constantes. D'après les hypothèses du théorème, cela converge. -\end{Proof} +\end{proof} diff --git a/annexePromelaProof.tex b/annexePromelaProof.tex index 3675094..6b3adaa 100644 --- a/annexePromelaProof.tex +++ b/annexePromelaProof.tex @@ -11,13 +11,13 @@ du chapitre~\ref{chap:promela}. le le scheduler met à jour les elements of $S^t$ donnés par \verb+update_elems+ à l'iteration $t$. \end{lemma} -\begin{Proof} +\begin{proof} La preuve est directe pour $t=0$. Supposons qu'elle est établie jusqu'en $t$ vallant un certain $t_0$. On considère des stratégies pseudo périodiques. Grâce à l'hypothèse d'équité faible, \verb+update_elems+ modifie les éléments de $S^t$ à l'iteration $t$. -\end{Proof} +\end{proof} Dans ce qui suit, soit $Xd^t_{ji}$ la valeur de \verb+Xd[+$j$\verb+].v[+$i$\verb+]+ après le $t^{\text{ème}}$ appel @@ -123,7 +123,7 @@ la variable \verb+Xp[k]+ en sortant du processus $X_k^{t}$ \textit{i.e.}, $F_{k}\left( X_1^{D_{k\,1}^{t-1}},\ldots, X_{\mathsf{N}}^{D_{k\,{\mathsf{N}}}^{t-1}}\right)$ à la fin de la $t^{\text{th}}$ itération. \end{lemma} -\begin{Proof} +\begin{proof} La preuve est faite par induction sur le nombre d'itérations. \paragraph{Situation initiale:} @@ -235,7 +235,7 @@ $\verb+Xp[+k\verb+]+= F(\verb+Xd[+k\verb+][0]+ \ldots,\verb+Xd[+k\verb+][+n\verb+-1]+)+$. Par définition $Xd=F(Xd^{l+1}_{k\,0}, \ldots,Xd^{l+1}_{k\,n-1})$. Grace à~\Equ{eq:correct_retrieve} déjà prouvée, on peut conclure la preuve. -\end{Proof} +\end{proof} \begin{lemma} @@ -244,17 +244,17 @@ Grace à~\Equ{eq:correct_retrieve} déjà prouvée, on peut conclure la preuve. $\delta_0$. \end{lemma} -\begin{Proof} +\begin{proof} Pour chaque $i$ et $j$, à chaque itération $t+1$, comme les délais sont bornés par $\delta_0$, l'élément $i$ doit connaître au plus $\delta_0$ valeurs qui sont $X_j^{t}$, \ldots, $X_j^{t-\delta_0+1}$. Elles peuvent être mémorisées dans n'importe quel cannal de taille $\delta_0$. -\end{Proof} +\end{proof} \promelasound* -\begin{Proof} +\begin{proof} % For the case where the strategy is finite, one notice that property % verification is achieved under weak fairness property. Instructions that % write or read into \verb+channels[j].sent[i]+ are continuously enabled leading @@ -267,7 +267,7 @@ Grace à~\Equ{eq:correct_retrieve} déjà prouvée, on peut conclure la preuve. Si des itérations du système dynamique discret sont divergentes, leur exécution vont empêcher le modèle PROMELA de se stabiliser, \textit{i.e.} ce dernier ne verifiera pas la propriété LTL (\ref{eq:ltl:conv}). -\end{Proof} +\end{proof} % \begin{Corol}[Soundness wrt universall convergence property]\label{Theo:sound} @@ -282,7 +282,7 @@ Grace à~\Equ{eq:correct_retrieve} déjà prouvée, on peut conclure la preuve. \promelacomplete* -\begin{Proof} +\begin{proof} Pour chaque modele $\psi$ qui ne vérifie pas la propriété LTL (\ref{eq:ltl:conv}), il est immédiat de construire les itérations correpondantes du @@ -299,5 +299,5 @@ Grace à~\Equ{eq:correct_retrieve} déjà prouvée, on peut conclure la preuve. % continuously enabled leading to convenient available dates $D_{ji}$. % \end{itemize} % The simulated DDN does not stabilize and its iterations are divergent. - \end{Proof} + \end{proof} diff --git a/annexesccg.tex b/annexesccg.tex index 257f86c..bbfc12d 100644 --- a/annexesccg.tex +++ b/annexesccg.tex @@ -23,7 +23,7 @@ arcs dont ${\mathsf{N}}$ est soit l'extrémité, soit l'origine (et dans ce dern cas, les arcs sont des boucles sur ${\mathsf{N}}$). \end{lemma} -\begin{Proof} +\begin{proof} Supposons que $G(f^{\alpha})$ possède un arc de $j$ vers $i$ de signe $s$. Par définition, il existe un sommet $x\in\Bool^{{\mathsf{N}}-1}$ tel que $f^{\alpha}_{ij}(x)=s$, et puisque @@ -42,13 +42,13 @@ Ainsi $f_{ij}(x,\alpha)$ est égal à $s$. On a donc aussi $f^{\alpha}_{ij}(x)=s$. Ainsi $G(f^\alpha)$ possède un arc arc de $j$ vers $i$ de signe $s$. -\end{Proof} +\end{proof} \begin{lemma}\label{lemma:iso} Les graphes $\textsc{giu}(f^\alpha)$ et $\textsc{giu}(f)^\alpha$ sont isomorphes. \end{lemma} -\begin{Proof} +\begin{proof} Soit $h$ la bijection de $\Bool^{{\mathsf{N}}-1}$ vers $\Bool^{{\mathsf{N}}-1}\times \{\alpha\}$ définie par $h(x)=(x,\alpha)$ pour chaque $x\in\Bool^{{\mathsf{N}}-1}$. @@ -56,13 +56,13 @@ On voit facilement que $h$ permet de définir un isomorphisme entre $\textsc{giu}(f^\alpha)$ et $\textsc{giu}(f)^\alpha$: $\textsc{giu}(f^\alpha)$ possède un arc de $x$ vers $y$ si et seulement si $\textsc{giu}(f)^\alpha$ a un arc de $h(x)$ vers $h(y)$. -\end{Proof} +\end{proof} On peut alors prouver le théorème: \thAdrien* -\begin{Proof} +\begin{proof} La preuve se fait par induction sur ${\mathsf{N}}$. Soit $f$ une fonction de $\Bool^{\mathsf{N}}$ dans lui-même et qui vérifie les hypothèses du théorème. @@ -122,7 +122,7 @@ Puisque la valeur de $f_{\mathsf{N}}(x)$ on a $f_{\mathsf{N}}(x')=f_{\mathsf{N}}(x)=1\neq x'_{\mathsf{N}}$ (resp. $f_{\mathsf{N}}(y')=f_{\mathsf{N}}(y)=0\neq y'_{\mathsf{N}}$). Ainsi la condition ($*$) est établie, et le théorème est prouvé. -\end{Proof} +\end{proof} diff --git a/caracgeneralise.tex b/caracgeneralise.tex index 3014a6b..9ebc5d1 100644 --- a/caracgeneralise.tex +++ b/caracgeneralise.tex @@ -4,7 +4,7 @@ des itérations généralisées. \caractransitivegeneralise* -\begin{Proof} +\begin{proof} $\Longleftarrow$ Supposons que $\textsc{gig}(f)$ soit fortement connexe. Soient $(x,S)$ et $(x',S')$ deux points de $\mathcal{X}_g$ et $\varepsilon >0$. @@ -49,7 +49,7 @@ Pour tout entier naturel $t$, on a $G_{f_g}^t(x'',S'') \neq (x',S')$. Ainsi $G_{f_g}$ n'est pas transitive et par contraposée, on a la démonstration souhaitée. -\end{Proof} +\end{proof} Prouvons à présent le théorème suivant: @@ -57,7 +57,7 @@ Prouvons à présent le théorème suivant: \caracsubgeneralise* -\begin{Proof} +\begin{proof} Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$ telle que $G_{f_g}$ est transitive (\textit{i.e.} $f$ appartient à $\mathcal{T}$). Soit $(x,S) \in\mathcal{X}_g$ et $\varepsilon >0$. Pour @@ -82,7 +82,7 @@ Il est évident que $(x,\tilde S)$ s'obtient à partir de $(x,\tilde S)$ aprè $t_1+t_2$ itérations parallèles de $G_{f_g}$. Ainsi $(x,\tilde S)$ est un point périodique. Puisque $\tilde s_t$ est égal à $s_t$ pour $t0$. @@ -53,7 +53,7 @@ Pour tout entier naturel $t$, on a $G_{f_u}^t(x'',S'') \neq (x',S')$. Ainsi $G_{f_u}$ n'est pas transitive et par contraposée, on a la démonstration souhaitée. -\end{Proof} +\end{proof} Prouvons à présent le théorème suivant: @@ -63,7 +63,7 @@ Prouvons à présent le théorème suivant: \end{theorem} -\begin{Proof} +\begin{proof} Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$ telle que $G_{f_u}$ est transitive (\textit{i.e.} $f$ appartient à $\mathcal{T}$). Soit $(x,S) \in\mathcal{X}_u$ et $\varepsilon >0$. Pour @@ -88,7 +88,7 @@ Il est évident que $(x,\tilde S)$ s'obtient à partir de $(x,\tilde S)$ aprè $t_1+t_2$ itérations parallèles de $G_{f_u}$. Ainsi $(x,\tilde S)$ est un point périodique. Puisque $\tilde s_t$ est égal à $s_t$ pour $t