2 From the last two decades, many researchers have investigated the use
3 of chaotic systems to build pseudorandom
4 sequences~\cite{915396,915385,5376454}. Two main features can
5 intuitively explain this interest: first of all, chaotic systems have
6 unpredictable or disorder-like behavior which is needed for producing
7 complex sequences. Furthermore, such systems are extremely sensitive
8 to the initial states too: a tiny difference in the input
9 may lead to dramatic changes in output.
11 Moreover, the property of chaos is often reduced to iterate a
12 \emph{chaotic} function, namely the logistic map\footnote{The logistic
13 map is defined by $X^0 \in [0,1], X^{n+1} = \mu X^n(1-X^n), \mu \in
14 [0,4]$.}~\cite{915396,915385}, the Arnolds cat map\footnote{Discrete
15 Arnolds cat map is defined by $(X^0, Y^0)\in [0,N]^2, X^{n+1} = 2 Y^n
16 + X^n$ mod $N$, $Y^{n+1} = X^n+Y^n$ mod $N$.}~\cite{5376454}\ldots
18 are thus focused on finding parameters of such kind of functions which
19 are the most suitable for generating random-like sequences. More
20 precisely, they have thus to find function parameters that avoid
21 parasitic attractors and that lead to a uniform distribution of the
22 output. To check how accurate are their generated
23 sequences~\cite{bfgw13:ij}, authors are then left to submit their
24 chaos-based PRNG with good parameters on statistical batteries of
25 tests~\cite{DBLP:journals/corr/abs-1112-5239}, namely:
26 DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, and
27 TestU01~\cite{LEcuyerS07}.
31 Devaney has formalized~\cite{Devaney} the fundamental properties of
32 the chaotic maps, namely: sensitive dependence on initial conditions,
33 transitivity, and density of periodic points. For short, a system is
34 sensitive to initial conditions if any point contains, in any
35 neighborhood, another point with a completely different future
36 trajectory. Topological transitivity is established when, for any
37 element, any neighborhood of its future evolution eventually overlaps
38 with any other open set. On the contrary, a dense set of periodic
39 points is an element of regularity that a chaotic dynamical system has
40 to exhibit. However, because of the finiteness of the memory of a
41 computer, only a kind of discrete chaos is generated. This induces
42 that chaotic properties, which could have been proven on $\Reels$, can
43 however be lost on floating point numbers, which is the interpretation
46 To avoid this loss of chaos, we had constructed chaos-based PRNGs
47 that iterate a continuous functions $G_f$ defined on the discrete
48 domain $\llbracket 1 ; n \rrbracket^{\Nats} \times \{0,1\}^n$ where
49 $f$ is a Boolean function (\textit{i.e.}, $f : \{0,1\}^n \rightarrow
50 \{0,1\}^n$). These PRNGs are named
51 $\textit{CIPRNG}_f^1(u)$~\cite{bgw09:ip,guyeuxTaiwan10},
52 $\textit{CIPRNG}_f^2(u,v)$~\cite{wbg10:ip}, and
53 $\textit{XOR~CIPRNG}(S)$~\cite{DBLP:journals/corr/abs-1112-5239},
54 where \textit{CI} stands for \emph{Chaotic Iterations}, which have
55 been particularized according to the function they iterate.
57 Chaotic properties have been well established for both the
58 $\textit{XOR~CIPRNG}$ and $\textit{CIPRNG}_f^1(u)$ under certain
59 conditions for the iteration function $f$, it has been formerly
60 deduced that it was the case too for the whole $\textit{CIPRNG}_f^2$
61 category of generators. However, contrarily to what has been too much
62 rapidly deduced, this claim is not obvious (a subsequence of a chaotic
63 sequence is not necessarily a chaotic sequence too) and it
64 necessitates a rigorous proof, which is the aim of this article.
66 The remainder of the paper is organized as follows.
67 Section~\ref{sec:notations} recalls definitions of chaos properties
68 and of the family of \textit{CIPRNG}. Section~\ref{sec:wellchosen}
69 gives the complete proof of chaos for the $\textit{CIPRNG}_f^2$
70 category. This is the main contribution of this work. The paper ends
71 with a conclusion section where intended future work is presented.
