-
-
-
-This generator is synthesized in Algorithm~\ref{CI Algorithm}.
-It takes as input: a Boolean function $f$ satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques};
-an integer $b$, ensuring that the number of executed iterations is at least $b$
-and at most $2b+1$; and an initial configuration $x^0$.
-It returns the new generated configuration $x$. Internally, it embeds two
-\textit{XORshift}$(k)$ PRNGs~\cite{Marsaglia2003} that return integers
-uniformly distributed
-into $\llbracket 1 ; k \rrbracket$.
-\textit{XORshift} is a category of very fast PRNGs designed by George Marsaglia,
-which repeatedly uses the transform of exclusive or (XOR, $\oplus$) on a number
-with a bit shifted version of it. This PRNG, which has a period of
-$2^{32}-1=4.29\times10^9$, is summed up in Algorithm~\ref{XORshift}. It is used
-in our PRNG to compute the strategy length and the strategy elements.
-
-This former generator has successively passed various batteries of statistical tests, as the NIST~\cite{bcgr11:ip}, DieHARD~\cite{Marsaglia1996}, and TestU01~\cite{LEcuyerS07} ones.
-
-\subsection{Improving the Speed of the Former Generator}
-
-Instead of updating only one cell at each iteration, we can try to choose a
-subset of components and to update them together. Such an attempt leads
-to a kind of merger of the two sequences used in Algorithm
-\ref{CI Algorithm}. When the updating function is the vectorial negation,
-this algorithm can be rewritten as follows:
-
-\begin{equation}
-\left\{
-\begin{array}{l}
-x^0 \in \llbracket 0, 2^\mathsf{N}-1 \rrbracket, S \in \llbracket 0, 2^\mathsf{N}-1 \rrbracket^\mathds{N} \\
-\forall n \in \mathds{N}^*, x^n = x^{n-1} \oplus S^n,
-\end{array}
-\right.
-\label{equation Oplus}
-\end{equation}
-where $\oplus$ is for the bitwise exclusive or between two integers.
-This rewriting can be understood as follows. The $n-$th term $S^n$ of the
-sequence $S$, which is an integer of $\mathsf{N}$ binary digits, presents
-the list of cells to update in the state $x^n$ of the system (represented
-as an integer having $\mathsf{N}$ bits too). More precisely, the $k-$th
-component of this state (a binary digit) changes if and only if the $k-$th
-digit in the binary decomposition of $S^n$ is 1.
-
-The single basic component presented in Eq.~\ref{equation Oplus} is of
-ordinary use as a good elementary brick in various PRNGs. It corresponds
-to the following discrete dynamical system in chaotic iterations:
-
-\begin{equation}
-\forall n\in \mathds{N}^{\ast }, \forall i\in
-\llbracket1;\mathsf{N}\rrbracket ,x_i^n=\left\{
-\begin{array}{ll}
- x_i^{n-1} & \text{ if } i \notin \mathcal{S}^n \\
- \left(f(x^{n-1})\right)_{S^n} & \text{ if }i \in \mathcal{S}^n.
-\end{array}\right.
-\label{eq:generalIC}
-\end{equation}
-where $f$ is the vectorial negation and $\forall n \in \mathds{N}$,
-$\mathcal{S}^n \subset \llbracket 1, \mathsf{N} \rrbracket$ is such that
-$k \in \mathcal{S}^n$ if and only if the $k-$th digit in the binary
-decomposition of $S^n$ is 1. Such chaotic iterations are more general
-than the ones presented in Definition \ref{Def:chaotic iterations} because, instead of updating only one term at each iteration,
-we select a subset of components to change.
-
-
-Obviously, replacing Algorithm~\ref{CI Algorithm} by
-Equation~\ref{equation Oplus}, which is possible when the iteration function is
-the vectorial negation, leads to a speed improvement. However, proofs
-of chaos obtained in~\cite{bg10:ij} have been established
-only for chaotic iterations of the form presented in Definition
-\ref{Def:chaotic iterations}. The question is now to determine whether the
-use of more general chaotic iterations to generate pseudorandom numbers
-faster, does not deflate their topological chaos properties.
-
-\subsection{Proofs of Chaos of the General Formulation of the Chaotic Iterations}
-\label{deuxième def}
-Let us consider the discrete dynamical systems in chaotic iterations having
-the general form: $\forall n\in \mathds{N}^{\ast }$, $ \forall i\in
-\llbracket1;\mathsf{N}\rrbracket $,
-
-\begin{equation}
- x_i^n=\left\{
-\begin{array}{ll}
- x_i^{n-1} & \text{ if } i \notin \mathcal{S}^n \\
- \left(f(x^{n-1})\right)_{S^n} & \text{ if }i \in \mathcal{S}^n.
-\end{array}\right.
-\label{general CIs}
-\end{equation}
-
-In other words, at the $n^{th}$ iteration, only the cells whose id is
-contained into the set $S^{n}$ are iterated.
-
-Let us now rewrite these general chaotic iterations as usual discrete dynamical
-system of the form $X^{n+1}=f(X^n)$ on an ad hoc metric space. Such a formulation
-is required in order to study the topological behavior of the system.
-
-Let us introduce the following function:
-\begin{equation}
-\begin{array}{cccc}
- \chi: & \llbracket 1; \mathsf{N} \rrbracket \times \mathcal{P}\left(\llbracket 1; \mathsf{N} \rrbracket\right) & \longrightarrow & \mathds{B}\\
- & (i,X) & \longmapsto & \left\{ \begin{array}{ll} 0 & \textrm{if }i \notin X, \\ 1 & \textrm{if }i \in X, \end{array}\right.
-\end{array}
-\end{equation}
-where $\mathcal{P}\left(X\right)$ is for the powerset of the set $X$, that is, $Y \in \mathcal{P}\left(X\right) \Longleftrightarrow Y \subset X$.
-
-Given a function $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, define the function:
-$F_{f}: \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}}
-\longrightarrow \mathds{B}^{\mathsf{N}}$
-\begin{equation*}
-\begin{array}{rll}
- (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+f(E)_{j}.\overline{\chi(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket}%
-\end{array}%
-\end{equation*}%
-where + and . are the Boolean addition and product operations, and $\overline{x}$
-is the negation of the Boolean $x$.
-Consider the phase space:
-\begin{equation}
-\mathcal{X} = \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N} \times
-\mathds{B}^\mathsf{N},
-\end{equation}
-\noindent and the map defined on $\mathcal{X}$:
-\begin{equation}
-G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), %\label{Gf} %%RAPH, j'ai viré ce label qui existe déjà avant...
-\end{equation}
-\noindent where $\sigma$ is the \emph{shift} function defined by $\sigma
-(S^{n})_{n\in \mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow (S^{n+1})_{n\in
-\mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}$ and $i$ is the \emph{initial function}
-$i:(S^{n})_{n\in \mathds{N}} \in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow S^{0}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)$.
-Then the general chaotic iterations defined in Equation \ref{general CIs} can
-be described by the following discrete dynamical system:
-\begin{equation}
-\left\{
-\begin{array}{l}
-X^0 \in \mathcal{X} \\
-X^{k+1}=G_{f}(X^k).%
-\end{array}%
-\right.
-\end{equation}%
-
-Once more, a shift function appears as a component of these general chaotic
-iterations.
-
-To study the Devaney's chaos property, a distance between two points
-$X = (S,E), Y = (\check{S},\check{E})$ of $\mathcal{X}$ must be defined.
-Let us introduce:
-\begin{equation}
-d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}),
-\label{nouveau d}
-\end{equation}
-\noindent where $ \displaystyle{d_{e}(E,\check{E})} = \displaystyle{\sum_{k=1}^{\mathsf{N}%
- }\delta (E_{k},\check{E}_{k})}$ is once more the Hamming distance, and
-$ \displaystyle{d_{s}(S,\check{S})} = \displaystyle{\dfrac{9}{\mathsf{N}}%
- \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}$,
-%%RAPH : ici, j'ai supprimé tous les sauts à la ligne
-%% \begin{equation}
-%% \left\{
-%% \begin{array}{lll}
-%% \displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}%
-%% }\delta (E_{k},\check{E}_{k})} \textrm{ is once more the Hamming distance}, \\
-%% \displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}%
-%% \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}.%
-%% \end{array}%
-%% \right.
-%% \end{equation}
-where $|X|$ is the cardinality of a set $X$ and $A\Delta B$ is for the symmetric difference, defined for sets A, B as
-$A\,\Delta\,B = (A \setminus B) \cup (B \setminus A)$.
-
-
-\begin{proposition}
-The function $d$ defined in Eq.~\ref{nouveau d} is a metric on $\mathcal{X}$.
-\end{proposition}
-
-\begin{proof}
- $d_e$ is the Hamming distance. We will prove that $d_s$ is a distance
-too, thus $d$, as being the sum of two distances, will also be a distance.
- \begin{itemize}
-\item Obviously, $d_s(S,\check{S})\geqslant 0$, and if $S=\check{S}$, then
-$d_s(S,\check{S})=0$. Conversely, if $d_s(S,\check{S})=0$, then
-$\forall k \in \mathds{N}, |S^k\Delta {S}^k|=0$, and so $\forall k, S^k=\check{S}^k$.
- \item $d_s$ is symmetric
-($d_s(S,\check{S})=d_s(\check{S},S)$) due to the commutative property
-of the symmetric difference.
-\item Finally, $|S \Delta S''| = |(S \Delta \varnothing) \Delta S''|= |S \Delta (S'\Delta S') \Delta S''|= |(S \Delta S') \Delta (S' \Delta S'')|\leqslant |S \Delta S'| + |S' \Delta S''|$,
-and so for all subsets $S,S',$ and $S''$ of $\llbracket 1, \mathsf{N} \rrbracket$,
-we have $d_s(S,S'') \leqslant d_e(S,S')+d_s(S',S'')$, and the triangle
-inequality is obtained.
- \end{itemize}
-\end{proof}
-
-
-Before being able to study the topological behavior of the general
-chaotic iterations, we must first establish that:
-
-\begin{proposition}
- For all $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, the function $G_f$ is continuous on
-$\left( \mathcal{X},d\right)$.
-\end{proposition}
-
-
-\begin{proof}
-We use the sequential continuity.
-Let $(S^n,E^n)_{n\in \mathds{N}}$ be a sequence of the phase space $%
-\mathcal{X}$, which converges to $(S,E)$. We will prove that $\left(
-G_{f}(S^n,E^n)\right) _{n\in \mathds{N}}$ converges to $\left(
-G_{f}(S,E)\right) $. Let us remark that for all $n$, $S^n$ is a strategy,
-thus, we consider a sequence of strategies (\emph{i.e.}, a sequence of
-sequences).\newline
-As $d((S^n,E^n);(S,E))$ converges to 0, each distance $d_{e}(E^n,E)$ and $d_{s}(S^n,S)$ converges
-to 0. But $d_{e}(E^n,E)$ is an integer, so $\exists n_{0}\in \mathds{N},$ $%
-d_{e}(E^n,E)=0$ for any $n\geqslant n_{0}$.\newline
-In other words, there exists a threshold $n_{0}\in \mathds{N}$ after which no
-cell will change its state:
-$\exists n_{0}\in \mathds{N},n\geqslant n_{0}\Rightarrow E^n = E.$
-
-In addition, $d_{s}(S^n,S)\longrightarrow 0,$ so $\exists n_{1}\in %
-\mathds{N},d_{s}(S^n,S)<10^{-1}$ for all indexes greater than or equal to $%
-n_{1}$. This means that for $n\geqslant n_{1}$, all the $S^n$ have the same
-first term, which is $S^0$: $\forall n\geqslant n_{1},S_0^n=S_0.$
-
-Thus, after the $max(n_{0},n_{1})^{th}$ term, states of $E^n$ and $E$ are
-identical and strategies $S^n$ and $S$ start with the same first term.\newline
-Consequently, states of $G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are equal,
-so, after the $max(n_0, n_1)^{th}$ term, the distance $d$ between these two points is strictly less than 1.\newline
-\noindent We now prove that the distance between $\left(
-G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is convergent to
-0. Let $\varepsilon >0$. \medskip
-\begin{itemize}
-\item If $\varepsilon \geqslant 1$, we see that the distance
-between $\left( G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is
-strictly less than 1 after the $max(n_{0},n_{1})^{th}$ term (same state).
-\medskip
-\item If $\varepsilon <1$, then $\exists k\in \mathds{N},10^{-k}\geqslant
-\varepsilon > 10^{-(k+1)}$. But $d_{s}(S^n,S)$ converges to 0, so
-\begin{equation*}
-\exists n_{2}\in \mathds{N},\forall n\geqslant
-n_{2},d_{s}(S^n,S)<10^{-(k+2)},
-\end{equation*}%
-thus after $n_{2}$, the $k+2$ first terms of $S^n$ and $S$ are equal.
-\end{itemize}
-\noindent As a consequence, the $k+1$ first entries of the strategies of $%
-G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are the same ($G_{f}$ is a shift of strategies) and due to the definition of $d_{s}$, the floating part of
-the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $%
-10^{-(k+1)}\leqslant \varepsilon $.
-
-In conclusion,
-%%RAPH : ici j'ai rajouté une ligne
-$
-\forall \varepsilon >0,$ $\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N}
-,$ $\forall n\geqslant N_{0},$
-$ d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right)
-\leqslant \varepsilon .
-$
-$G_{f}$ is consequently continuous.
-\end{proof}
-
-
-It is now possible to study the topological behavior of the general chaotic
-iterations. We will prove that,
-
-\begin{theorem}
-\label{t:chaos des general}
- The general chaotic iterations defined on Equation~\ref{general CIs} satisfy
-the Devaney's property of chaos.
-\end{theorem}
-
-Let us firstly prove the following lemma.
-
-\begin{lemma}[Strong transitivity]
-\label{strongTrans}
- For all couples $X,Y \in \mathcal{X}$ and any neighborhood $V$ of $X$, we can
-find $n \in \mathds{N}^*$ and $X' \in V$ such that $G^n(X')=Y$.
-\end{lemma}
-
-\begin{proof}
- Let $X=(S,E)$, $\varepsilon>0$, and $k_0 = \lfloor log_{10}(\varepsilon)+1 \rfloor$.
-Any point $X'=(S',E')$ such that $E'=E$ and $\forall k \leqslant k_0, S'^k=S^k$,
-are in the open ball $\mathcal{B}\left(X,\varepsilon\right)$. Let us define
-$\check{X} = \left(\check{S},\check{E}\right)$, where $\check{X}= G^{k_0}(X)$.
-We denote by $s\subset \llbracket 1; \mathsf{N} \rrbracket$ the set of coordinates
-that are different between $\check{E}$ and the state of $Y$. Thus each point $X'$ of
-the form $(S',E')$ where $E'=E$ and $S'$ starts with
-$(S^0, S^1, \hdots, S^{k_0},s,\hdots)$, verifies the following properties:
-\begin{itemize}
- \item $X'$ is in $\mathcal{B}\left(X,\varepsilon\right)$,
- \item the state of $G_f^{k_0+1}(X')$ is the state of $Y$.
-\end{itemize}
-Finally the point $\left(\left(S^0, S^1, \hdots, S^{k_0},s,s^0, s^1, \hdots\right); E\right)$,
-where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties
-claimed in the lemma.
-\end{proof}
-
-We can now prove the Theorem~\ref{t:chaos des general}.
-
-\begin{proof}[Theorem~\ref{t:chaos des general}]
-Firstly, strong transitivity implies transitivity.
-
-Let $(S,E) \in\mathcal{X}$ and $\varepsilon >0$. To
-prove that $G_f$ is regular, it is sufficient to prove that
-there exists a strategy $\tilde S$ such that the distance between
-$(\tilde S,E)$ and $(S,E)$ is less than $\varepsilon$, and such that
-$(\tilde S,E)$ is a periodic point.
-
-Let $t_1=\lfloor-\log_{10}(\varepsilon)\rfloor$, and let $E'$ be the
-configuration that we obtain from $(S,E)$ after $t_1$ iterations of
-$G_f$. As $G_f$ is strongly transitive, there exists a strategy $S'$
-and $t_2\in\mathds{N}$ such
-that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$.
-
-Consider the strategy $\tilde S$ that alternates the first $t_1$ terms
-of $S$ and the first $t_2$ terms of $S'$:
-%%RAPH : j'ai coupé la ligne en 2
-$$\tilde
-S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,$$$$\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It
-is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after
-$t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic
-point. Since $\tilde S_t=S_t$ for $t<t_1$, by the choice of $t_1$, we
-have $d((S,E),(\tilde S,E))<\epsilon$.
-\end{proof}
-
-
-\begin{color}{red}
-\section{Improving Statistical Properties Using Chaotic Iterations}
-
-
-\subsection{The CIPRNG family}
-
-Three categories of PRNGs have been derived from chaotic iterations. They are
-recalled in what follows.
-
-\subsubsection{Old CIPRNG}
-
-Let $\mathsf{N} = 4$. Some chaotic iterations are fulfilled to generate a sequence $\left(x^n\right)_{n\in\mathds{N}} \in \left(\mathds{B}^4\right)^\mathds{N}$ of Boolean vectors: the successive states of the iterated system. Some of these vectors are randomly extracted and their components constitute our pseudorandom bit flow~\cite{bgw09:ip}.
-Chaotic iterations are realized as follows. Initial state $x^0 \in \mathds{B}^4$ is a Boolean vector taken as a seed and chaotic strategy $\left(S^n\right)_{n\in\mathds{N}}\in \llbracket 1, 4 \rrbracket^\mathds{N}$ is constructed with $PRNG_2$. Lastly, iterate function $f$ is the vectorial Boolean negation.
-At each iteration, only the $S^n$-th component of state $x^n$ is updated. Finally, some $x^n$ are selected by a sequence $m^n$, provided by a second generator $PRNG_1$, as the pseudorandom bit sequence of our generator.
-
-The basic design procedure of the Old CI generator is summed up in Algorithm~\ref{Chaotic iteration}.
-The internal state is $x$, the output array is $r$. $a$ and $b$ are those computed by $PRNG_1$ and $PRNG_2$.
-
-
-\begin{algorithm}
-\textbf{Input:} the internal state $x$ (an array of 4-bit words)\\
-\textbf{Output:} an array $r$ of 4-bit words
-\begin{algorithmic}[1]
-
-\STATE$a\leftarrow{PRNG_1()}$;
-\STATE$m\leftarrow{a~mod~2+13}$;
-\WHILE{$i=0,\dots,m$}
-\STATE$b\leftarrow{PRNG_2()}$;
-\STATE$S\leftarrow{b~mod~4}$;
-\STATE$x_S\leftarrow{ \overline{x_S}}$;
-\ENDWHILE
-\STATE$r\leftarrow{x}$;
-\STATE return $r$;
-\medskip
-\caption{An arbitrary round of the old CI generator}
-\label{Chaotic iteration}
-\end{algorithmic}
-\end{algorithm}
-
-\subsubsection{New CIPRNG}
-
-The New CI generator is designed by the following process~\cite{bg10:ip}. First of all, some chaotic iterations have to be done to generate a sequence $\left(x^n\right)_{n\in\mathds{N}} \in \left(\mathds{B}^{32}\right)^\mathds{N}$ of Boolean vectors, which are the successive states of the iterated system. Some of these vectors will be randomly extracted and our pseudo-random bit flow will be constituted by their components. Such chaotic iterations are realized as follows. Initial state $x^0 \in \mathds{B}^{32}$ is a Boolean vector taken as a seed and chaotic strategy $\left(S^n\right)_{n\in\mathds{N}}\in \llbracket 1, 32 \rrbracket^\mathds{N}$ is
-an \emph{irregular decimation} of $PRNG_2$ sequence, as described in Algorithm~\ref{Chaotic iteration1}.
-
-Another time, at each iteration, only the $S^n$-th component of state $x^n$ is updated, as follows: $x_i^n = x_i^{n-1}$ if $i \neq S^n$, else $x_i^n = \overline{x_i^{n-1}}$.
