X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/b60c35c87e498fa1be9cc75364cd069b18b06e9d..988f9c51eeae9751e11cdaf34302ee96677a10da:/intro.tex

diff --git a/intro.tex b/intro.tex
index b2cdd1c..569c493 100644
--- a/intro.tex
+++ b/intro.tex
@@ -1,57 +1,50 @@
 The exploitation of chaotic systems to generate pseudorandom sequences is
 an hot topic~\cite{915396,915385,5376454}. Such systems are fundamentally 
-chosen due to their unpredictable character and their sensibility to initial conditions.
+chosen due to their unpredictable character and their sensitiveness to initial conditions.
 In most cases, these generators simply consist in iterating a chaotic function like 
 the logistic map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots
 It thus remains to find optimal parameters in such functions so that attractors are
-avoided, guaranteeing by doing so that generated numbers follow a uniform distribution.
+avoided, hoping by doing so that the generated numbers follow a uniform distribution.
 In order to check the quality of the produced outputs, it is usual to test the 
 PRNGs   (Pseudo-Random  Number   Generators) with statistical batteries like
-the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite{LEcuyerS07}.
+the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite{LEcuyerS07} ones.
+
+In its general understanding, chaos notion is often reduced to the strong
+sensitiveness to the initial conditions (the well known ``butterfly effect''):
+a continuous function $k$ defined on a metrical space is said 
+\emph{strongly sensitive to the initial conditions} if for each point 
+$x$ and each positive value $\epsilon$, it is possible to find another 
+point $y$ as close as possible to $x$, and an integer $t$ such that the distance
+between the $t$-th iterates of $x$ and $y$, denoted by $k^t(x)$ and $k^t(y)$,
+are larger than $\epsilon$. However, in his definition of chaos, Devaney~\cite{Devaney} 
+imposes to the chaotic function two other properties called
+\emph{transitivity} and \emph{regularity}. Functions evoked above have
+been studied according to these properties, and they have been proven as chaotic on $\R$.
+But nothing guarantees that such properties are preserved when iterating the functions
+on floating point numbers, which is the domain of interpretation of real numbers $\R$ on
+machines.
+
+To avoid this lack of chaos, we have previously presented some PRNGs that iterate
+continuous functions $G_f$ on a discrete domain  $\{ 1, \ldots,  n \}^{\Nats}
+ \times  \{0,1\}^n$, where $f$  is a Boolean function (\textit{i.e.},  $f  :
+ \{0,1\}^n      \rightarrow      \{0,1\}^n$).       These generators are 
+$\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11:ip},
+$\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip}                                     and
+$\chi_{\textit{14Secrypt}}$ \cite{chgw14oip}     where    \textit{CI}    means
+\emph{Chaotic Iterations}.
+We have firstly proven in~\cite{bcgr11:ip} that, to establish the chaotic nature
+of algorithm $\textit{CIPRNG}_f^1$, it is necessary and sufficient that the 
+asynchronous iterations are strongly connected. We then have proven that it is necessary
+and sufficient that the Markov matrix associated to this graph is doubly stochastic,
+in order to have a uniform distribution of the outputs. We have finally established 
+sufficient conditions to guarantee the first property of connectivity. Among the 
+generated functions, we thus have considered for further investigations only the one that
+satisfy the second property too. In~\cite{chgw14oip}, we have proposed an algorithmic 
+method allowing to directly obtain a strongly connected iteration graph having a doubly
+stochastic Markov matrix. The research work presented here generalizes this latter article
+by updating the iteration domain and the metric. The obtained algorithm owns the same
+theoretical properties but with a reduced mixing time.
 
