The exploitation of chaotic systems to generate pseudorandom sequences
-is a hot topic~\cite{915396,915385,5376454}. Such systems are
-fundamentally chosen due to their unpredictable character and their
+is a very topical issue~\cite{915396,915385,5376454}. Such systems are
+fundamentally chosen because of 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, hoping by doing so that the generated numbers
+map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots
+Optimal parameters of such functions remain to be found so that
+attractors are avoided,\textit{e.g.}.
+By following this procedure, generated numbers will hopefully
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
+produced outputs, PRNGs (Pseudo-Random Number
+Generators) are usually tested with statistical batteries like 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
+In its general understanding, the notion of chaos 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
+space is said to be \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,
+denoted by $k^t(x)$ and $k^t(y)$, is 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
+\emph{regularity}. The functions mentioned 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
\rightarrow \{0,1\}^{\mathsf{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{DBLP:conf/secrypt/CouchotHGWB14} where \textit{CI} means
+\cite{wbg10ip}, and $\chi_{\textit{14Secrypt}}$
+\cite{DBLP:conf/secrypt/CouchotHGWB14} where \textit{CI} stands for
\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
+that, to establish the chaotic nature of
+$\textit{CIPRNG}_f^1$ algorithm, 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
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.
+as well.
However, it cannot be directly deduced that
$\chi_{\textit{14Secrypt}}$ is chaotic since we do not output all the
successive values of iterating $G_f$. This algorithm only displays a
subsequence $x^{b.n}$ of a whole chaotic sequence $x^{n}$ and it is
-indeed not correct that the chaos property is preserved for any
+indeed incorrect to say that the chaos property is preserved for any
subsequence of a chaotic sequence. This article presents conditions
to preserve this property.
iteration graph having a doubly stochastic Markov matrix is however
not an easy task.
We have firstly proposed in~\cite{bcgr11:ip} a generate-and-test based
-approach that solves this issue. However, this one was not efficient enough.
+approach that solved this issue. However, this one was not efficient enough.
Thus, a second scheme has been further presented
in~\cite{DBLP:conf/secrypt/CouchotHGWB14} by remarking that
a $\mathsf{N}$-cube where an Hamiltonian cycle (or equivalently a Gray code)
However, the removed Hamiltonian cycle
has a great influence in the quality of the output.
-For instance, if this one one is not balanced (\textit{i.e.},
+For instance, if this one is not balanced (\textit{i.e.},
the number of changes in different bits are completely different),
some bits would be hard to switch.
This article shows an effective algorithm that efficiently
-implements the previous scheme and provides thus functions issued
-from removing in the $\mathsf{N}$-cube a \emph{balanced} Hamiltonian cycle.
+implements the previous scheme and thus provides functions issued
+from removing, in the $\mathsf{N}$-cube, a \emph{balanced} Hamiltonian cycle.
The length $b$ of the walk to reach a
distribution close to the uniform one would be dramatically long.
-
-The remainder of this article is organized as follows. The next
+This article, which
+is an extension of~\cite{DBLP:conf/secrypt/CouchotHGWB14},
+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
+recalled while the proof of chaos of our most general PRNGs is
provided. This is the first major contribution.
Section~\ref{sec:SCCfunc} recalls a general scheme
-to obtain functions with awaited behavior. Main theorems are recalled
-to make the document self-content.
+to obtain functions with an expected behavior. Main theorems are recalled
+to make the article self-sufficient.
The next section (Sect.~\ref{sec:hamilton}) presents an algorithm that
-implements this scheme and proves it always produces a solution.
-This is the second major contribution
-The later section
-(Sect.~\ref{sec:hypercube}) defines the theoretical framework to study
-the mixing-time, \textit{i.e.}, time until reaching a uniform
-distribution. It proves that this one is at worth quadratic in the number
-of elements. Experiments show that the bound is practically largely much
-lower. This is the third major contribution. The
+implements this scheme and proves that it always produces a solution.
+This is the second major contribution.
+Then, Section~\ref{sec:hypercube} defines the theoretical framework to study
+the mixing-time, \textit{i.e.},
+the sufficient amont of time until reaching an uniform
+distribution. It proves that this one is in the worst case quadratic in the number
+of elements. Experiments show that the bound is in practice
+significantly lower. This is the third major contribution.
Section~\ref{sec:prng} gives practical results on evaluating the PRNG
-against the NIST suite. This research work ends by a conclusion
+against the NIST suite. This research work ends with a conclusion
section, where the contribution is summarized and intended future work
is outlined.
