From c30b91ee116985e1082ece543aaf0f6b4c71247b Mon Sep 17 00:00:00 2001 From: couchot Date: Mon, 20 Jul 2015 14:44:39 +0200 Subject: [PATCH] r --- 15RairoGen.tex | 22 ++++-- annexePreuveDistribution.tex | 145 ++++++++++++++++++----------------- images/texput.log | 10 +-- main.tex | 18 +++-- 4 files changed, 110 insertions(+), 85 deletions(-) diff --git a/15RairoGen.tex b/15RairoGen.tex index 4c9a25b..d71c0d3 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -670,7 +670,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g \subfigure[$\textsc{giu}_{\{2\}}(h)$]{ \begin{minipage}{0.30\textwidth} \begin{center} - \includegraphics[height=4cm]{images/h2prng.pdf} + \includegraphics[height=4cm]{images/h2prng} \end{center} \end{minipage} \label{fig:h2prng} @@ -678,7 +678,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g \subfigure[$\textsc{giu}_{\{3\}}(h)$]{ \begin{minipage}{0.40\textwidth} \begin{center} - \includegraphics[height=4cm]{images/h3prng.pdf} + \includegraphics[height=4cm]{images/h3prng} \end{center} \end{minipage} \label{fig:h3prng} @@ -686,7 +686,7 @@ Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{g \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{ \begin{minipage}{0.40\textwidth} \begin{center} - \includegraphics[height=4cm]{images/h23prng.pdf} + \includegraphics[height=4cm]{images/h23prng} \end{center} \end{minipage} \label{fig:h23prng} @@ -720,7 +720,7 @@ Le dernier donnerait le comportement d'un générateur qui s'autoriserait \subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$} Le théorème suivant, similaire à celui dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$ -est prouvé en annexes~\ref{}. +est prouvé en annexes~\ref{anx:generateur}. \begin{theorem} La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur @@ -728,6 +728,18 @@ La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 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}_{\mathcal{b}}(f)$ + n'est pas fortement connexe. +\end{proof} diff --git a/annexePreuveDistribution.tex b/annexePreuveDistribution.tex index 878b317..f53e3b9 100644 --- a/annexePreuveDistribution.tex +++ b/annexePreuveDistribution.tex @@ -88,94 +88,99 @@ aussi. -\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} +Montrons que: +\begin{lemma} +Le graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ +est fortement connexe si et seulement si +la fonction $G_{f_u,\mathcal{P}}$ est topologiquement transitive sur +$(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$. +\end{lemma}\label{prop:trans} \begin{proof} -Suppose that $\Gamma_{\mathcal{P}}(f)$ is strongly connected. -Let $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v})) -\in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. -We will find a point $y$ in the open ball $\mathcal{B}(x,\varepsilon )$ and -$n_0 \in \mathds{N}$ such that $G_f^{n_0}(y)=\check{x}$: this strong transitivity -will imply the transitivity property. -We can suppose that $\varepsilon <1$ without loss of generality. - -Let us denote by $(E,(U,V))$ the elements of $y$. As -$y$ must be in $\mathcal{B}(x,\varepsilon)$ and $\varepsilon < 1$, -$E$ must be equal to $e$. Let $k=\lfloor \log_{10} (\varepsilon) \rfloor +1$. -$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ must be lower than -$\varepsilon$, so the $k$ first digits of the fractional part of -$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ are null. -Let $k_1$ the smallest integer such that, if $V^0=v^0$, ..., $V^{k_1}=v^{k_1}$, - $U^0=u^0$, ..., $U^{\sum_{l=0}^{k_1}V^l-1} = u^{\sum_{l=0}^{k_1}v^l-1}$. -Then $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))<\varepsilon$. -In other words, any $y$ of the form $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}), -(v^0, ..., v^{k_1}))$ is in $\mathcal{B}(x,\varepsilon)$. - -Let $y^0$ such a point and $z=G_f^{k_1}(y^0) = (e',(u',v'))$. $\Gamma_{\mathcal{P}}(f)$ -being strongly connected, there is a path between $e'$ and $\check{e}$. Denote -by $a_0, \hdots, a_{k_2}$ the edges visited by this path. We denote by -$V^{k_1}=|a_0|$ (number of terms in the finite sequence $a_1$), -$V^{k_1+1}=|a_1|$, ..., $V^{k_1+k_2}=|a_{k_2}|$, and by +Supposons tout d'abord que $G_{f_u,\mathcal{P}}$ fortement connexe. +Soit $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v})) +\in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ et $\varepsilon >0$. +On cherche un point $y$ dans une boule ouverte $\mathcal{B}(x,\varepsilon )$ +et un nombre +$n_0 \in \mathds{N}$ tels que $G_{f_u,\mathcal{P}}^{n_0}(y)=\check{x}$: +Cette transitivité forte entrainera la propriété de transitivité classique. +On peut supposer que $\varepsilon <1$ sans perte de généralité. + +Soit $(E,(U,V))$ les éléments de $y$. Comme +$y$ doit appartenir à $\mathcal{B}(x,\varepsilon)$ et $\varepsilon < 1$, +$E$ est égal à $e$. +Soit $k=\lfloor \log_{10} (\varepsilon) \rfloor +1$. +La distance $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ est inférieure à +$\varepsilon$: les $k$ premiers éléments de la partie décimale de +$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ sont nuls. +Soit $k_1$ le plus petit entier tel que, si $V^0=v^0$, ..., $V^{k_1}=v^{k_1}$, +alors $U^0=u^0$, ..., $U^{\sum_{l=0}^{k_1}V^l-1} = u^{\sum_{l=0}^{k_1}v^l-1}$. +Alors $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))<\varepsilon$. +En d'autres mots, chaque $y$ de la forme $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}), +(v^0, ..., v^{k_1}))$ est dans $\mathcal{B}(x,\varepsilon)$. + +Soit $y^0$ un tel point et $z=G_{f_u,\mathcal{P}}^{k_1}(y^0) = (e',(u',v'))$. +$G_{f_u,\mathcal{P}}$ étant fortement connexe, +il existe un chemin entre $e'$ et $\check{e}$. +Soit $a_0, \hdots, a_{k_2}$ les arêtes visitées le long de ce chemin. +On fixe $V^{k_1}=|a_0|$ +(le nombre de termes dans la séquence finie $a_1$), +$V^{k_1+1}=|a_1|$, ..., $V^{k_1+k_2}=|a_{k_2}|$, et $U^{k_1}=a_0^0$, $U^{k_1+1}=a_0^1$, ..., $U^{k_1+V_{k_1}-1}=a_0^{V_{k_1}-1}$, -$U^{k_1+V_{k_1}}=a_1^{0}$, $U^{k_1+V_{k_1}+1}=a_1^{1}$,... +$U^{k_1+V_{k_1}}=a_1^{0}$, $U^{k_1+V_{k_1}+1}=a_1^{1}$,\ldots -Let $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., +Soit $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},$ \linebreak $\check{u}^0, \check{u}^1, ...),(v^0, ..., v^{k_1},|a_0|, ..., - |a_{k_2}|,\check{v}^0, \check{v}^1, ...)))$. So $y\in \mathcal{B}(x,\varepsilon)$ - and $G_{f}^{k_1+k_2}(y)=\check{x}$. - + |a_{k_2}|,\check{v}^0, \check{v}^1, ...)))$. +Ainsi + $y\in \mathcal{B}(x,\varepsilon)$ + et $G_{f}^{k_1+k_2}(y)=\check{x}$. -Conversely, if $\Gamma_{\mathcal{P}}(f)$ is not strongly connected, then there are -2 vertices $e_1$ and $e_2$ such that there is no path between $e_1$ and $e_2$. -That is, it is impossible to find $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$ -and $n \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$ -cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transitive. +Réciproquement, si $G_{f_u,\mathcal{P}}$ n'est pas fortement connexe, +il y a donc deux n{\oe}uds +$e_1$ et $e_2$ sans chemins entre eux. +Il n'est ainsi pas possible de trouver un couple $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$ +et $n \mathds{N}$ tel que $G_{f_u,\mathcal{P}}^n(e,(u,v))_1=e_2$. +La boule ouverte $\mathcal{B}(e_2, 1/2)$ ne peut ainsi pas être atteinte +depuis n'importe quel voisins de $e_1$: +$G_{f_u,\mathcal{P}}$ n'est pas transitive. \end{proof} -We show now that, -\begin{prpstn} -If $\Gamma_{\mathcal{P}}(f)$ is strongly connected, then $G_f$ is -regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$. -\end{prpstn} +Montrons maintenant que +\begin{lemma} +Si $G_{f_u,\mathcal{P}}$ est fortement connexe, alors $G_{f_u,\mathcal{P}}$ est +régulière sur $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$. +\end{lemma} \begin{proof} -Let $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. -As in the proofs of Prop.~\ref{prop:trans}, let $k_1 \in \mathds{N}$ such -that +Soit $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ et $\varepsilon >0$. +Comme dans la preuve du lemme~\ref{prop:trans}, soit $k_1 \in \mathds{N}$ tel +que $$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \mid \right.$$ $$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\} \subset \mathcal{B}(x,\varepsilon),$$ -and $y=G_f^{k_1}(e,(u,v))$. $\Gamma_{\mathcal{P}}(f)$ being strongly connected, -there is at least a path from the Boolean state $y_1$ of $y$ and $e$. -Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path. -Then the point: +et $y=G_{f_u,\mathcal{P}}^{k_1}(e,(u,v))$. +$G_{f_u,\mathcal{P}}$ étant fortement connexe, +il existe au moins un chemin entre l'état booléen $y_1$ de $y$ et $e$. +Nommons $a_0, \hdots, a_{k_2}$ les arêtes d'un tel chemin. +Le point $$(e,((u^0, ..., u^{v^{k_1-1}},a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},u^0, ..., u^{v^{k_1-1}},$$ $$a_0^0, ...,a_{k_2}^{|a_{k_2}|}...),(v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,...))$$ -is a periodic point in the neighborhood $\mathcal{B}(x,\varepsilon)$ of $x$. +est un point périodique dans le voisinage $\mathcal{B}(x,\varepsilon)$ de $x$. \end{proof} -$G_f$ being topologically transitive and regular, we can thus conclude that -\begin{thrm} -The function $G_f$ is chaotic on $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ if -and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is strongly connected. -\end{thrm} +$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} + -\begin{crllr} - The pseudorandom number generator $\chi_{\textit{14Secrypt}}$ is not chaotic - on $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ for the negation function. -\end{crllr} -\begin{proof} - In this context, $\mathcal{P}$ is the singleton $\{b\}$. - If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach - its neighborhood and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected. - If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach itself - and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected. -\end{proof} diff --git a/images/texput.log b/images/texput.log index dfb78d3..9503c0c 100644 --- a/images/texput.log +++ b/images/texput.log @@ -1,4 +1,4 @@ -This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013/Debian) (format=pdflatex 2014.4.22) 1 JUL 2014 08:43 +This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2015/dev/Debian) (preloaded format=pdflatex 2015.4.24) 17 JUL 2015 16:13 entering extended mode restricted \write18 enabled. %&-line parsing enabled. @@ -11,10 +11,10 @@ End of file on the terminal! Here is how much of TeX's memory you used: - 3 strings out of 494999 - 105 string characters out of 6180228 - 46040 words of memory out of 5000000 - 3324 multiletter control sequences out of 15000+600000 + 3 strings out of 494991 + 113 string characters out of 6180055 + 46069 words of memory out of 5000000 + 3329 multiletter control sequences out of 15000+600000 3640 words of font info for 14 fonts, out of 8000000 for 9000 14 hyphenation exceptions out of 8191 0i,0n,0p,1b,6s stack positions out of 5000i,500n,10000p,200000b,80000s diff --git a/main.tex b/main.tex index 9713260..8a06e63 100644 --- a/main.tex +++ b/main.tex @@ -125,6 +125,7 @@ \newtheorem{theorem}{Théorème} \newtheorem{lemma}{Lemme} +\newtheorem{corollary}{Corollaire} \newtheorem*{xpl}{Exemple} \newtheorem*{Proof}{Preuve} \newtheorem{Def}{Définition} @@ -210,20 +211,25 @@ On montre qu'on a des résultats similaires. \chapter{Caractérisation des générateurs chaotiques} \input{15RairoGen} -\chapter{Fonctions dont les graphes +\chapter{Engendrer une classe de générateurs} + +\section{Fonctions dont les graphes $\textsc{giu}(f)$ $\textsc{gig}(f)$ sont fortement connexes} % Secrypt 14 -% TSI 2015 -\chapter{Quantifier l'écart par rapport à la distribution uniforme} + +\section{Quantifier l'écart par rapport à la distribution uniforme} %15 Rairo \part{Conclusion et Perspectives} + + + \JFC{Perspectives pour SDD->Promela} Among drawbacks of the method, one can argue that bounded delays is only realistic in practice for close systems. @@ -249,9 +255,11 @@ will then be stated. Ajouter lefait que le codede gray n'est pas optimal. On pourrait aussi travailler à établir un classement qui préserverait le fait que deux configurations voisines seraient représentées -par deux entiers voisins. +par deux entiers voisins. Par optimisation? - +\JFC{Perspectives pour les générateurs} : marcher ou sauter... comment on +pourrait étendre, ce que l'on a déjà, ce qu'il reste à faire. +% TSI 2015 -- 2.39.5