-% 
-% Dans son acception vulgarisÃ©e, 
-% la notion de chaos est souvent rÃ©duite Ã  celle de forte sensibilitÃ©
-% aux conditions initiales (le fameux \og \emph{effet papillon}\fg{}): 
-% une fonction continue $k$ dÃ©finie sur un espace mÃ©trique 
-% est dite \emph{fortement sensible aux conditions initiales} si pour tout
-% point $x$ et pour toute valeur positive $\epsilon$
-% il est possible de trouver un point $y$, arbitrairement proche 
-% de $x$, et un entier $t$ tels que la distance entre les 
-% $t^{\textrm{iÃ¨mes}}$ itÃ©rÃ©s de $x$ et de $y$ 
-% -- notÃ©s $k^t(x)$ et $k^t(y)$ 
-% -- est supÃ©rieure Ã  $\epsilon$. 
-% Cependant, dans sa dÃ©finition du chaos, 
-% Devaney~\cite{Devaney} impose Ã  la fonction chaotique deux autres propriÃ©tÃ©s 
-% appelÃ©es \emph{transitivitÃ©} et \emph{rÃ©gularitÃ©},
-% Les fonctions citÃ©es plus haut ont Ã©tÃ© Ã©tudiÃ©es 
-% au regard de ces propriÃ©tÃ©s et ont Ã©tÃ© prouvÃ©es comme chaotiques sur $\R$.
-% Cependant, rien ne garantit que ces propriÃ©tÃ©s sont prÃ©servÃ©es sur les nombres 
-% flottants qui est le domaine d'interprÃ©tation des nombres rÃ©els de $\R$.
-% 
-% Pour Ã©viter cette perte de chaos,  nous avons prÃ©sentÃ© des PRNGs qui itÃ¨rent des
-% fonctions continues  $G_f$ sur  un domaine discret  $\{ 1, \ldots,  n \}^{\Nats}
-% \times  \{0,1\}^n$  oÃ¹ $f$  est  une  fonction  boolÃ©enne (\textit{i.e.},  $f  :
-% \{0,1\}^n      \rightarrow      \{0,1\}^n$).       Ces     gÃ©nÃ©rateurs      sont
-% $\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11:ip},
-% $\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip}                                     et
-% $\chi_{\textit{14Secrypt}}$ \cite{chgw14oip}     oÃ¹    \textit{CI}    signifie
-% \emph{Chaotic Iterations}.
-% 
-% Dans~\cite{bcgr11:ip} nous avons tout d'abord  prouvÃ© que pour Ã©tablir la nature
-% chaotique de l'algorithme $\textit{CIPRNG}_f^1$,  il est nÃ©cessaire et suffisant
-% que le  graphe des  itÃ©rations asynchrones soit  fortement connexe.   Nous avons
-% ensuite  prouvÃ© que  pour  que la  sortie de  cet  algorithme suive  une loi  de
-% distribution uniforme, il  est nÃ©cessaire et suffisant que  la matrice de Markov
-% associÃ©e Ã  ce graphe soit  doublement stochastique.  Nous avons enfin Ã©tabli des
-% conditions suffisantes pour garantir  la premiÃ¨re propriÃ©tÃ© de connexitÃ©.  Parmi
-% les  fonctions gÃ©nÃ©rÃ©es,  on ne  retenait ensuite  que celles  qui  vÃ©rifiait la
-% seconde  propriÃ©tÃ©.  Dans~\cite{chgw14oip},  nous avons  proposÃ©  une dÃ©marche
-% algorithmique permettant d'obtenir  directement un graphe d'itÃ©rations fortement
-% connexe et  dont la matrice de  Markov est doublement  stochastique.  Le travail
-% prÃ©sentÃ© ici gÃ©nÃ©ralise ce dernier  article en changeant le domaine d'itÃ©ration,
-% et donc de mÃ©trique. L'algorithme  obtenu possÃ¨de les mÃªme propriÃ©tÃ©s thÃ©oriques
-% mais un temps de mÃ©lange plus rÃ©duit.
 % 
 % Pour dÃ©crire un peu plus prÃ©cisÃ©ment le principe de
 % la gÃ©nÃ©ration pseudo-alÃ©atoire, considÃ©rons l'espace boolÃ©en 
@@ -222,6 +215,16 @@ the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite
 % sur une batterie de tests.
 
 
+The remainder of this article is organized as follows. The next section is devoted to 
+preliminaries, basic notations, and terminologies regarding asynchronous iterations.
+Then, in Section~\ref{sec:proofOfChaos}, Devaney's definition of chaos is recalled
+while the proofs of chaos of our most general PRNGs is provided. Section~\ref{sec:SCCfunc} shows how to generate functions and a number of iterations such that the iteration graph is strongly connected, making the
+PRNG chaotic. The next section focuses on examples of such graphs obtained by modifying the 
+hypercube, while Section~\ref{sec:prng} establishes the link between the theoretical study and
+pseudorandom number generation. 
+This research work ends by a conclusion section, where the contribution is summarized and
+intended future work is outlined.
+
 % Le reste de ce document est organisÃ© comme suit. 
 % La section~\ref{section:chaos} prÃ©sente ce qu'est un systÃ¨me dynamique discret boolÃ©en itÃ©rant une fonction $f$.
 % La chaoticitÃ© de la fonction engendrÃ©e $G_f$ est caractÃ©risÃ©e en 
