From eb86b87fcb8bd9aa66283fcea4d9efbe964179ff Mon Sep 17 00:00:00 2001 From: =?utf8?q?Jean-Fran=C3=A7ois=20Couchot?= Date: Thu, 16 Jul 2015 13:58:16 +0200 Subject: [PATCH] ajout de fichiers + 15Rairo --- 15RairoGen.tex | 451 ++++++++++++++++++++++++----------- annexePreuveDistribution.tex | 57 +++++ annexePreuvePRNGchotique.tex | 328 +++++++++++++++++++++++++ main.tex | 8 +- 4 files changed, 700 insertions(+), 144 deletions(-) create mode 100644 annexePreuveDistribution.tex create mode 100644 annexePreuvePRNGchotique.tex diff --git a/15RairoGen.tex b/15RairoGen.tex index f2b9243..e4f8858 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -6,9 +6,8 @@ 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. Enfin, un bon générateur aléatoire se doit de -fournir des nombres selon une {distributionuniforme} -La suite de ce document donnera, -dans le cas où le graphe d'itérations est fortement connexe, +fournir des nombres selon une distribution uniforme +La suite de ce document donnera une condition nécessaire est suffisante pour que cette propriété soit satisfaite. @@ -24,14 +23,12 @@ L'approche est évaluée dans la dernière section. \JFC{plan à revoir} -\subsection{ Générateur de nombres pseudo aléatoires basé sur le chaos}\label{sub:prng:algo} +\section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo} -On peut penser à construire un générateur de nombres pseudo -aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous. \begin{algorithm}[h] %\begin{scriptsize} @@ -39,13 +36,13 @@ aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous. une configuration initiale $x^0$ ($n$ bits)} \KwOut{une configuration $x$ ($n$ bits)} $x\leftarrow x^0$\; -$k\leftarrow b + \textit{Random}(b+1)$\; +$k\leftarrow b $\; %$k\leftarrow b + \textit{XORshift}(b+1)$\; -\For{$i=0,\dots,k-1$} +\For{$i=1,\dots,k$} { $s\leftarrow{\textit{Random}(n)}$\; %$s\leftarrow{\textit{XORshift}(n)}$\; -$x\leftarrow{F_f(s,x)}$\; +$x\leftarrow{F_{f_u}(s,x)}$\; } return $x$\; %\end{scriptsize} @@ -54,11 +51,18 @@ return $x$\; \label{CI Algorithm} \end{algorithm} +\subsection{Algorithme d'un générateur} +On peut penser à construire un générateur de nombres pseudo +aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous. + Celui-ci prend en entrée: une fonction $f$; un entier $b$, qui assure que le nombre d'itérations -est compris entre $b+1 $ et $2b+1$ et une configuration initiale $x^0$. -Il retourne une nouvelle configuration $x$. +est compris entre $b+1 $ et $2b+1$ (et donc supérieur à $b$) +et une configuration initiale $x^0$. +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)$. @@ -67,12 +71,8 @@ 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 -très rapides conçus par George Marsaglia. +nombres pseudo aléatoires conçus par George Marsaglia. -% L'algorithme \textit{XORshift} exploite itérativement -% la fonction \og {xor}\fg{} $\oplus$ (cf. glossaire) -% sur des nombres obtenus grâce à des pl{decalageDeBits} (cf. glossaire). L'algorithme \textit{XORshift} exploite itérativement l'opérateur $\oplus$ @@ -98,13 +98,13 @@ return $y$\; \end{algorithm} - -Il reste à instancier une fonction $f$ dans -l'algorithme~\ref{CI Algorithm} -en adéquation avec l'approche développée -en section~\ref{sec:sccg}. -La section suivante montre comment l'uniformité de la distribution a -contraint cette instanciation. +Nous avons vu au chapitre~\ref{chap:carachaos} que +$G_{f_u}$ est chaotique dans l'espace $\mathcal{X}_u$ +si et seulement le graphe d'itérations $\textsc{giu}(f)$ +doit être fortement connexe. +Pour $b=1$, l'algorithme itère la fonction $F_{f_u}$. +Regardons comment l'uniformité de la distribution a +contraint la fonction. \subsection{Un générateur à sortie uniformément distribuée}\label{sub:prng:unif} @@ -118,12 +118,13 @@ 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 -vecteurDeProbabilite -et les chaineDeMarkov: +vecteur de probabilite +et les chaines de Markov. -\begin{Theo}\label{th} + +\begin{theorem}\label{th} Si $M$ est une matrice stochastique régulière, alors $M$ possède un unique vecteur stationnaire de probabilités $\pi$ ($\pi.M = \pi$). @@ -133,7 +134,7 @@ et les chaineDeMarkov: $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$ alors la {chaineDeMarkov} $\pi^k$ converge vers $\pi$ lorsque $k$ tend vers l'infini. -\end{Theo} +\end{theorem} Montrons sur un exemple jouet à deux éléments @@ -145,29 +146,93 @@ 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 a pu déjà vérifier aux figures +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$. + + + + + + + +\begin{figure}%[t] + \begin{center} + \subfigure[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[height=4cm]{images/g.pdf} + \end{center} + \end{minipage} + \label{fig:g:iter} + } + \subfigure[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[height=4cm]{images/h.pdf} + \end{center} + \end{minipage} + \label{fig:h:iter} + } \end{center} + \caption{Graphes d'itérations de fonctions booléennes dans $\Bool^2$} + \label{fig:xplgraphIter} + \end{figure} + + + + + + + + + +\begin{figure}%[t] + \begin{center} + \subfigure[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[height=3cm]{images/gp.pdf} + \end{center} + \end{minipage} + \label{fig:g:inter} + } + \subfigure[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[height=3cm]{images/hp.pdf} + \end{center} + \end{minipage} + \label{fig:h:inter} + } \end{center} + \caption{Graphes d'interactions de fonctions booléennes dans $\Bool^2$} + \label{fig:xplgraphInter} + \end{figure} + + + + + + Comme le générateur \textit{Random} possède une sortie uniformément distribuée, la stratégie est uniforme sur $\llbracket 1, 2 \rrbracket$, et donc, -pour tout sommet de $\Gamma(g)$ et de $\Gamma(h)$, +pour tout sommet de $\textsc{giu}(g)$ et de $\textsc{giu}(h)$, chaque arc sortant de ce sommet a, parmi l'ensemble des arcs sortant de ce sommet, une probabilité $1/2$ d’être celui qui sera traversé. -En d'autres mots, $\Gamma(g)$ est le graphe orienté d'une chaîne de Markov. -Il est facile de vérifier que la {matriceDeTransitions} +En d'autres mots, $\textsc{giu}(g)$ est le graphe orienté d'une chaîne de Markov. +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 {matriceDAdjacence} donnée en +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$. \begin{figure}[h] \begin{center} - \subfloat[$\check{M}_g $.]{ + \subfigure[$\check{M}_g $.]{ \begin{minipage}{0.25\textwidth} \begin{center} % \vspace{-3cm} @@ -184,7 +249,7 @@ figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$. \end{minipage} \label{fig:g:incidence} } - \subfloat[$\check{M}_h $.]{ + \subfigure[$\check{M}_h $.]{ \begin{minipage}{0.25\textwidth} \begin{center} $\left( @@ -228,71 +293,24 @@ 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}. -Considérons le lemme technique suivant: -\begin{Lemma}\label{lem:stoc} -Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\Gamma(f)$, et $M$ la matrice -$2^n\times 2^n$ définie par -$M = \frac{1}{n}\check{M}$. -Alors $M$ est une matrice stochastique régulière si et seulement si -$\Gamma(f)$ est fortement connexe. -\end{Lemma} - -\begin{Proof} -On remarque tout d'abord que $M$ -est une matrice stochastique par construction. -Supposons $M$ régulière. -Il existe donc $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket -1; 2^n \rrbracket$. L'inégalité $\check{M}_{ij}^k>0$ est alors établie. -Puisque $\check{M}_{ij}^k$ est le nombre de chemins de $i$ à $j$ de longueur $k$ -dans $\Gamma(f)$ et puisque ce nombre est positif, alors -$\Gamma(f)$ est fortement connexe. - -Réciproquement si $\Gamma(f)$ -est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut être construit pour atteindre $j$ depuis $i$ en au plus $2^n$ étapes. -Il existe donc -$k_{ij} \in \llbracket 1, 2^n \rrbracket$ tels que $\check{M}_{ij}^{k_{ij}}>0$. -Comme tous les multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que -$\check{M}_{ij}^{l\times k_{ij}}>0$, -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{Theo} - Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son +\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 $\Gamma(f)$ est fortement connexe, alors + 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{Theo} -\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}). - Soit $\pi$ défini par - $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$. - On a $\pi M = \pi$ si et seulement si - la somme des valeurs de chaque colonne de $M$ est 1, - \textit{i.e.} si et seulement si - $M$ est doublement stochastique. -\end{Proof} - - -\subsection{Expérimentations} - -On considère le graphe d'interactions $G(f)$ donné en figure~\ref{fig:G}. -Il vérifie le théorème~\ref{th:Adrien}: -toutes les fonctions $f$ possédant un tel graphe d'interactions -ont un graphe d'itérations $\Gamma(f)$ fortement connexe. -Pratiquement, un algorithme simple de satisfaction de contraintes -a trouvé 520 fonctions $f$ non isomorphes de graphe d'interactions $G(f)$, +\end{theorem} + + +\subsection{Quelques exemples} + +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. La figure~\ref{fig:listfonction} explicite ces 16 fonctions en @@ -306,7 +324,7 @@ Soit $e_i$ le $i^{\textrm{ème}}$ vecteur la base canonique de $\R^{2^{n}}$. Chacun des éléments $v_j$, $1 \le j \le 2^n$, du vecteur $e_i M_f^t$ représente la probabilité d'être dans la configuration $j$ après $t$ étapes du processus de Markov -associé à $\Gamma(f)$ en partant de la configuration $i$. +associé à $\textsc{giu}(f)$ en partant de la configuration $i$. Le nombre $\min \{ t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4} \}$ représente le plus petit nombre d'itérations où la distance de @@ -326,7 +344,7 @@ $$ \begin{figure}%[h] \begin{center} - \subfloat[Graphe d'interactions]{ + \subfigure[Graphe d'interactions]{ \begin{minipage}{0.20\textwidth} \begin{center} \includegraphics[width=3.5cm]{images/Gi.pdf} @@ -334,7 +352,7 @@ $$ \end{minipage} \label{fig:G} }\hfill - \subfloat[Fonctions doublement stochastiques]{ + \subfigure[Fonctions doublement stochastiques]{ \begin{minipage}{0.75\textwidth} \begin{scriptsize} \begin{center} @@ -404,58 +422,209 @@ La qualité des séquences aléatoires a été évaluée à travers la suite de tests statistiques développée pour les générateurs de nombres pseudo aléatoires par le \emph{National Institute of Standards and Technology} (NIST). -% Pour les 15 tests, le seuil $\alpha$ est fixé à $1\%$: -% une valeur -% qui est plus grande que $1\%$ signifie -% que la chaîne est considérée comme aléatoire avec une confiance de $99\%$. -% Le tableau~\ref{fig:TEST} donne une vision synthétique de toutes -% les expérimentations. 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: +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. +Montrer les sous-séquences de suites chaotiques ainsi générées demeurent chaotiques +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 +est chaotique sur cet espace. +\subsection{Un espace $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ pour le PRNG de l'algorithme~\ref{CI Algorithm}} -% \begin{table}[th] -% \begin{scriptsize} -% \begin{tabular}{|*{17}{c|}} -% \hline -% {Propriété}& $\mathcal{F}_{1}$ &$\mathcal{F}_{2}$ &$\mathcal{F}_{3}$ &$\mathcal{F}_{4}$ &$\mathcal{F}_{5}$ &$\mathcal{F}_{6}$ &$\mathcal{F}_{7}$ &$\mathcal{F}_{8}$ &$\mathcal{F}_{9}$ &$\mathcal{F}_{10}$ &$\mathcal{F}_{11}$ &$\mathcal{F}_{12}$ &$\mathcal{F}_{13}$ &$\mathcal{F}_{14}$ &$\mathcal{F}_{15}$ &$\mathcal{F}_{16}$ \\ -% \hline -% Fréquence &77.9 &15.4 &83.4 &59.6 &16.3 &38.4 &20.2 &29.0 &77.9 &21.3 &65.8 &85.1 &51.4 &35.0 &77.9 &92.4 \\ -% \hline -% Fréquence / bloc &88.3 &36.7 &43.7 &81.7 &79.8 &5.9 &19.2 &2.7 &98.8 &1.0 &21.3 &63.7 &1.4 &7.6 &99.1 &33.5 \\ -% \hline -% Somme cummulée &76.4 &86.6 &8.7 &66.7 &2.2 &52.6 &20.8 &80.4 &9.8 &54.0 &73.6 &80.1 &60.7 &79.7 &76.0 &44.7 \\ -% \hline -% Exécution &5.2 &41.9 &59.6 &89.8 &23.7 &76.0 &77.9 &79.8 &45.6 &59.6 &89.8 &2.4 &96.4 &10.9 &72.0 &11.5 \\ -% \hline -% Longue exécution &21.3 &93.6 &69.9 &23.7 &33.5 &30.4 &41.9 &43.7 &30.4 &17.2 &41.9 &51.4 &59.6 &65.8 &11.5 &61.6 \\ -% \hline -% Rang &1.0 &41.9 &35.0 &45.6 &51.4 &20.2 &31.9 &83.4 &89.8 &38.4 &61.6 &4.0 &21.3 &69.9 &47.5 &95.6 \\ -% \hline -% Fourrier Rapide &40.1 &92.4 &97.8 &86.8 &43.7 &38.4 &76.0 &57.5 &36.7 &35.0 &55.4 &57.5 &86.8 &76.0 &31.9 &7.6 \\ -% \hline -% Sans superposition &49.0 &45.7 &50.5 &51.0 &48.8 &51.2 &51.6 &50.9 &50.9 &48.8 &45.5 &47.3 &47.0 &49.2 &48.6 &46.4 \\ -% \hline -% Avec Superposition &27.6 &10.9 &53.4 &61.6 &16.3 &2.7 &59.6 &94.6 &88.3 &55.4 &76.0 &23.7 &47.5 &91.1 &65.8 &81.7 \\ -% \hline -% Universelle &24.9 &35.0 &72.0 &51.4 &20.2 &74.0 &40.1 &23.7 &9.1 &72.0 &4.9 &13.7 &14.5 &1.8 &93.6 &65.8 \\ -% \hline -% Entropie approchée &33.5 &57.5 &65.8 &53.4 &26.2 &98.3 &53.4 &63.7 &38.4 &6.7 &53.4 &19.2 &20.2 &27.6 &67.9 &88.3 \\ -% \hline -% Suite aléatoire &29.8 &35.7 &40.9 &36.3 &54.8 &50.8 &43.5 &46.0 &39.1 &40.8 &29.6 &42.0 &34.8 &33.8 &63.0 &46.3 \\ -% \hline -% Suite aléatoire variante &32.2 &40.2 &23.0 &39.6 &47.5 &37.2 &56.9 &54.6 &53.3 &31.5 &23.0 &38.1 &52.3 &57.1 &47.7 &40.8 \\ -% \hline -% Série &56.9 &58.5 &70.4 &73.2 &31.3 &45.9 &60.8 &39.9 &57.7 &21.2 &6.4 &15.6 &44.7 &31.4 &71.7 &49.1 \\ -% \hline -% Complexité linéaire &24.9 &23.7 &96.4 &61.6 &83.4 &49.4 &49.4 &18.2 &3.5 &76.0 &24.9 &97.2 &38.4 &38.4 &1.1 &8.6 \\ -% \hline -% \end{tabular} -% \end{scriptsize} -% \caption{Test de NIST réalisé sur des instances de générateurs}\label{fig:TEST} -% \end{table} +Introduisons tout d'abord $\mathcal{P} \subset \mathds{N}$ un ensemble fini non vide de cardinalité +$\mathsf{p} \in \mathds{N}^\ast$. +Intuitivement, c'est le nombre d'itérations qu'il est autorisé de faire. +On ordonne les $\mathsf{p}$ éléments de $\mathcal{P}$ comme suit: +$\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$ +et $p_1< p_2< \hdots < p_\mathsf{p}$. +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}$. +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 +$F_{{f_u},p_i} : \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^{p_i} +\rightarrow \mathds{B}^\mathsf{N}$ définie par + +$$ +F_{f_u,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1})) \mapsto +F_{f_u}(\hdots (F_{f_u}(F_{f_u}(x,u^0), u^1), \hdots), u^{p_i-1}). +$$ + + +on construit l'espace + $\mathcal{X}_{\mathsf{N},\mathcal{P}}= \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, où +$\mathds{S}_{\mathsf{N},\mathcal{P}}= +\llbracket 1, \mathsf{N} \rrbracket^{\Nats}\times +\mathcal{P}^{\Nats}$. +Chaque élément de l'espace est une paire où le premier élément est +un $\mathsf{N}$-uplet de $\Bool^{\mathsf{N}}$ (comme dans $\mathcal{X}_u$). +Le second élément est aussi une paire $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats})$ de suites infinies. +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}}$. +$$\begin{array}{cccc} +\Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow +&\mathds{S}_{\mathsf{N},\mathcal{P}} \\ +& \left((u^k)_{k \in \mathds{N}},(v^k)_{k \in \mathds{N}}\right) & \longmapsto & \left(\sigma^{v^0}\left((u^k)_{k \in \mathds{N}}\right),\sigma\left((v^k)_{k \in \mathds{N}}\right)\right). +\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 +sur la seconde. + + +Ainsi, les sorties $(y^0, y^1, \hdots )$ produites par le générateur détaillé dans +l'algorithme~\ref{CI Algorithm} +sont les premiers composants des itérations $X^0 = (x^0, (u,v))$ et $\forall n \in \mathds{N}, +X^{n+1} = G_{f_u,\mathcal{P}}(X^n)$ dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ où +$G_{f_u,\mathcal{P}}$ est définie par: + + + + +\begin{equation} +\begin{array}{cccc} +G_{f_u,\mathcal{P}} :& \mathcal{X}_{\mathsf{N},\mathcal{P}} & \longrightarrow & \mathcal{X}_{\mathsf{N},\mathcal{P}}\\ + & (e,(u,v)) & \longmapsto & \left( F_{f,v^0}\left( e, (u^0, \hdots, u^{v^0-1}\right), \Sigma (u,v) \right) . +\end{array} +\end{equation} + + + +\subsection{Une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$} + +On définit la fonction $d$ sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ comme suit: +Soit $x=(e,s)$ et $\check{x}=(\check{e},\check{s})$ dans +$\mathcal{X}_{\mathsf{N},\mathcal{P}} = \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}} $, +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$. +\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. +\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. +\end{itemize} +\item The next $p$ digits are $|v^1-\check{v}^1|$, etc. +\end{itemize} +\end{itemize} + + + + +\begin{xpl} +Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=3$), and that +$s=\left\{ +\begin{array}{l} +u=\underline{6,} ~ \underline{11,5}, ...\\ +v=1,2,... +\end{array} +\right.$ +while +$\check{s}=\left\{ +\begin{array}{l} +\check{u}=\underline{6,4} ~ \underline{1}, ...\\ +\check{v}=2,1,... +\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. +\end{xpl} + + +\begin{xpl} +Consider now that $\mathsf{N}=9$, and $\mathcal{P}=\{2,7\}$, and that + +$s=\left\{ +\begin{array}{l} +u=\underline{6,7,} ~ \underline{4,2,} ...\\ +v=2,2,... +\end{array} +\right.$ +while +$\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.$ + +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$. +\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: +\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)}.$$ +\end{itemize} + + +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)$} + +\subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$} + diff --git a/annexePreuveDistribution.tex b/annexePreuveDistribution.tex new file mode 100644 index 0000000..7a05f11 --- /dev/null +++ b/annexePreuveDistribution.tex @@ -0,0 +1,57 @@ + +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 +$2^n\times 2^n$ définie par +$M = \frac{1}{n}\check{M}$. +Alors $M$ est une matrice stochastique régulière si et seulement si +$\textsc{giu}(f)$ est fortement connexe. +\end{lemma} + +\begin{Proof} +On remarque tout d'abord que $M$ +est une matrice stochastique par construction. +Supposons $M$ régulière. +Il existe donc $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket +1; 2^n \rrbracket$. L'inégalité $\check{M}_{ij}^k>0$ est alors établie. +Puisque $\check{M}_{ij}^k$ est le nombre de chemins de $i$ à $j$ de longueur $k$ +dans $\textsc{giu}(f)$ et puisque ce nombre est positif, alors +$\textsc{giu}(f)$ est fortement connexe. + +Réciproquement si $\textsc{giu}(f)$ +est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut être construit pour atteindre $j$ depuis $i$ en au plus $2^n$ étapes. +Il existe donc +$k_{ij} \in \llbracket 1, 2^n \rrbracket$ tels que $\check{M}_{ij}^{k_{ij}}>0$. +Comme tous les multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que +$\check{M}_{ij}^{l\times k_{ij}}>0$, +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} + $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}). + Soit $\pi$ défini par + $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$. + On a $\pi M = \pi$ si et seulement si + la somme des valeurs de chaque colonne de $M$ est 1, + \textit{i.e.} si et seulement si + $M$ est doublement stochastique. +\end{Proof} + diff --git a/annexePreuvePRNGchotique.tex b/annexePreuvePRNGchotique.tex new file mode 100644 index 0000000..5277040 --- /dev/null +++ b/annexePreuvePRNGchotique.tex @@ -0,0 +1,328 @@ + + + + + +\subsection{A metric on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$} + +We define a distance $d$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ as follows. +Consider +$x=(e,s)$ and $\check{x}=(\check{e},\check{s})$ in +$\mathcal{X}_{\mathsf{N},\mathcal{P}} = \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}} $, +where $s=(u,v)$ and $\check{s}=(\check{u},\check{v})$ are in $ \mathds{S}_{\mathsf{N},\mathcal{P}} = +\mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. +\begin{itemize} +\item $e$ and $\check{e}$ are integers belonging in $\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$. +\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. +\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. +\end{itemize} +\item The next $p$ digits are $|v^1-\check{v}^1|$, etc. +\end{itemize} +\end{itemize} + + + + +\begin{xpl} +Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=3$), and that +$s=\left\{ +\begin{array}{l} +u=\underline{6,} ~ \underline{11,5}, ...\\ +v=1,2,... +\end{array} +\right.$ +while +$\check{s}=\left\{ +\begin{array}{l} +\check{u}=\underline{6,4} ~ \underline{1}, ...\\ +\check{v}=2,1,... +\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. +\end{xpl} + + +\begin{xpl} +Consider now that $\mathsf{N}=9$, and $\mathcal{P}=\{2,7\}$, and that + +$s=\left\{ +\begin{array}{l} +u=\underline{6,7,} ~ \underline{4,2,} ...\\ +v=2,2,... +\end{array} +\right.$ +while +$\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.$ + +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$. +\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: +\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)}.$$ +\end{itemize} + + +Let us show that, +\begin{prpstn} +$d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. +\end{prpstn} + + +\begin{proof} + $d_{\mathds{B}^\mathsf{N}}$ is the Hamming distance. We will prove that + $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ is a distance +too, thus $d$ will also be a distance, being the sum of two distances. + \begin{itemize} +\item Obviously, $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})\geqslant 0$, and if $s=\check{s}$, then +$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$. Conversely, if $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$, then +$\forall k \in \mathds{N}, v^k=\check{v}^k$ due to the +definition of $d$. Then, as digits between positions $p+1$ and $p+n$ are null and correspond to $|u^0-\check{u}^0|$, we can conclude that $u^0=\check{u}^0$. An extension of this result to the whole first $n \times \max{(\mathcal{P})}$ bloc leads to $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$, and by checking all the $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$. + \item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ is clearly symmetric +($d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\check{s},s)$). +\item The triangle inequality is obtained because the absolute value satisfies it too. + \end{itemize} +\end{proof} + + +Before being able to study the topological behavior of the general +chaotic iterations, we must first establish that: + +\begin{prpstn} + For all $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, the function $G_f$ is continuous on +$\left( \mathcal{X},d\right)$. +\end{prpstn} + + +\begin{proof} +We will show this result by using the sequential continuity. Consider a +sequence $x^n=(e^n,(u^n,v^n)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}^\mathds{N}$ such +that $d(x^n,x) \longrightarrow 0$, for some $x=(e,(u,v))\in +\mathcal{X}_{\mathsf{N},\mathcal{P}}$. We will show that +$d\left(G_f(x^n),G_f(x)\right) \longrightarrow 0$. +Remark that $u$ and $v$ are sequences of sequences. + +As $d(x^n,x) \longrightarrow 0$, there exists +$n_0\in\mathds{N}$ such that +$d(x^n,x) < 10^{-(p+n \max{(\mathcal{P})})}$ +(its $p+n \max{(\mathcal{P})}$ first digits are null). +In particular, $\forall n \geqslant n_0, e^n=e$, +as the Hamming distance between the integral parts of +$x$ and $\check{x}$ is 0. Similarly, due to the nullity +of the $p+n \max{(\mathcal{P})}$ first digits of +$d(x^n,x)$, we can conclude that $\forall n \geqslant n_0$, +$(v^n)^0=v^0$, and that $\forall n \geqslant n_0$, +$(u^n)^0=u^0$, $(u^n)^1=u^1$, ..., $(u^n)^{v^0-1}=u^{v^0-1}$. +This implies that: +\begin{itemize} +\item $G_f(x^n)_1=G_f(x)_1$: they have the same +Boolean vector as first coordinate. +\item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\Sigma (u^n,v^n); \Sigma(u,v)) = 10^{p+n \max{(\mathcal{P})}} d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u^n,v^n); (u,v))$. As the right part of the equality tends +to 0, we can deduce that it is the case too for the left part of the equality, and so +$G_f(x^n)_2$ is convergent to $G_f(x)_2$. +\end{itemize} +\end{proof} + + + +\subsection{$\Gamma_{\mathcal{P}}(f)$ as an extension of $\Gamma(f)$} + +Let $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$. +We define the directed graph $\Gamma_{\mathcal{P}}(f)$ as follows. +\begin{itemize} +\item Its vertices are the $2^\mathsf{N}$ elements of $\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 There is an arc labeled $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ between vertices $x$ and $y$ if and only if +$y=F_{f,p_i} (x, (u_0, \hdots, u_{p_i-1})) $. +\end{itemize} + +It is not hard to see that the graph $\Gamma_{\{1\}}(f)$ is +$\Gamma(f)$. + +\begin{figure}[ht] + \centering + \begin{subfigure}[b]{0.45\textwidth} + \centering + \includegraphics[scale=0.85]{graphe1.pdf} + \caption{$\Gamma(f_0)$} + \label{graphe1} + \end{subfigure}% + ~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc. + % (or a blank line to force the subfigure onto a new line) + \begin{subfigure}[b]{0.3\textwidth} + \centering + \includegraphics[scale=0.85]{graphe2.pdf} + \caption{$\Gamma_{\{2,3\}}(f_0)$} + \label{graphe2} + \end{subfigure} + ~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc. + \caption{Iterating $f_0:(x_1,x_2) \mapsto (\overline{x_1}, \overline{x_2})$} + \label{fig:itg} +\end{figure} + + +\begin{xpl} +Consider for instance $\mathsf{N}=2$, +Let $f_0:\mathds{B}^2 \longrightarrow \mathds{B}^2$ be the negation function, +\textit{i.e.}, $f_0(x_1,x_2) = (\overline{x_1}, \overline{x_2})$, and consider +$\mathcal{P}=\{2,3\}$. The graphs of iterations are given in +\textsc{Figure~\ref{fig:itg}}. +The \textsc{Figure~\ref{graphe1}} shows what happens when +displaying each iteration result. +On the contrary, the \textsc{Figure~\ref{graphe2}} explicits the behaviors +when always applying 2 or 3 modification and next outputing results. +Notice that here, orientations of arcs are not necessary +since the function $f_0$ is equal to its inverse $f_0^{-1}$. +\end{xpl} + +\subsection{Proofs of chaos} + +We will show that, +\begin{prpstn} +\label{prop:trans} + $\Gamma_{\mathcal{P}}(f)$ is strongly connected if and only if $G_f$ is +topologically transitive on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$. +\end{prpstn} + + +\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 +$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}$,... + +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|},..., + 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}$. + + +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. +\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} + +\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 +$$\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: +$$(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$. +\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} + +\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} + +The next section shows how to generate functions and a iteration number $b$ +such that $\Gamma_{\{b\}}$ is strongly connected. + + + \ No newline at end of file diff --git a/main.tex b/main.tex index dcbfa74..34e991d 100644 --- a/main.tex +++ b/main.tex @@ -17,6 +17,7 @@ \usepackage[utf8]{inputenc} \usepackage{thmtools, thm-restate} \usepackage{multirow} +\usepackage{algorithm2e} %\declaretheorem{theorem} %%-------------------- @@ -175,7 +176,7 @@ au chaos} \chapter[Caracterisation des systèmes discrets chaotiques]{Caracterisation des systèmes - discrets chaotiques pour les schémas unaires et généralisés} + discrets chaotiques pour les schémas unaires et généralisés}\label{chap:carachaos} La première section rappelle ce que sont les systèmes dynamiques chaotiques. Dire que cette caractérisation dépend du type de stratégie : unaire (TIPE), @@ -195,7 +196,7 @@ On montre qu'on a des résultats similaires. \input{15TSI} -\section{Générer des fonctions chaotiques} +\section{Générer des fonctions chaotiques}\label{sec:11FCT} \input{11FCT} \chapter{Prédiction des systèmes chaotiques} @@ -290,7 +291,8 @@ par deux entiers voisins. \input{annexesccg} - +\chapter{Preuves sur les générateurs de nombres pseudo-aléatoires}\label{anx:generateur} +\input{annexePreuveDistribution} \backmatter -- 2.39.5