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.
-%
-% 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\}$
-% muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\bullet}$ \fg{}
-% définies par les tableaux ci-dessous:
-
-% \begin{center}
-% \begin{tabular}{|c|c|c|}
-% \hline
-% + & 0 & 1 \\
-% \hline
-% 0 & 0 & 1 \\
-% \hline
-% 1 & 1 & 1 \\
-% \hline
-% \end{tabular}\qquad
-% \begin{tabular}{|c|c|c|}
-% \hline
-% . & 0 & 1 \\
-% \hline
-% 0 & 0 & 0 \\
-% \hline
-% 1 & 0 & 1 \\
-% \hline
-% \end{tabular}\qquad
-% \begin{tabular}{|c|c|c|}
-% \hline
-% x & 0 & 1 \\
-% \hline
-% $\overline{x}$ & 1 & 0 \\
-% \hline
-% \end{tabular}
-% \end{center}
-
-
-% La fonction itérée est
-% une fonction $f$ de $\Bool^n$ dans lui-même qui à
-% un mot binaire $x = (x_1,\ldots,x_n)$
-% associe le mot $(f_1(x),\ldots, f_n(x))$.
-% Un exemple de fonction de $\Bool^n$ dans lui-même
-% est la fonction négation
-% définie par
-% $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$.
-
-% Le principe itératif, basé sur le mode opératoire dit \emph{asynchrone}, est le
-% suivant: à chaque itération $t$, on choisit un indice $i$ entre $1$ et $n$, et
-% le mot $x^t = (x_1^t,\ldots,x_n^t)$ est remplacé par $x^{t+1} = (x_1^t,\ldots ,
-% x_{i-1}^t, f_i(x^t), x_{i+1}^t,\ldots, x_n^t)$.
-
-% Au bout d'un nombre $N$ d'itérations, si la fonction (notée $G_f$ dans ce
-% document) que l'on peut associer à l'algorithme décrit ci-dessus a de \og
-% \emph{bonnes}\fg{} propriétés chaotiques, le mot $x^N$ doit être \og \emph{très
-% différent}\fg{} de $x^0$ de façon à sembler ne plus dépendre de $x_0$. En
-% effet, pour un générateur aléatoire, il faut que la structure de $x^N$ semble
-% être due au hasard; pour une application cryptographique, il faut qu'il soit
-% matériellement impossible (dans les conditions techniques actuelles) de
-% retrouver $x^0$ à partir de $x^N$.
-
-% Tous les mots de $\Bool^n$ peuvent constituer les $2^n$ sommets d'un
-% \gls{graphoriente} (cf. glossaire) dans lequel un arc relie deux sommets $x$ et
-% $x'$ s'il existe une itération de l'algorithme de génération qui permet de
-% passer directement de $x$ à $x'$. Ce graphe est appelé le \emph{graphe d'itérations} et
-% nous montrons ici que si l'on a un \gls{graphfortementconnexe} (cf. glossaire),
-% alors la fonction $G_f$ est transitive, donc chaotique.
-
-% Enfin, un bon générateur aléatoire se doit de
-% fournir des nombres selon une \gls{distributionuniforme} (cf. glossaire).
-% La dernière partie de cet article donne,
-% dans le cas où le graphe d'itérations est fortement connexe,
-% une condition nécessaire et suffisante pour que
-% cette propriété soit satisfaite.
-
-
-% Le chaos a été appliqué à des domaines variés en
-% informatique, comme les fonctions de hachage,
-% la stéganographie, la génération de nombres pseudo
-% aléatoires\ldots
-% Toutes ces applications exploitent les propriétés définissant des
-% fonctions chaotiques et énoncées par Devaney, telles que la
-% transitivité, la régularité et la sensibilité aux conditions initiales.
-
-
-% Les systèmes dynamiques \emph{chaotiques} sont des processus itératifs
-% définis par une fonction chaotique $f$ d'un domaine $E$ dans lui-même.
-% En démarrant d'un état quelconque $x$ du sytème,
-% nommé par la suite \emph{configuration},
-% le système construit la séquence $x$, $f(x)$, $f^2(x)$, $f^3(x)$, \dots
-% où $f^k(x)$ est le $k^{\textrm{ème}}$ itéré de $f$ en $x$.
-% La plupart des applications informatiques dite \og chaotiques \fg{}
-% sont basées sur des processus itératifs de la forme $x^{n+1} = f(x^n)$
-% où $f$ est la fonction \emph{tente} avec $x^0 = 0,4001$ (donnée à la figure~\ref{fig:iter:tent})
-% ou la fonction \emph{logistique} avec $\mu = 3,45$ et $x^0 = 0,1$ (donnée à la figure~\ref{fig:iter:log})
-% connues pour être chaotiques dans $\R$.
-
-% \begin{figure}[hb]
-% \begin{center}
-% \subfloat[Fonction tente $f=\min\{x,\,1-x\}$]{
-% \begin{minipage}{0.45\textwidth}
-% \begin{center}
-% \includegraphics[height=3cm]{images/tente.png}
-% \end{center}
-% \end{minipage}
-% \label{fig:iter:tent}
-% }
-% \subfloat[Fonction logistique $f(x) = \mu x (1 -x)$]{
-% \begin{minipage}{0.45\textwidth}
-% \begin{center}
-% \includegraphics[height=3cm]{images/logistique.png}
-% \end{center}
-% \end{minipage}
-% \label{fig:iter:log}
-% }
-% \end{center}
-% \caption{Systèmes itératifs basés sur des fonctions chaotiques dans $\R$ \label{fig:iter}}
-% \end{figure}
-
-
-% Cependant il n'a pas été établi que des fonctions prouvées
-% comme étant chaotiques sur $\R$ le restent sur les nombres à virgule flottante,
-% qui est le domaine d'interprétation informatique des réels.
-% On souhaite ainsi éviter une éventuelle perte des propriétés de chaos
-% lors de l'exécution des programmes implémentant ces fonctions.
-% Ce document présente pour cela l'alternative suivante:
-% à partir d'une fonction booléenne, $f: \Bool^n \rightarrow \Bool^n$,
-% où $\Bool$ est le domaine des booléens $\{0,1\}$, on
-% construit une fonction $G_f : \llbracket 1 ; n \rrbracket^{\Nats} \times \Bool^n$,
-% où $\llbracket 1 ; n \rrbracket$ est l'ensemble des entiers
-% $\{1, 2, \hdots, n\}$ et on itère celle-ci.
-% Comme $f$ est discrète, $G_f$ l'est aussi et les résultats théoriques
-% obtenus sur $G_f$, notamment sa chaoticité, sont maintenus durant
-% l'implémentation.
-% Un exemple de fonction booléenne de $\Bool^n$ dans lui-même est la fonction négation
-% définie par
-% $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$.
-
-
-
-
-% De plus, plutôt que de trouver des exemples de telles fonctions $f$, et de prouver
-% (\textit{a posteriori}) la chaoticité de $G_f$, on peut penser à caractériser
-% les fonctions engendrant systématiquement des fonctions chaotiques.
-% Ce document présente une telle caractérisation
-% qui s'exprime sur le graphe des itérations asynchrones
-% de la fonction booléenne $f$, qui est, intuitivement, le graphe
-% de toutes les itérations possibles de la fonction.
-% Cette situation se réduit en un problème portant sur des graphes à $2^n$
-% sommets.
-% Ainsi pour étendre l'applicabilité de cette caractérisation, on s'intéresse
-% au graphe des interactions de $f$, qui, intuitivement,
-% représente les dépendances entre les $f_i$, $1\le i \le n$ et les $i$
-% et qui ne contient que $n$ sommets (et qui est à comparer aux $2^n$
-% sommets.
-% Sur ce graphe on exprime des conditions garantissant la chaoticité de la fonction $G_f$.
-% Ainsi, toutes les fonctions $G_f$ engendrées à partir d'un graphe
-% d'interactions de $f$ aux propriétés \textit{ad hoc} seront chaotiques.
-
-% Se pose enfin l'applicabilité des fonctions $G_f$ à la génération
-% de nombres pseudo aléatoires, l'aléa étant intuitivement
-% une notion proche de celle du chaos.
-% Pour aborder cette classe de problèmes, on remarque que l'on doit au moins
-% garantir que l'ensemble des valeurs retournées par l'algorithme suit
-% une loi uniforme, propriété qui n'est pas imposée d'un point de vue topologique.
-% Ce document montre que cette contrainte peut s'exprimer à nouveau sur le graphe des itérations asynchrones de $f$
-% et qu'on peut ainsi filtrer les bons candidats à la génération de nombres pseudo aléatoires.
-% Cette idée est validée après évaluation
-% des générateurs de nombres pseudo aléatoires
-% sur une batterie de tests.
-
-
-% 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
-% section~\ref{sec:charac}.
-% Des conditions suffisantes pour obtenir cette chaoticité sont présentées en
-% section~\ref{sec:sccg}.
-% L'application à la génération de nombres pseudo aléatoires est formalisée,
-% 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.
-%
-
-%%% Local Variables:
-%%% mode: latex
-%%% TeX-master: "main"
-%%% End:
+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 ones 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.
+
+
+However, it cannot be directly deduced
+that $\chi_{\textit{14Secrypt}}$ is chaotic
+since we do not output all the successive
+values of iterating $F_f$.
+This algorithm only displays a
+subsequence $x^{b.n}$ of a whole chaotic sequence $x^{n}$ and
+it is indeed definitively false that the chaos property is
+preserved for any subsequence of a chaotic sequence.
+This article presents conditions to preserve this property.
+
+An approach to generate a large class of chaotic functions has
+been presented in~\cite{chgw14oip}.
+It is basically fourfold:
+first build a $\mathsf{N}$-cube, next remove an Hamiltonian cycle, further add self-loop
+on each vertex and finally, translate this into a Boolean map.
+We are then left to check whether this approach proposes maps with the required conditions
+for the chaos.
+The answer is indeed positive. The pseudorandom number generation can thus be seen as a
+random walk in a $\mathsf{N}$-cube without a Hamiltonian cycle.
+
+In the PRNG context, there remains to find which subsequence
+is theoretically and practically
+sufficient to extract.
+A uniform distribution is indeed awaited and this
+cannot be obtained in a walk in the hypercube
+with paths of short length $b$.
+However, the higher
+is $b$ the slower is the
+algorithm to generate pseudorandom
+numbers.
+The time until the
+corresponding Markov chain is close
+to the uniform distribution is a metric
+that should be theoretically and practically studied.
+Finally, the ability of the approach to face classical
+tests suite has to be evaluated.
+
+
+%A upper bound of this time quadratic in the number of
+%generated bits.
+
+
+The remainder of this article is organized as follows. The next section is devoted to
+preliminaries, basic notations, and terminologies regarding Boolean map 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.
+This is the first major contribution.
+Section~\ref{sec:SCCfunc} shows how to generate functions with required properties
+making the PRNG chaotic.
+The next section (Sect.~\ref{sec:hypercube}) defines the theoretical framework
+to study the stopping-time, \textit{i.e.}, time until reaching
+a uniform distribution.
+This is the second major contribution.
+The Section~\ref{sec:prng} gives practical results on evaluating the PRNG against the NIST suite.
+This research work ends by a conclusion section, where the contribution is summarized and
+intended future work is outlined.
