X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/review_prng.git/blobdiff_plain/6d6fccfc41ac320a93542faf3558ea72bd4897da..905e5b647fdc00743e18cb72146a010d5a456287:/review_prng.tex?ds=sidebyside

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.
 
 
 
