From 905e5b647fdc00743e18cb72146a010d5a456287 Mon Sep 17 00:00:00 2001 From: guyeux Date: Sun, 10 Jun 2012 13:14:05 +0200 Subject: [PATCH] =?utf8?q?avanc=C3=A9es?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- review_prng.tex | 239 +++++++++++++++++++++++------------------------- 1 file changed, 116 insertions(+), 123 deletions(-) diff --git a/review_prng.tex b/review_prng.tex index 7ed72e6..80fece0 100644 --- a/review_prng.tex +++ b/review_prng.tex @@ -7,7 +7,7 @@ \usepackage{amsmath} \usepackage{color} \usepackage{dsfont} - +\usepackage{graphicx} \title{A Review of Chaotic Iteration Based Pseudorandom Number Generators} @@ -117,6 +117,7 @@ are defined as follows~\cite{Robert}. \begin{definition} +\label{defIC} Let $f: \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$ and $S \subset \mathcal{P} \left(\llbracket1,\mathsf{N}\rrbracket\right)^\mathds{N}$. \emph{Chaotic iterations} $(f, (x^0, S))$ are defined by: @@ -405,130 +406,122 @@ complexity of the topological dynamical system $(\mathcal{X}, f)$. \subsection{The Lyapunov Exponent} -%\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} -%%} - - - +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. -- 2.39.5