X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/review_prng.git/blobdiff_plain/2a4c35a90cbd9b41b4a730aafa519c8e28ea04ab..refs/heads/master:/review_prng.tex diff --git a/review_prng.tex b/review_prng.tex index d4acd30..80fece0 100644 --- a/review_prng.tex +++ b/review_prng.tex @@ -3,15 +3,15 @@ \usepackage[standard]{ntheorem} \usepackage[english]{babel} - +\usepackage{stmaryrd} \usepackage{amsmath} \usepackage{color} \usepackage{dsfont} - +\usepackage{graphicx} \title{A Review of Chaotic Iteration Based Pseudorandom Number Generators} -\author{Jacques M. Bahi, Jean-Fran\c cois Couchot, Raphaël Couturier, and Christophe Guyeux~\thanks{Authors in alphabetic order}} +\author{Jacques M. Bahi, Jean-Fran\c cois Couchot, Raphaël Couturier,\\ Nicolas Friot, and Christophe Guyeux~\thanks{Authors in alphabetic order}} @@ -27,9 +27,9 @@ \section{Introduction} -\section{Topology} +\section{Topological Study of Disorder} -\subsection{Historical context} +\subsection{Historical Context} Pseudorandom number generators are recurrent sequences having a disordered behavior. @@ -52,474 +52,476 @@ More precisely, his theorem states that, considering Eq.~\eqref{sdd} with a func $f:I \longrightarrow I$ continuous on the line segment $I$, the absence of any 2-cycle implies the convergence of the discrete dynamical system. - -% -% -% \begin{block}{Convergence} -% \begin{itemize} -% \item $f$ monotone -% \item Applications contractantes -% \item Coppel: Pas de 2-cycle $\Rightarrow$ convergence -% \end{itemize} -% \end{block} -%} - - - -%\frame{ -% \frametitle{3-cycle implique chaos} -% \begin{alertblock}{Period Three Implies Chaos (Li et Yorke, 1975)} -%S'il y a un point de période 3, alors il y a un point de n'importe quelle période -% \end{alertblock} -% -% \uncover<2->{ -% \begin{exampleblock}{Remarques} -% \begin{itemize} -% \item Désordre lié à la multiplicité des périodes -% \item \`A AND, on étudie des ``systèmes itératifs'' pour le calcul distribué, généralisation des suites récurrentes -% \end{itemize} -% \end{exampleblock} -% } -%} - - - - - -%%\subsection*{Réécriture des systèmes itératifs} - -%%\frame{ -%% \frametitle{Les systèmes itératifs: généralisation} -%% \begin{block}{Les systèmes itératifs en toute généralité} -%% La formulation suivante englobe tous les modes d'itérations imaginables: -%% $$\left\{ -%% \begin{array}{l} -%% x^0 \in \mathcal{X}\\ -%% x^{n+1} = f^n(x^0, \hdots, x^n) -%% \end{array} -%% \right.$$ -%% où $f^n:\mathcal{X}^{n+1}\rightarrow \mathcal{X}$ -%% \end{block} -%%\uncover<2->{ -%%Différents modes d'itérations: séries, parallèles, chaotiques, asynchrones... -%%} -%%} - - - - - - - - - - -%\subsection*{Cas des Itérations chaotiques} -%\frame{ -% \frametitle{Les « itérations chaotiques »} -% \begin{block}{Définition (Itérations chaotiques)} -% Soient $f: \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$ et $S \subset \mathcal{P} \left(\llbracket1,\mathsf{N}\rrbracket\right)^\mathds{N}$. Les \emph{itérations chaotiques} sont: -%$$\left\{ -%\begin{array}{l} -%x^0 \in \mathds{B}^\mathsf{N} \\ -%\forall n \in \mathds{N}^*, \forall i \in \llbracket 1; \mathsf{N} \rrbracket, x^{n}_i = \left\{ -%\begin{array}{ll} -%x^{n-1}_{i} & \textrm{ si } i \notin S^n\\ -%f(x^{n-1})_{i} & \textrm{ si } i \in S^n -%\end{array} -%\right. -%\end{array} -%\right.$$ -%\end{block} -%%\uncover<2->{ -%%Itérations chaotiques et théorie du chaos: a priori, rien à voir. -%%} -%%\uncover<3->{Y a-t-il un lien ?}\uncover<4->{ Pour quoi faire ?} -%} - - - - - -%\frame{ -% \frametitle{Non-convergence des IC} -% \begin{alertblock}{Théorème (Condition nécessaire de non-convergence)} -% % Soit $f : \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$ et $S \in \mathcal{S}$. -% Si les itérations chaotiques $\left(f,(x^0,S)\right)$ sont non convergentes, alors: -%\begin{itemize} -%\item soit $f$ n'est pas contractante, -%\item soit $S$ n'est pas pseudo-périodique (complète). -%\end{itemize} -% \end{alertblock} -% \uncover<2->{ -% Quelle quantité de désordre ? -% } -%} - - - - - - - - - - -%\frame{ -%\frametitle{Présentation du problème} - -%\begin{tabular}{c||c} -%MATHS DISCRÈTES & TOPOLOGIE MATHÉMATIQUE \tabularnewline -%\hline -%\multirow{2}{5cm}{\centering $f: \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$} & $(\mathcal{X},\tau)$ espace topologique\\ -%& $f : \mathcal{X} \to \mathcal{X}$ continue pour $\tau$\\ -%\hline -%$S \in \mathcal{S} = \llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$ & \multirow{2}{5cm}{\centering $x^0 \in \mathcal{X}$} \\ -%$x^0 \in \mathds{B}^\mathds{N}$ & \\ -%\hline -%$x_i^{n+1} = \left\{ \begin{array}{ll} x^{n}_{i} & \textrm{ si } i \neq S^n\\ f(x^{n})_{i} & \textrm{ si } i = S^n \end{array} \right.$ & $\forall n \in \mathds{N}, x^{n+1} = f(x^n)$ \\ -%\end{tabular} - -%} - - - - - - -%\frame{ -%\frametitle{Définitions et notations} -%\begin{block}{Introduisons quelques fonctions...} -%\begin{itemize} -%\item décalage: $\sigma : \mathcal{S} \longrightarrow \mathcal{S}, (S^n)_{n \in \mathds{N}} \mapsto (S^{n+1})_{n \in \mathds{N}}$. -%\item initiale: $i : \mathcal{S} \longrightarrow \llbracket 1 ; \mathsf{N} \rrbracket, (S^n)_{n \in \mathds{N}} \mapsto S^0$ -%\item $F_f : \llbracket 1 ; \mathsf{N} \rrbracket \times \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N},$ $$(k,E) \longmapsto \left( E_j.\delta(k,j) + f(E)_k.\overline{\delta (k,j)} \right)_{j \in \llbracket 1 ; \mathsf{N} \rrbracket}$$ -%\end{itemize} -%où $\delta(x,y) = \left\{\begin{array}{ll} -%0 & \textrm{ si } x=y, \\ -%1 & \textrm{ sinon.} -% \end{array}\right. -%$ -%\end{block} -%} - - - - -%\frame{ -%\frametitle{Modélisation des IC} -%\begin{alertblock}{Modélisation des IC en topologie} -%Soit $\mathcal{X} = \llbracket 1 ; \mathsf{N} \rrbracket^\mathds{N} \times \mathds{B}^\mathsf{N},$ et $G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right).$ - - -%On modélise les itérations chaotiques $\left(f, (S,x^0)\right)$ par le système dynamique discret: -%$$\left\{ -%\begin{array}{l} -%X^0 = (S,x^0) \in \mathcal{X}, \\ -%\forall k \in \mathds{N}, X^{k+1} = G_f(X^k). -%\end{array} -%\right.$$ -%\end{alertblock} - -% \uncover<2>{ -% On peut donc étudier leur désordre topologique. -% } -%} - - - - - -%\frame{ -% \frametitle{Métrique et continuité} - -%Distance sur $\mathcal{X}:$ -%$$d((S,E);(\check{S};\check{E})) = d_e(E,\check{E}) + d_s(S,\check{S})$$ - -%\noindent où $\displaystyle{d_e(E,\check{E}) = \sum_{k=1}^\mathsf{N} \delta (E_k, \check{E}_k)}$, ~~et~ $\displaystyle{d_s(S,\check{S}) = \dfrac{9}{\textsf{N}} \sum_{k = 1}^\infty \dfrac{|S^k-\check{S}^k|}{10^k}}$. -%%\end{block} - -%\vspace{0.5cm} - -%\begin{alertblock}{Théorème} -%La fonction $G_f : (\mathcal{X},d) \to (\mathcal{X},d)$ est continue. -%\end{alertblock} - -%} - - - -% \frame{ -% \frametitle{\'Etude de $(\mathcal{X},d)$} -% \begin{block}{Propriétés de $(\mathcal{X},d)$} -% \begin{itemize} -% \item $\mathcal{X}$ est infini indénombrable -% \vspace{0.15cm} -% \item $(\mathcal{X},d)$ est un espace métrique compact, complet et parfait -% \end{itemize} -% \end{block} -% -% \vspace{0.5cm} -% -% \begin{block}{\'Etude de $G_{f_0}$} -% $G_{f_0}$ est surjective, mais pas injective \vspace{0.3cm}\newline $\Rightarrow (\mathcal{X},G_{f_0})$ pas réversible. -% \end{block} - -% } - - - -%%\frame{ -%% \frametitle{Etude des périodes} -%% \begin{block}{Multiplicité des périodes ?} -%% Soit $f_0:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$ la négation vectorielle. -%% \begin{itemize} -%% \item $\forall k \in \mathds{N}, Per_{2k+1}(G_{f_0}) = \varnothing, card\left(Per_{2k+2}(G_{f_0})\right)>0$ \vspace{0.3cm} \linebreak $\Rightarrow G_{f_0}$ pas chaotique sur $\mathcal{X}$ -%% \item Cependant : -%% \begin{itemize} -%% \item Il y a chaos sur $\mathcal{X}^G = \mathcal{P}\left(\llbracket 1,\mathsf{N}\rrbracket\right)^\mathds{N}\times \mathds{B}^\mathsf{N}$. -%% \item $G_{f_0}$ possède plus de $n^2$ points périodiques de période $2n$. -%% \end{itemize} -%% \end{itemize} -%% \end{block} -%% \uncover<2->{ -%% Cette multiplicité des périodes n'est pas le désordre complet... -%% } -%%} - - - -%\subsection*{Approche type Devaney/Knudsen} - -%\frame{ -% \frametitle{Les approches Devaney et Knudsen} -% \begin{block}{3 propriétés pour de l'imprévisibilité} -% \begin{enumerate} -% \item \emph{Indécomposabilité.} On ne doit pas pouvoir simplifier le système -% \begin{itemize} -% \item Impossible de diviser pour régner -% \item Des orbites doivent visiter tout l'espace -% \end{itemize} -% \item \emph{Élément de régularité.} -% \begin{itemize} -% \item Contrecarre l'effet précédent -% \item Des points proches \textit{peuvent} se comporter complètement différemment -% \end{itemize} -% \item \emph{Sensibilité.} Des points proches \textit{peuvent} finir éloignés -% \end{enumerate} -% \end{block} -%} - - -%\frame{ -% \frametitle{Exemple : définition de Devaney} -%\begin{enumerate} -%\item \emph{Transitivité:} Pour chaque couple d'ouverts non vides $A,B \subset \mathcal{X}$, il existe $k \in \mathbb{N}$ tel que $f^{(k)}(A)\cap B \neq \varnothing$ -%\item \emph{Régularité:} Les points périodiques sont denses -%\item \emph{Sensibilité aux conditions initiales:} Il existe $\varepsilon>0$ tel que $$\forall x \in \mathcal{X}, \forall \delta >0, \exists y \in \mathcal{X}, \exists n \in \mathbb{N}, d(x,y)<\delta \textrm{ et } d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$$ -%\end{enumerate} -%} - -%\frame{ -% \frametitle{Systèmes intrinsèquement compliqués} -% \begin{block}{Définitions de l'indécomposabilité} -% \begin{itemize} -% \item \emph{Indécomposable}: pas la réunion de deux parties non vides, fermées et t.q. $f(A) \subset A$ -% \item \emph{Totalement transitive}: $\forall n \geqslant 1$, l'application composée $f^{(n)}$ est transitive. -% \item \emph{Fortement transitif}: -%$\forall x,y \in \mathcal{X},$ $\forall r>0,$ $\exists z \in B(x,r),$ $\exists n \in \mathbb{N},$ $f^{(n)}(z)=y.$ -% \item \emph{Topologiquement mélangeant}: pour toute paire d'ouverts disjoints et non vides $U$ et $V$, il existe $n_0 \in \mathbb{N}$ tel que $\forall n \geqslant n_0, f^{(n)}(U) \cap V \neq \varnothing$. -% \end{itemize} -% \end{block} -%} - - - - -%\frame{ -%\frametitle{Stabilité et expansivité} -% \begin{block}{Définitions de la sensibilité} -% \begin{itemize} -% \item $(\mathcal{X},f)$ est \emph{instable} si tous ses points le sont: $\forall x \in \mathcal{X},$ $\exists \varepsilon >0,$ $\forall \delta > 0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$ et $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$ -% \item $(\mathcal{X},f)$ est \emph{expansif} si -%$\exists \varepsilon >0,$ $\forall x \neq y,$ $\exists n \in \mathbb{N},$ $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$ -% \end{itemize} -% \end{block} -%} - -%%\frame{ -%% \frametitle{Des systèmes imprévisibles} -%% \begin{block}{Définitions des systèmes dynamiques désordonnés} -%% \begin{itemize} -%% \item \emph{Devaney:} $(\mathcal{X},f)$ est sensible aux conditions initiales, régulier et transitif -%% \item \emph{Wiggins:} $(\mathcal{X},f)$ est transitif et sensible aux conditions initiales -%% \item \emph{Knudsen:} $(\mathcal{X},f)$ a une orbite dense et s'il est sensible aux conditions initiales -%% \item \emph{expansif:} $(\mathcal{X},f)$ est transitif, régulier et expansif -%% \end{itemize} -%% \end{block} -%%} - - - -%\subsection*{Autres approches} - - -%\frame{ -% \frametitle{Selon Li et Yorke} -% \begin{block}{Définitions} -% \begin{description} -%\item[Couple de Li-Yorke.] $(x,y)$ en est un quand: $\limsup_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))>0$ et $\liminf_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))=0.$ - -%\item[Ensemble brouillé.] $B \subset \mathcal{X}$ en est un si tout couple de points distincts de $B$ est de Li-Yorke. - -%\item[Systèmes de Li-Yorke.] $\mathcal{X}$ est compact et contient un ensemble brouillé indénombrable. -%\end{description} -%\end{block} -%} - - - - - - -%\frame{ -% \frametitle{Approche entropie topologique} -% \begin{block}{Entropie topologique} -% \begin{itemize} -% \item $x,y \in \mathcal{X}$ sont ~$\varepsilon-$\emph{séparés en temps $n$} s'il existe $k \leqslant n$ tel que $d\left(f^{(k)}(x),f^{(k)}(y)\right)>\varepsilon$. -% \item Les ensembles $(n,\varepsilon)-$séparé sont des ensembles de points qui seront tous $\varepsilon-$séparés en temps $n$ -% \item $s_n(\varepsilon,Y)$: cardinal maximal d'un ensemble $(n,\varepsilon)-$séparé $$h_{top}(\mathcal{X},f) = \displaystyle{\lim_{\varepsilon \rightarrow 0} \Big[ \limsup_{n \rightarrow +\infty} \dfrac{1}{n} \log s_n(\varepsilon,\mathcal{X})\Big]}$$ -% \end{itemize} -% \end{block} -%} - - - - -%\frame{ -% \frametitle{Exposant de Lyapunov} -%\begin{block}{L'exposant de Lyapunov} -%$$\lambda(x^0) = \displaystyle{\lim_{n \to +\infty} \dfrac{1}{n} \sum_{i=1}^n \ln \left| ~f'\left(x^{i-1}\right)\right|}$$ -%Il doit être positif pour multiplier les erreurs -%\end{block} -%} - - - - - -%\subsection*{Etude des systèmes itératifs} - -%%\frame{ -%% \frametitle{IC et propriété de Devaney} -%%\begin{alertblock}{Théorème} -%%$G_{f_0}$ est régulier et transitif (Devaney). - -%%Sa sensibilité est $\geqslant \mathsf{N}-1$. -%%\end{alertblock} - -%%\uncover<2->{ -%% \begin{exampleblock}{Question} -%% $f_0$ est-elle la seule fonction dont le système itératif vérifie la condition de Devaney ? -%% \end{exampleblock} -%% -%% \vspace{0.5cm} - -%%Pour y répondre, nous avons utilisé le graphe de tous les possibles par itérations chaotiques : le GTPIC.} -%%} - - - - -%%\frame{ -%% \frametitle{Nombre de fonctions imprévisibles} -%% \begin{alertblock}{Caractérisation des IC imprévisibles selon Devaney} -%%$G_f$ vérifie l'hypothèse de Devaney $\Leftrightarrow$ Son graphe des possibles est fortement connexe. - -%%$\Rightarrow$ Il y a $\left(2^\mathsf{N}\right)^{2^\mathsf{N}}$ IC chaotiques. -%%\end{alertblock} -%%} - - - - - - - -%\frame{ -% \frametitle{Etude topologique} -% \begin{exampleblock}{Etude topologique des ICs} -% \begin{itemize} -% \item $\forall f \in \mathcal{C}$, $Per\left(G_f\right)$ est infini dénombrable, $G_f$ est fortement transitive, est chaotique selon Knudsen, -% \item $\left(\mathcal{X}, G_{f_0}\right)$ est topologiquement mélangeant, expansif (constante 1), est chaotique selon Li-Yorke, a une entropie topologique infinie, un exposant de Lyapunov de $ln(\mathsf{N})$ -% \item Indécomposabilité, instabilité, chaos de Wiggins, de la multiplicité des périodes... -% \end{itemize} -% \end{exampleblock} -%} - - - - - - - -%\frame{ -% \frametitle{Graphe de tous les possibles par IC} -% \begin{center} -% \includegraphics[scale=0.55]{14.Caracterisation_des_IC_chaotiques_selon_Devaney/grapheTPICver2.pdf} -% \end{center} -%} - - - - - - - - - - - - - - - - - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\section*{Topologie des programmes} -%\frame{ -%% 'transition': Crossfade, -% \begin{center} -% \Huge{Topologie des programmes} -% -% \end{center} -%} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%\frame{ -%% \frametitle{Premières questions} -%% \begin{exampleblock}{Le chaos dans mon PC ?} -%% Le désordre, l'imprévisibilité (vrai, sans perte) sont-ils possibles sur un ordinateur ? -%%\begin{itemize} -%% \item Il n'y a pas de réels sur mon PC -%% \item Toute machine ayant un nombre fini d'états finit par entrer dans un cycle. -%%\end{itemize} -%% \end{exampleblock} -%%} - - - - - +This theorem establish a clear link between the existence of a cycle of +a given length and the convergence of the system. In other words, between +cycles and order. Conversely, Li and Yorke have established in 1975~\cite{Li75} that +the presence of a point of period three implies chaos in the same situation +than previously. By chaos, they mean the existence of points of any +period: this kind of disorder, which is the first occurrence of the +term ``chaos'' in the mathematical literature, is thus related to the +multiplicity of periods. Since that time, the mathematical theory of +chaos has known several developments to qualify or quantify the richness +of chaos presented by a given discrete dynamical system, one of the most +famous work, although old, being the one of Devaney~\cite{Devaney}. + +\subsection{Iterative Systems} + +In the distributed computing community, dynamical systems have been +generalized to take into account delay transmission or heterogeneous +computational powers. Mathematically, the intended result is often one +fixed point resulting from the iterations of a given function over a +Boolean vector, considering that: +\begin{itemize} +\item at time $t$, $x^{t}$ is computed using not only $x^{t-1}$, but +potentially any $x^{k}, k0$. +\end{proposition} + +So $ G_{f_0}$ does not present the existence of points of any period referred as chaos in the article of Li and Yorke~\cite{Li75}. +However~\cite{GuyeuxThese10}: + \begin{itemize} + \item This kind of disorder can be stated on $\mathcal{X}^G = \mathcal{P}\left(\llbracket 1,\mathsf{N}\rrbracket\right)^\mathds{N}\times \mathds{B}^\mathsf{N}$. + \item $G_{f_0}$ possesses more than $n^2$ points of period $2n$. + \end{itemize} +Additionally, this existence of points of any period has been rejected +by the community to the benefit of more recent notions of chaos, +like those developed these last decades by Devaney~\cite{Devaney}, Knudsen~\cite{Knudsen94}, etc. +These approaches are recalled in the next section. + +\section{The Mathematical Theory of Chaos} + +We will present in this section various understanding of a chaotic behavior for a discrete +dynamical system. + +\subsection{Approaches Similar to Devaney} + +In these approaches, three ingredients are required for unpredictability. +Firstly, the system must be intrinsically complicated, undecomposable: it cannot be simplified into two +subsystems that do not interact, making any divide and conquer strategy +applied to the system inefficient. In particular, a lot of orbits must visit +the whole space. Secondly, an element of regularity is added, to counteract +the effects of the first ingredient, leading to the fact that closed points +can behave in a completely different manner, and this behavior cannot be predicted. +Finally, sensibility of the system is demanded as a third ingredient, making that +closed points can finally become distant during iterations of the system. +This last requirement is, indeed, often implied by the two first ingredients. + +Having this understanding of an unpredictable dynamical system, Devaney has +formalized in~\cite{Devaney} the following definition of chaos. + +\begin{definition} +A discrete dynamical system $x^0 \in \mathcal{X}, x^{n+1}=f(x^n)$ on a +metric space $(\mathcal{X},d)$ is said to be chaotic according to Devaney +if it satisfies the three following properties: + \begin{enumerate} +\item \emph{Transitivity:} For each couple of open sets $A,B \subset \mathcal{X}$, there exists $k \in \mathbb{N}$ such that $f^{(k)}(A)\cap B \neq \varnothing$. +\item \emph{Regularity:} Periodic points are dense in $\mathcal{X}$. +\item \emph{Sensibility to the initial conditions:} There exists $\varepsilon>0$ such that $$\forall x \in \mathcal{X}, \forall \delta >0, \exists y \in \mathcal{X}, \exists n \in \mathbb{N}, d(x,y)<\delta \textrm{ and } d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon.$$ +\end{enumerate} +\end{definition} + +The system can be intrinsically complicated for various other understanding of this wish, that are +not equivalent one another, like: +\begin{itemize} + \item \emph{Undecomposable}: it is not the union of two nonempty closed subsets that are positively invariant ($f(A) \subset A$). + \item \emph{Total transitivity}: $\forall n \geqslant 1$, the function composition $f^{(n)}$ is transitive. + \item \emph{Strong transitivity}: $\forall x,y \in \mathcal{X},$ $\forall r>0,$ $\exists z \in B(x,r),$ $\exists n \in \mathbb{N},$ $f^{(n)}(z)=y.$ + \item \emph{Topological mixing}: for all pairs of disjoint open nonempty sets $U$ and $V$, there exists $n_0 \in \mathbb{N}$ such that $\forall n \geqslant n_0, f^{(n)}(U) \cap V \neq \varnothing$. +\end{itemize} + + +Concerning the ingredient of sensibility, it can be reformulated as follows. +\begin{itemize} + \item $(\mathcal{X},f)$ is \emph{unstable} is all its points are unstable: $\forall x \in \mathcal{X},$ $\exists \varepsilon >0,$ $\forall \delta > 0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$ and $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$. + \item $(\mathcal{X},f)$ is \emph{expansive} is $\exists \varepsilon >0,$ $\forall x \neq y,$ $\exists n \in \mathbb{N},$ $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$ +\end{itemize} + +These variety of definitions lead to various notions of chaos. For instance, +a dynamical system is chaotic according to Wiggins if it is transitive and +sensible to the initial conditions. It is said chaotic according to Knudsen +if it has a dense orbit while being sensible. Finally, we speak about +expansive chaos when the properties of transitivity, regularity, and expansivity +are satisfied. + + + +\subsection{Li-Yorke approach} + +The approach for chaos presented in the previous section, considering that +a chaotic system is a system intrinsically complicated (undecomposable), +with possibly an element of regularity and/or sensibility, has been +completed by other understanding of chaos. Indeed, as ``randomness'' +or ``infiniteness'', a single universal definition of chaos is cannot +be found. The kind of behaviors that are attempted to be described are +too much complicated to enter into only one definition. Instead, a +large panel of mathematical descriptions have been proposed these last +decades, being all theoretically justified. Each of these definitions +give illustration to some particular aspects of a chaotic behavior. + +The first of these parallel approaches can be found in the pioneer +work of Li and Yorke~\cite{Li75}. In their well-known article entitled +``Period three implies chaos'', they rediscovered a weaker formulation of +the Sarkovskii's theorem, meaning that when a discrete dynamical system +$(f,[0,1])$, with $f$ continuous, has a 3-cycle, then it has too a +$n-$cycle, $\forall n \leqslant 2$. The community has not adopted this +definition of chaos, as several degenerated systems satisfy this property. +However, on their article~\cite{Li75}, Li and Yorke have studied too +another interesting property, which has led to a notion of chaos +``according to Li and Yorke'', which is recalled below. + +Let us firstly introduce the definition of Li-Yorke scrambled couple +of points. This is points that never stop to oscillate. + +\begin{definition} +Let $(\mathcal{X},d)$ a metric space and $f:\mathcal{X} \longrightarrow +\mathcal{X}$ a continuous map. $(x,y)\in \mathcal{X}^2$ is a scrambled +couple of points if $lim inf_{n\rightarrow \infty} d(f^n(x),f^n(y))=0$ +and $lim sup_{n\rightarrow \infty} d(f^n(x),f^n(y))>0$. +\end{definition} + +A scrambled set is a set in which any couple of points oscillate (are +a scrambled couple), whereas a Li-Yorke chaotic system is a system +possessing an uncountable scrambled set. + + +\subsection{Topological Entropy Approach} + +The topological entropy of a topological dynamical system, +firstly introduced in 1965 by Adler, Konheim, and McAndrew~\cite{Adler65}, +is a nonnegative real number that measures the complexity of the system. +It represents the exponential growth rate of the number of distinguishable +orbits of the iterates, for a system given by an iterated function. +It can be formulated as follows. + +Let $f:\mathcal{X} \longrightarrow \mathcal{X}$ be a continuous map on +a compact metric space $(\mathcal{X},d)$. For each natural +number $n$, a new metric $d_n$ is defined on $\mathcal{X}$ by +$$d_n(x,y)=\max\{d(f^i(x),f^i(y)): 0\leq i0$ and $n \geqslant 1$, two points of +$\mathcal{X}$ are $\varepsilon$-close with respect to +this metric if their first $n$ iterates are $\varepsilon$-close. This +metric allows one to distinguish in a neighborhood of an orbit the +points that move away from each other during the iteration from the +points that travel together. + +A subset $E$ of $\mathcal{X}$ is said to be $(n,\varepsilon)$-separated +if each pair of distinct points of $E$ is at least $\varepsilon$ apart +in the metric $d_n$. Denote by $N(n, \varepsilon)$ the +maximum cardinality of a $(n,\varepsilon)$-separated set. +$N(n, \varepsilon)$ represents the number of distinguishable orbit +segments of length $n$, assuming that we cannot distinguish points +within $\varepsilon$ of one another. + +\begin{definition} +The topological +entropy of the map $f$ is defined by +$$h(f)=\lim_{\epsilon\to 0} \left(\limsup_{n\to \infty} \frac{1}{n} +\log N(n,\epsilon)\right).$$ +\end{definition} + + + +The limit defining $h(f)$ may +be interpreted as the measure of the average exponential growth of the +number of distinguishable orbit segments. In this sense, it measures +complexity of the topological dynamical system $(\mathcal{X}, f)$. + +\subsection{The Lyapunov Exponent} + +The last measure of chaos that has been regarded for our proposed family +of pseudorandom number generators is the Lyapunov exponent. This +quantity characterizes the rate of separation of infinitesimally close +trajectories. Indeed, two trajectories in phase space with initial +separation $\delta$ diverge at a rate approximately +equal to $\delta e^{\lambda t}$, +where $\lambda$ is the Lyapunov exponent, which is defined by: + +\begin{definition} +Let $f:\mathds{R} \longrightarrow \mathds{R}$ be a differentiable +function, and $x^0\in \mathds{R}$. The Lyapunov exponent is given by +$$\lambda(x^0) = \displaystyle{\lim_{n \to +\infty} \dfrac{1}{n} \sum_{i=1}^n \ln \left| ~f'\left(x^{i-1}\right)\right|}.$$ +\end{definition} + +Obviously, this exponent must be positive to have a multiplication of +initial errors, and thus chaos in this understanding. + +Having all these definitions in mind, we have studied the topological +behavior of chaotic iterations presented in Definition~\ref{defIC}. + +\section{The Study of Iterative Systems} + +We have firstly stated that~\cite{gb11:bc,GuyeuxThese10}: + +\begin{theorem} + $G_{f_0}$ is regular and transitive on $(\mathcal{X},d)$, thus it is + chaotic according to Devaney. +Furthermore, its constant of sensibility is greater than $\mathsf{N}-1$. +\end{theorem} + +Thus the set $\mathcal{C}$ of functions $f:\mathds{B}^\mathsf{N} +\longrightarrow \mathds{B}^\mathsf{N}$ making the chaotic iterations of +Definition~\ref{defIC} a case of chaos according to Devaney, is a nonempty +set. To characterize functions of $\mathcal{C}$, we have firstly stated +that transitivity implies regularity for these particular iterated +systems~\cite{bcgr11:ip}. To achieve characterization, we then have introduced the +following graph. + +\begin{figure} + \centering + \includegraphics[scale=0.55]{grapheTPICver2.pdf} + \caption{Example of an asynchronous iteration graph} + \label{GTPIC} + \end{figure} + + + +Let $f$ be a map from $\mathds{B}^\mathsf{N}$ to itself. The +{\emph{asynchronous iteration graph}} associated with $f$ is the +directed graph $\Gamma(f)$ defined by: the set of vertices is +$\mathds{B}^\mathsf{N}$; for all $x\in\mathds{B}^\mathsf{N}$ and +$i\in \llbracket1;\mathsf{N}\rrbracket$, +the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(i,x)$. +The relation between $\Gamma(f)$ and $G_f$ is clear: there exists a +path from $x$ to $x'$ in $\Gamma(f)$ if and only if there exists a +strategy $s$ such that the parallel iteration of $G_f$ from the +initial point $(s,x)$ reaches the point $x'$. Figure~\ref{GTPIC} presents +such an asynchronous iteration graph. +We thus have proven that~\cite{bcgr11:ip}. + + +\begin{theorem} +$G_f$ is transitive, and thus chaotic according to Devaney, +if and only if $\Gamma(f)$ is strongly connected. +\end{theorem} + +This characterization makes it possible to quantify the number of +functions in $\mathcal{C}$: it is equal to + $\left(2^\mathsf{N}\right)^{2^\mathsf{N}}$. +Then the study of the topological properties of disorder of these +iterative systems has been further investigated, leading to the following +results. + +\begin{theorem} + $\forall f \in \mathcal{C}$, $Per\left(G_f\right)$ is infinitely countable, $G_f$ is strongly transitive and is chaotic according to Knudsen. It is thus undecomposable, unstable, and chaotic as defined by Wiggins. + \end{theorem} + + \begin{theorem} +$\left(\mathcal{X}, G_{f_0}\right)$ is topologically mixing, + expansive (with a constant equal to 1), chaotic as defined by + Li and Yorke, and has a topological entropy and an exponent of Lyapunov + both equal to $ln(\mathsf{N})$. +\end{theorem} + +At this stage, a new kind of iterative systems that only manipulates +integers have been discovered, leading to the questioning of their +computing for security applications. In order to do so, the possibility +of their computation without any loss of chaotic properties has first +been investigated. These chaotic machines are presented in the next +section. + + + + +\section{Topology of Programs} + + +The next stage was to prove that chaos was possible in finite machine. +The two main problems were that: (1) Chaotic sequences are usually +defined in the real line whereas define real numbers on computers +is impossible. (2) All finite state machines always enter into a cycle +when iterating, and this periodic behavior cannot be stated as chaotic. + +The first problem is disputable, as the shadow lemma proves that, when +considering the sequence $x^{n+1} = trunc_k\left(f(x^n)\right)$, where +$(f,[0,1])$ is a chaotic dynamical system and $trunc_k(x) = +\dfrac{\lfloor 10^k x \rfloor}{10^k}$ is the truncated version of +$x\in \mathds{R}$ at its $k-$th digits, then the sequence $(x^n)$ is as +close as possible to a real chaotic orbit. Thus iterating a chaotic +function on floating point numbers does not deflate the chaotic behavior +as much. However, even if this first claim is not really a problem, we +have prevent from any disputation by considering a tool (the chaotic +iterations) that only manipulates integers bounded by $\mathsf{N}$. + +The second claim is surprisingly never considered as an issue when +considering the generation of randomness on computers.