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, 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} ones.

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 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, 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.
