X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/07a05f881830e54c344db7060dfbfd74220d0eec..412f54fbed2c443f03aa09cc72f559221e63d83b:/intro.tex?ds=inline

diff --git a/intro.tex b/intro.tex
index 097d514..3f51a08 100644
--- a/intro.tex
+++ b/intro.tex
@@ -1,60 +1,54 @@
-L'exploitation de  \og systèmes chaotiques\fg{} pour générer des séquences
-pseudo-aléatoires est un sujet actif de recherche~\cite{915396,915385,5376454}. 
-Ces systèmes sont choisis principalement
-en raison de leur imprévisibilité et de leur sensibilité aux conditions initiales.
-
-Souvent   les   travaux  se   limitent   à   itérer   une  fonction   paramétrée
-\emph{chaotique}  comme la  fonction logistique~\cite{915396,915385},  ou encore
-celle du  chat d'Arnold~\cite{5376454}\ldots Il  reste à trouver  les paramètres
-optimaux permettant d'éviter les attracteurs de telles fonctions et garantissant
-que les séquences de nombres  produits suivent une loi de distribution uniforme.
-Pour vérifier  la qualité des  sorties produites il  est usuel de  soumettre les
-PRNG   (Pseudo-Random  Number   Generator)   à  des   tests  statistiques   tels
-DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10} et TestU01~\cite{LEcuyerS07}.
-
-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.
-
+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 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.
+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}.
+
+In its general understanding, the 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 all point 
+$x$ and all 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} 
+impose 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.
+
+% 
+% 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 
 % $\Bool=\{0,1\}$
@@ -234,15 +228,15 @@ mais un temps de mélange plus réduit.
 % les fonctions dont l'image est uniformément distribuée sur le domaine sont
 % caractérisées et les générateurs sont évalués en section~\ref{sec:prng}.
 
-Dans  la section  suivante,  nous  rappelons les  notions  élémentaires sur  les
-systèmes   booléens.   La  section~\ref{section:caracterisation}   présente  les
-définitions théoriques liées au chaos. Ensuite, une application de ces résultats
-à    la   génération    de   nombres    pseudo-aléatoires   est    proposée   en
-section~\ref{section:genpa}  ainsi  qu'une   méthode  permettant  d'obtenir  des
-matrices         d'itérations         doublement        stochastiques         en
-section~\ref{section:genmat}.  Enfin, en section~\ref{section:expes}  la qualité
-du PRNG obtenu est éprouvée avec les tests standards du domaine.
-
+% Dans  la section  suivante,  nous  rappelons les  notions  élémentaires sur  les
+% systèmes   booléens.   La  section~\ref{section:caracterisation}   présente  les
+% définitions théoriques liées au chaos. Ensuite, une application de ces résultats
+% à    la   génération    de   nombres    pseudo-aléatoires   est    proposée   en
+% section~\ref{section:genpa}  ainsi  qu'une   méthode  permettant  d'obtenir  des
+% matrices         d'itérations         doublement        stochastiques         en
+% section~\ref{section:genmat}.  Enfin, en section~\ref{section:expes}  la qualité
+% du PRNG obtenu est éprouvée avec les tests standards du domaine.
+% 
 
 %%% Local Variables: 
 %%% mode: latex