From: Christophe Guyeux <christophe.guyeux@univ-fcomte.fr>
Date: Fri, 13 Mar 2015 16:26:37 +0000 (+0100)
Subject: Poursuite de l'intro
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/428720e875baf64678c06f2c75ae55185b18d81a

Poursuite de l'intro
---

diff --git a/intro.tex b/intro.tex
index 3f51a08..f4ed222 100644
--- a/intro.tex
+++ b/intro.tex
@@ -24,30 +24,27 @@ But nothing guarantees that such properties are preserved when iterating the fun
 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.
+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 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.
+
 % 
 % 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