X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/eb86b87fcb8bd9aa66283fcea4d9efbe964179ff..d69000ebda300fc836232f34cebb88ddfce4ac98:/15RairoGen.tex diff --git a/15RairoGen.tex b/15RairoGen.tex index e4f8858..a950d85 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -16,7 +16,7 @@ Cette section présente une application directe de la théorie développée ci-a à la génération de nombres pseudo aléatoires. 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 distributionuniforme +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. @@ -46,8 +46,7 @@ $x\leftarrow{F_{f_u}(s,x)}$\; } return $x$\; %\end{scriptsize} -\caption{Algorithme de génération de nombres pseudo aléatoires -à l'aide de la fonction chaotique $G_f$} +\caption{PRNG basé sur les itérations unaires.} \label{CI Algorithm} \end{algorithm} @@ -64,38 +63,43 @@ Il retourne une nouvelle configuration $x$ en appliquant la fonction $F_{f_u}$ vue au chapitre~\ref{chap:carachaos} et correspondant à des itérations unaires. En interne, il exploite un algorithme de génération -de nombres pseudo aléatoires -\textit{Random}$(l)$. -Cet algorithme est utilisée dans notre générateur pour construire la longueur -de la stratégie ainsi que les éléments qui la composent. -Pratiquement, il retourne des entiers dans $\llbracket 1 ; l \rrbracket$ -selon une distributionuniforme et utilise -\textit{XORshift} qui est une classe de générateurs de -nombres pseudo aléatoires conçus par George Marsaglia. - - -L'algorithme \textit{XORshift} -exploite itérativement l'opérateur $\oplus$ -sur des nombres obtenus grâce à des decalages de bits. -Cet opérateur, défini dans $\Bool^{n}$, -applique la fonction \og xor \fg{} -aux bits de même rang de ses deux opérandes (\og opération bit à bit \fg{}). -Une instance de cette classe est donnée dans l'algorithme~\ref{XORshift} donné -ci-dessous. - -\begin{algorithm}[h] -%\SetLine -\KwIn{la configuration interne $z$ (un mot de 32-bit)} -\KwOut{$y$ (un mot de 32-bits)} -$z\leftarrow{z\oplus{(z\ll13)}}$\; -$z\leftarrow{z\oplus{(z\gg17)}}$\; -$z\leftarrow{z\oplus{(z\ll5)}}$\; -$y\leftarrow{z}$\; -return $y$\; -\medskip -\caption{Une boucle de l'algorithme de \textit{XORshift}} -\label{XORshift} -\end{algorithm} +de nombres pseudo aléatoires donné en paramètre. +Cela peut être n'importe quel PRNG (XORshift, Mersenne-Twister) dont la +sortie est uniformément distribuée. +Notre approche vise a donner des propriétés de chaos a ce générateur embarqué. + + +% \textit{Random}$(l)$. +% Cet algorithme est utilisée dans notre générateur pour construire la longueur +% de la stratégie ainsi que les éléments qui la composent. +% Pratiquement, il retourne des entiers dans $\llbracket 1 ; l \rrbracket$ +% selon une distribution uniforme et utilise +% \textit{XORshift} qui est une classe de générateurs de +% nombres pseudo aléatoires conçus par George Marsaglia. + + +% L'algorithme \textit{XORshift} +% exploite itérativement l'opérateur $\oplus$ +% sur des nombres obtenus grâce à des décalages de bits. +% Cet opérateur, défini dans $\Bool^{n}$, +% applique la fonction \og xor \fg{} +% aux bits de même rang de ses deux opérandes (\og opération bit à bit \fg{}). +% Une instance de cette classe est donnée dans l'algorithme~\ref{XORshift} donné +% ci-dessous. + +% \begin{algorithm}[h] +% %\SetLine +% \KwIn{la configuration interne $z$ (un mot de 32-bit)} +% \KwOut{$y$ (un mot de 32-bits)} +% $z\leftarrow{z\oplus{(z\ll13)}}$\; +% $z\leftarrow{z\oplus{(z\gg17)}}$\; +% $z\leftarrow{z\oplus{(z\ll5)}}$\; +% $y\leftarrow{z}$\; +% return $y$\; +% \medskip +% \caption{Une boucle de l'algorithme de \textit{XORshift}} +% \label{XORshift} +% \end{algorithm} Nous avons vu au chapitre~\ref{chap:carachaos} que @@ -118,8 +122,8 @@ si la propriété suivante est établie: $$\exists k \in \mathds{N}^\ast, \forall i,j \in \llbracket 1; n \rrbracket, M_{ij}^k>0.$$ On énonce enfin le théorème suivant liant les -vecteur de probabilite -et les chaines de Markov. +vecteur de probabilités +et les chaînes de Markov. @@ -128,11 +132,11 @@ et les chaines de Markov. Si $M$ est une matrice stochastique régulière, alors $M$ possède un unique vecteur stationnaire de probabilités $\pi$ ($\pi.M = \pi$). - De plus, si $\pi^0$ est un {vecteurDeProbabilite} + De plus, si $\pi^0$ est un {vecteur de probabilités} et si on définit la suite $(\pi^{k})^{k \in \Nats}$ par $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$ - alors la {chaineDeMarkov} $\pi^k$ + alors la {chaîne de Markov} $\pi^k$ converge vers $\pi$ lorsque $k$ tend vers l'infini. \end{theorem} @@ -146,8 +150,8 @@ et $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$. Leurs graphes d'interactions donnés en figure \ref{fig:g:inter} et \ref{fig:h:inter} vérifient les hypothèses du théorème~\ref{th:Adrien}. Leurs graphes d'itérations -sont donc fortement connexes, ce que l'on peut vérifier aux figures -\ref{fig:g:iter} et \ref{fig:h:iter}. +sont donc fortement connexes, ce que l'on peut vérifier aux figures~\ref{fig:g:iter} +et~\ref{fig:h:iter}. \textit{A priori}, ces deux fonctions pourraient être intégrées dans un générateur de nombres pseudo aléatoires. Montrons que ce n'est pas le cas pour $g$ et que cela l'est pour $h$. @@ -178,7 +182,8 @@ que cela l'est pour $h$. \end{minipage} \label{fig:h:iter} } \end{center} - \caption{Graphes d'itérations de fonctions booléennes dans $\Bool^2$} + \caption{Graphes des itérations unaires + de fonctions booléennes dans $\Bool^2$} \label{fig:xplgraphIter} \end{figure} @@ -228,7 +233,7 @@ Il est facile de vérifier que la matrice de transitions d'un tel processus est $M_g = \frac{1}{2} \check{M}_g$, où $\check{M}_g$ est la matrice d' adjacence donnée en -figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$. +figure~\ref{fig:g:incidence} (voir ci-après), et de manière similaire pour $M_h$. \begin{figure}[h] \begin{center} @@ -293,12 +298,14 @@ de valeurs soit suffisamment grand de sorte que le vecteur d’état de la chaîne de Markov ait une distribution suffisamment proche de la distribution uniforme. -On énnonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}. +On énonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}. -\begin{theorem} +\begin{theorem}\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$ définie comme dans le lemme précédent. + et $M$ une matrice $2^n\times 2^n$ + définie par + $M = \dfrac{1}{n} \check{M}$. 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 @@ -311,7 +318,7 @@ On énnonce directement le théorème suivant dont la preuve est donnée en anne On reprend le graphe d'interactions $\Gamma(f)$ donné en figure~\ref{fig:G} à la section~\ref{sec:11FCT}. On a vu qu'il y avait 520 fonctions $f$ non isomorphes de graphe d'interactions $\Gamma(f)$, -dont seulement 16 d'entre elles possédent une matrice doublement stochastique. +dont seulement 16 d'entre elles possèdent une matrice doublement stochastique. La figure~\ref{fig:listfonction} explicite ces 16 fonctions en définissant les images des éléments de la liste @@ -332,15 +339,21 @@ ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^n})$ -- autrement dit, où la déviation par rapport à la distribution uniforme -- est inférieure à $10^{-4}$. En prenant le max pour tous les $e_i$, on obtient une valeur pour - $b$. Ainsi, on a -$$ + $b$. +Ainsi, on a +\begin{equation} b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} \{ \min \{ t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4} \} \}. -$$ +\label{eq:mt:ex} +\end{equation} + +\noindent Par la suite, ce nombre sera appelé \emph{temps de mélange}. + + \begin{figure}%[h] \begin{center} @@ -426,8 +439,8 @@ L'expérience a montré notamment que toutes ces fonctions passent avec succès cette batterie de tests. Pour conclure cette section, on remarque que le générateur de nombres pseudo-aléatoires -a été prouvé chaotique pour $b=1$, \textit{i.e.}, lorqu'il y a une sortie pour chaque itération. -Ceci est difficilement compatible avec la volonté d'avoir une sortie uniformémement distribuée: +a été prouvé chaotique pour $b=1$, \textit{i.e.}, lorsqu'il y a une sortie pour chaque itération. +Ceci est difficilement compatible avec la volonté d'avoir une sortie uniformément distribuée: se rapprocher de cette distribution nécessite en effet un nombre plus élevé d'itérations $b$ entre chaque sortie. Par exemple, dans l'exemple précédent, il est nécessaire d'itérer au moins 42 fois entre chaque sortie pour suivre une loi uniforme à $10^{-4}$ près. @@ -438,7 +451,7 @@ est l'objectif de la section suivante. \section{Un PRNG basé sur des itérations unaires qui est chaotique } Cette section présente un espace métrique adapté au générateur de nombres pseudo-aléatoires -pésenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente +présenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente est chaotique sur cet espace. \subsection{Un espace $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ pour le PRNG de l'algorithme~\ref{CI Algorithm}} @@ -455,7 +468,7 @@ Dans l'algorithme~\ref{CI Algorithm}, $\mathsf{p}$ vaut 1 et $p_1=b$. -Cet algorithme peut être vu comme $b$ compostions de la function $F_{f_u}$. +Cet algorithme peut être vu comme $b$ compostions de la fonction $F_{f_u}$. Ceci peut cependant se généraliser à $p_i$, $p_i \in \mathcal{P}$, compositions fonctionnelles de $F_{f_u}$. Ainsi, pour chaque $p_i \in \mathcal{P}$, on construit la fonction @@ -479,7 +492,7 @@ Le second élément est aussi une paire $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats La suite $(v^k)_{k \in \Nats}$ définit combien d'itérations sont exécutées au temps $k$ entre deux sorties. La séquence $(u^k)_{k \in \Nats}$ définit quel élément est modifié (toujours au temps $k$). -Définissons la fonction de décallage $\Sigma$ pour chaque élément de $\mathds{S}_{\mathsf{N},\mathcal{P}}$. +Définissons la fonction de décalage $\Sigma$ pour chaque élément de $\mathds{S}_{\mathsf{N},\mathcal{P}}$. $$\begin{array}{cccc} \Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow &\mathds{S}_{\mathsf{N},\mathcal{P}} \\ @@ -487,7 +500,7 @@ $$\begin{array}{cccc} \end{array} $$ En d'autres termes, $\Sigma$ reçoit deux suites $u$ et $v$ et -effectue $v^0$ décallage vers la droite sur la première et un décallage vers la droite +effectue $v^0$ décalage vers la droite sur la première et un décalage vers la droite sur la seconde. @@ -517,45 +530,76 @@ $\mathcal{X}_{\mathsf{N},\mathcal{P}} = \mathds{B}^\mathsf{N} \times \mathds{S}_ où $s=(u,v)$ et $\check{s}=(\check{u},\check{v})$ sont dans $ \mathds{S}_{\mathsf{N},\mathcal{P}} = \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. \begin{itemize} -\item $e$ et $\check{e}$ sont des entiers appartenant à $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. The Hamming distance -on their binary decomposition, that is, the number of dissimilar binary digits, constitutes the integral -part of $d(X,\check{X})$. -\item The fractional part is constituted by the differences between $v^0$ and $\check{v}^0$, followed by the differences -between finite sequences $u^0, u^1, \hdots, u^{v^0-1}$ and $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$, followed by - differences between $v^1$ and $\check{v}^1$, followed by the differences -between $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ and $\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc. -More precisely, let $p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ and $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$. +\item $e$ et $\check{e}$ sont des entiers appartenant à $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. +La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ sur entre les +décompositions binaires de $e$ et de $\check{e}$ (\textit{i.e.}, le +le nombre de bits qu'elles ont de différent) constitue +la partie entière de $d(X,\check{X})$. +\item la partie décimale est construite à partir des différences entre +$v^0$ et $\check{v}^0$, suivie des différences entre les séquences finies +$u^0, u^1, \hdots, u^{v^0-1}$ et $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$, suivie par les différences entre $v^1$ et $\check{v}^1$, +suivie par les différences entre $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ et +$\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc. + +Plus précisément, soit +$p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ et +$n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$. \begin{itemize} -\item The $p$ first digits of $d(x,\check{x})$ is $|v^0-\check{v}^0|$ written in decimal numeration (and with $p$ digits). -\item The next $n\times \max{(\mathcal{P})}$ digits aim at measuring how much $u^0, u^1, \hdots, u^{v^0-1}$ differs from $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. The $n$ first -digits are $|u^0-\check{u}^0|$. They are followed by -$|u^1-\check{u}^1|$ written with $n$ digits, etc. +\item Les $p$ premiers éléments de $d(x,\check{x})$ sont $|v^0-\check{v}^0|$ + écrits en base 10 et sur $p$ indices; +\item les $n\times \max{(\mathcal{P})}$ éléments suivants servent + à évaluer de combien $u^0, u^1, \hdots, u^{v^0-1}$ diffère de + $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. + Les $n$ premiers éléments sont $|u^0-\check{u}^0|$. Il sont suivis de +$|u^1-\check{u}^1|$ écrits à l'aide de $n$ éléments, etc. \begin{itemize} -\item If -$v^0=\check{v}^0$, then the process is continued until $|u^{v^0-1}-\check{u}^{\check{v}^0-1}|$ and the fractional -part of $d(X,\check{X})$ is completed by 0's until reaching -$p+n\times \max{(\mathcal{P})}$ digits. -\item If $v^0<\check{v}^0$, then the $ \max{(\mathcal{P})}$ blocs of $n$ -digits are $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$, -$\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digits), followed by 0's if required. -\item The case $v^0>\check{v}^0$ is dealt similarly. +\item Si +$v^0=\check{v}^0$, +alors le processus se continue jusqu'à $|u^{v^0-1}-\check{u}^{\check{v}^0-1}|$ et la +partie décimale de $d(X,\check{X})$ est complétée par des 0 +jusqu'à atteindre +$p+n\times \max{(\mathcal{P})}$ éléments. +\item Si $v^0<\check{v}^0$, alors les $ \max{(\mathcal{P})}$ blocs de $n$ +éléments sont $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$, +$\check{u}^{v^0}$ (sur $n$ éléments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ éléments), suivi par des 0, si besoin. +\item Le cas $v^0>\check{v}^0$ est similaire, et donc omis \end{itemize} -\item The next $p$ digits are $|v^1-\check{v}^1|$, etc. +\item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc. \end{itemize} \end{itemize} +La fonction $d$ peut se formaliser comme suit: +$$d(x,\check{x})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})+d_{\mathds{B}^\mathsf{N}}(e,\check{e}),$$ +où: % $p=\max \mathcal{P}$ and: +\begin{itemize} +\item $d_{\mathds{B}^\mathsf{N}}$ est la distance de Hamming, +\item $\forall s=(u,v), \check{s}=(\check{u},\check{v}) \in \mathcal{S}_{\mathsf{N},\mathcal{P}}$,\newline +$$\begin{array}{rcl} + d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) &= & + \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} + \bigg(|v^k - \check{v}^k| \\ + & & + \left| \sum_{l=0}^{v^k-1} + \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{(l+1)n}} - + \sum_{l=0}^{\check{v}^k-1} + \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{(l+1)n}} \right| \bigg) +\end{array} +$$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.$$ +\end{itemize} + \begin{xpl} -Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=3$), and that +On considère par exemple +$\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ ($\mathsf{p}$ vaut ainsi $3$), +et $s=\left\{ \begin{array}{l} u=\underline{6,} ~ \underline{11,5}, ...\\ v=1,2,... \end{array} \right.$ -while +avec $\check{s}=\left\{ \begin{array}{l} \check{u}=\underline{6,4} ~ \underline{1}, ...\\ @@ -563,68 +607,152 @@ $\check{s}=\left\{ \end{array} \right.$. -So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$ -Indeed, the $p=2$ first digits are 01, as $|v^0-\check{v}^0|=1$, -and we use $p$ digits to code this difference ($\mathcal{P}$ being $\{1,2,11\}$, this difference can be equal to 10). We then take the $v^0=1$ first terms of $u$, each term being coded in $n=2$ digits, that is, 06. As we can iterate -at most $\max{(\mathcal{P})}$ times, we must complete this -value by some 0's in such a way that the obtained result -has $n\times \max{(\mathcal{P})}=22$ digits, that is: -0600000000000000000000. Similarly, the $\check{v}^0=2$ first -terms in $\check{u}$ are represented by 0604000000000000000000, and the absolute value of their -difference is equal to 0004000000000000000000. These digits are concatenated to 01, and -we start again with the remainder of the sequences. +Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$ +En effet, les $p=2$ premiers éléments sont 01, c'est-à-dire +$|v^0-\check{v}^0|=1$, +et on utilise $p$ éléments pour représenter cette différence +(Comme $\mathcal{P}=\{1,2,11\}$, cette différence peut valoir 10). +On prend alors le $v^0=1$ premier terme de $u$, +chaque terme étant codé sur $n=2$ éléments, soit 06. +Comme on itère au plus $\max{(\mathcal{P})}$ fois, +on complète cette valeur par des 0 de sorte que +la chaîne obtenue a $n\times \max{(\mathcal{P})}=22$ éléments, soit: +0600000000000000000000. +De manière similaire, les $\check{v}^0=2$ premiers +termes de $\check{u}$ sont représentés par +0604000000000000000000. +LA valeur absolue de leur différence est égale à +0004000000000000000000. +Ces éléments sont concaténés avec 01. On peut construire alors le reste de +la séquence. \end{xpl} \begin{xpl} -Consider now that $\mathsf{N}=9$, and $\mathcal{P}=\{2,7\}$, and that - -$s=\left\{ +On considère à présent que $\mathsf{N}=9$, que $\mathcal{P}=\{2,7\}$ et que +$$s=\left\{ \begin{array}{l} u=\underline{6,7,} ~ \underline{4,2,} ...\\ v=2,2,... \end{array} -\right.$ -while -$\check{s}=\left\{ +\right.$$ +avec +$$\check{s}=\left\{ \begin{array}{l} \check{u}=\underline{4, 9, 6, 3, 6, 6, 7,} ~ \underline{9, 8}, ...\\ \check{v}=7,2,... \end{array} -\right.$ +\right. +$$ -So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, as $|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$, -and $|9800000-4200000| = 5600000$. +Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, +puisque +$|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$, +et $|9800000-4200000| = 5600000$. \end{xpl} -$d$ can be more rigorously written as follows: -$$d(x,\check{x})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})+d_{\mathds{B}^\mathsf{N}}(e,\check{e}),$$ -where: % $p=\max \mathcal{P}$ and: +On a la proposition suivante, qui est démontrée en annexes~\ref{anx:generateur}. +\begin{lemma} +$d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. +\end{lemma} + + +\subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant $\textsc{giu}(f)$} + +A partir de $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$, on +définit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suivante: \begin{itemize} -\item $d_{\mathds{B}^\mathsf{N}}$ is the Hamming distance, -\item $\forall s=(u,v), \check{s}=(\check{u},\check{v}) \in \mathcal{S}_{\mathsf{N},\mathcal{P}}$,\newline -$$\begin{array}{rcl} - d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) &= & - \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} - \bigg(|v^k - \check{v}^k| \\ - & & + \left| \sum_{l=0}^{v^k-1} - \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{(l+1)n}} - - \sum_{l=0}^{\check{v}^k-1} - \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{(l+1)n}} \right| \bigg) -\end{array} -$$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.$$ +\item les n{\oe}uds sont les $2^\mathsf{N}$ configurations de $\mathds{B}^\mathsf{N}$, +%\item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples +% having their elements in $\llbracket 1, \mathsf{N} \rrbracket $. +\item il y a un arc libellé $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ entre les n{\oe}uds $x$ et $y$ si et seulement si $p_i$ est un élément de +$\mathcal{P}$ (\textit{i.e.}, on peut itérer $p_i$ fois), +chaque $u_k$ de la suite appartient à $[\mathsf{N}]$ et +$y=F_{f_u,p_i} (x, (u_0, \hdots, u_{p_i-1})) $. \end{itemize} +Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{giu}(f)$. -Let us show that, -\begin{prpstn} -$d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. -\end{prpstn} -\subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant $\textsc{giu}(f)$} + +\begin{figure}%[t] + \begin{center} + \subfigure[$\textsc{giu}_{\{2\}}(h)$]{ + \begin{minipage}{0.30\textwidth} + \begin{center} + \includegraphics[height=4cm]{images/h2prng} + \end{center} + \end{minipage} + \label{fig:h2prng} + } + \subfigure[$\textsc{giu}_{\{3\}}(h)$]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[height=4cm]{images/h3prng} + \end{center} + \end{minipage} + \label{fig:h3prng} + } + \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[height=4cm]{images/h23prng} + \end{center} + \end{minipage} + \label{fig:h23prng} + } + + \end{center} + \caption{Graphes d'itérations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$} + %\label{fig:xplgraphIter} + \end{figure} + + + + +\begin{xpl} +On reprend l'exemple où $\mathsf{N}=2$ et +$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ déjà détaillé +à la section~\ref{sub:prng:unif}. + +Le graphe $\textsc{giu}_{\{1\}}(h)$ a déjà été donné à la figure~\ref{fig:h:iter}. +Les graphes $\textsc{giu}_{\{2\}}(h)$, $\textsc{giu}_{\{3\}}(h)$ et +$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnés aux figure~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}. +Le premier (respectivement le second) +illustre le comportement du générateur lorsque qu'on itère exactement +2 fois (resp. 3 fois) puis qu'on affiche le résultat. +Le dernier donnerait le comportement d'un générateur qui s'autoriserait +à itérer en interne systématiquement 2 ou trois fois avant de retourner un résultat. + +\end{xpl} + \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{anx:generateur}. + +\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} +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} + +