]> AND Private Git Repository - review_prng.git/commitdiff
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
avancées master
authorguyeux <guyeux@gmail.com>
Sun, 10 Jun 2012 11:14:05 +0000 (13:14 +0200)
committerguyeux <guyeux@gmail.com>
Sun, 10 Jun 2012 11:14:05 +0000 (13:14 +0200)
review_prng.tex

index 7ed72e60decbd9aa0943b3ac07216db5ae3a226c..80fece0e5c121f7add1f96af3e7d10eeeea95a06 100644 (file)
@@ -7,7 +7,7 @@
 \usepackage{amsmath}
 \usepackage{color}
 \usepackage{dsfont}
 \usepackage{amsmath}
 \usepackage{color}
 \usepackage{dsfont}
-
+\usepackage{graphicx}
 
 
 \title{A Review of Chaotic Iteration Based Pseudorandom Number Generators}
 
 
 \title{A Review of Chaotic Iteration Based Pseudorandom Number Generators}
@@ -117,6 +117,7 @@ are defined as follows~\cite{Robert}.
  
 
 \begin{definition}
  
 
 \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:
 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}
 
 
 \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.