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, the chaos notion is often reduced to the strong
+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 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
+\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$.
-% 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.
+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.
+
%
% 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
% 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
