The exploitation of chaotic systems to generate pseudorandom sequences
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 
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, 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,  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 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)$, 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}. 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
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\}^{\mathsf{N}}
\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} stands for
\emph{Chaotic Iterations}.  We have firstly proven in~\cite{bcgr11:ip}
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
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
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 incorrect to say that the chaos property is preserved for any
subsequence of  a chaotic sequence.  This  article presents conditions
to preserve this property.


Finding a Boolean function which provides a  strongly connected
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 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)
has been removed is strongly connected and has
a doubly stochastic Markov matrix.

However, the removed Hamiltonian cycle  
has a great influence in the quality of the output.
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 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.
This article theoretically and practically
studies the length $b$ until the corresponding Markov
chain is close to the uniform distribution.
Finally, the ability of the approach to face classical tests
suite is evaluated.



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  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 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 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  with a  conclusion
section, where the contribution is summarized and intended future work
is outlined.

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "main"
%%% ispell-dictionary: "american"
%%% mode: flyspell
%%% End:
