\usepackage{amscd}
\usepackage{moreverb}
\usepackage{commath}
+\usepackage{algorithm2e}
+\usepackage{listings}
\usepackage[standard]{ntheorem}
% Pour mathds : les ensembles IR, IN, etc.
% Pour faire des sous-figures dans les figures
\usepackage{subfigure}
+\usepackage{color}
+
\newtheorem{notation}{Notation}
\newcommand{\X}{\mathcal{X}}
\newcommand{\BN}{\mathds{B}^\mathsf{N}}
\let\sur=\overline
+\newcommand{\alert}[1]{\begin{color}{blue}\textit{#1}\end{color}}
-\title{Efficient generation of pseudo random numbers based on chaotic iterations on GPU}
+\title{Efficient Generation of Pseudo-Random Numbers based on Chaotic Iterations
+on GPU}
\begin{document}
+
+\author{Jacques M. Bahi, Rapha\"{e}l Couturier, and Christophe
+Guyeux, Pierre-Cyrille Heam\thanks{Authors in alphabetic order}}
+
\maketitle
\begin{abstract}
-This is the abstract
+In this paper we present a new pseudo-random numbers generator (PRNG) on
+graphics processing units (GPU). This PRNG is based on chaotic iterations. it
+is proven to be chaotic in the Devanay's formulation. We propose an efficient
+implementation for GPU which succeeds to the {\it BigCrush}, the hardest
+batteries of test of TestU01. Experimentations show that this PRNG can generate
+about 20 billions of random numbers per second on Tesla C1060 and NVidia GTX280
+cards.
+
+
\end{abstract}
\section{Introduction}
-Interet des itérations chaotiques pour générer des nombre alea\\
-Interet de générer des nombres alea sur GPU
-...
+Random numbers are used in many scientific applications and simulations. On
+finite state machines, as computers, it is not possible to generate random
+numbers but only pseudo-random numbers. In practice, a good pseudo-random numbers
+generator (PRNG) needs to verify some features to be used by scientists. It is
+important to be able to generate pseudo-random numbers efficiently, the
+generation needs to be reproducible and a PRNG needs to satisfy many usual
+statistical properties. Finally, from our point a view, it is essential to prove
+that a PRNG is chaotic. Concerning the statistical tests, TestU01 is the
+best-known public-domain statistical testing package. So we use it for all our
+PRNGs, especially the {\it BigCrush} which provides the largest serie of tests.
+Concerning the chaotic properties, Devaney~\cite{Devaney} proposed a common
+mathematical formulation of chaotic dynamical systems.
+
+In a previous work~\cite{bgw09:ip} we have proposed a new familly of chaotic
+PRNG based on chaotic iterations. We have proven that these PRNGs are
+chaotic in the Devaney's sense. In this paper we propose a faster version which
+is also proven to be chaotic.
+
+Although graphics processing units (GPU) was initially designed to accelerate
+the manipulation of images, they are nowadays commonly used in many scientific
+applications. Therefore, it is important to be able to generate pseudo-random
+numbers inside a GPU when a scientific application runs in a GPU. That is why we
+also provide an efficient PRNG for GPU respecting based on IC. Such devices
+allows us to generated almost 20 billions of random numbers per second.
+
+In order to establish that our PRNGs are chaotic according to the Devaney's
+formulation, we extend what we have proposed in~\cite{guyeux10}.
+
+The rest of this paper is organised as follows. In Section~\ref{section:related
+ works} we review some GPU implementions of PRNG. Section~\ref{section:BASIC
+ RECALLS} gives some basic recalls on Devanay's formation of chaos and chaotic
+iterations. In Section~\ref{sec:pseudo-random} the proof of chaos of our PRNGs
+is studied. Section~\ref{sec:efficient prng} presents an efficient
+implementation of our chaotic PRNG on a CPU. Section~\ref{sec:efficient prng
+ gpu} describes the GPU implementation of our chaotic PRNG. In
+Section~\ref{sec:experiments} some experimentations are presented.
+ Finally, we give a conclusion and some perspectives.
+
+
+
+
+\section{Related works on GPU based PRNGs}
+\label{section:related works}
+In the litterature many authors have work on defining GPU based PRNGs. We do not
+want to be exhaustive and we just give the most significant works from our point
+of view. When authors mention the number of random numbers generated per second
+we mention it. We consider that a million numbers per second corresponds to
+1MSample/s and than a billion numbers per second corresponds to 1GSample/s.
+
+In \cite{Pang:2008:cec}, the authors define a PRNG based on cellular automata
+which does not require high precision integer arithmetics nor bitwise
+operations. There is no mention of statistical tests nor proof that this PRNG is
+chaotic. Concerning the speed of generation, they can generate about
+3.2MSample/s on a GeForce 7800 GTX GPU (which is quite old now).
+
+In \cite{ZRKB10}, the authors propose different versions of efficient GPU PRNGs
+based on Lagged Fibonacci, Hybrid Taus or Hybrid Taus. They have used these
+PRNGs for Langevin simulations of biomolecules fully implemented on
+GPU. Performance of the GPU versions are far better than those obtained with a
+CPU and these PRNGs succeed to pass the {\it BigCrush} test of TestU01. There is
+no mention that their PRNGs have chaos mathematical properties.
+
+
+Authors of~\cite{conf/fpga/ThomasHL09} have studied the implementation of some
+PRNGs on diferrent computing architectures: CPU, field-programmable gate array
+(FPGA), GPU and massively parallel processor. This study is interesting because
+it shows the performance of the same PRNGs on different architeture. For
+example, the FPGA is globally the fastest architecture and it is also the
+efficient one because it provides the fastest number of generated random numbers
+per joule. Concerning the GPU, authors can generate betweend 11 and 16GSample/s
+with a GTX 280 GPU. The drawback of this work is that those PRNGs only succeed
+the {\it Crush} test which is easier than the {\it Big Crush} test.
+
+Cuda has developped a library for the generation of random numbers called
+Curand~\cite{curand11}. Several PRNGs are implemented:
+Xorwow~\cite{Marsaglia2003} and some variants of Sobol. Some tests report that
+the fastest version provides 15GSample/s on the new Fermi C2050 card. Their
+PRNGs fail to succeed the whole tests of TestU01 on only one test.
+\newline
+\newline
+To the best of our knowledge no GPU implementation have been proven to have chaotic properties.
+
+\section{Basic Recalls}
+\label{section:BASIC RECALLS}
+This section is devoted to basic definitions and terminologies in the fields of
+topological chaos and chaotic iterations.
+\subsection{Devaney's Chaotic Dynamical Systems}
+
+In the sequel $S^{n}$ denotes the $n^{th}$ term of a sequence $S$ and $V_{i}$
+denotes the $i^{th}$ component of a vector $V$. $f^{k}=f\circ ...\circ f$
+is for the $k^{th}$ composition of a function $f$. Finally, the following
+notation is used: $\llbracket1;N\rrbracket=\{1,2,\hdots,N\}$.
+
+
+Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f :
+\mathcal{X} \rightarrow \mathcal{X}$.
-\section{Chaotic iterations}
+\begin{definition}
+$f$ is said to be \emph{topologically transitive} if, for any pair of open sets
+$U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq
+\varnothing$.
+\end{definition}
-Présentation des itérations chaotiques
+\begin{definition}
+An element $x$ is a \emph{periodic point} for $f$ of period $n\in \mathds{N}^*$
+if $f^{n}(x)=x$.% The set of periodic points of $f$ is denoted $Per(f).$
+\end{definition}
+\begin{definition}
+$f$ is said to be \emph{regular} on $(\mathcal{X}, \tau)$ if the set of periodic
+points for $f$ is dense in $\mathcal{X}$: for any point $x$ in $\mathcal{X}$,
+any neighborhood of $x$ contains at least one periodic point (without
+necessarily the same period).
+\end{definition}
-\section{The phase space is an interval of the real line}
+\begin{definition}[Devaney's formulation of chaos~\cite{Devaney}]
+$f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and
+topologically transitive.
+\end{definition}
-\subsection{Toward a topological semiconjugacy}
+The chaos property is strongly linked to the notion of ``sensitivity'', defined
+on a metric space $(\mathcal{X},d)$ by:
-In what follows, our intention is to establish, by using a topological semiconjugacy, that chaotic iterations over $\mathcal{X}$ can be described as iterations on a real interval. To do so, we must firstly introduce some notations and terminologies.
+\begin{definition}
+\label{sensitivity} $f$ has \emph{sensitive dependence on initial conditions}
+if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any
+neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that
+$d\left(f^{n}(x), f^{n}(y)\right) >\delta $.
-Let $\mathcal{S}_\mathsf{N}$ be the set of sequences belonging into $\llbracket 1; \mathsf{N}\rrbracket$ and $\mathcal{X}_{\mathsf{N}} = \mathcal{S}_\mathsf{N} \times \B^\mathsf{N}$.
+$\delta$ is called the \emph{constant of sensitivity} of $f$.
+\end{definition}
+Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is
+chaotic and $(\mathcal{X}, d)$ is a metric space, then $f$ has the property of
+sensitive dependence on initial conditions (this property was formerly an
+element of the definition of chaos). To sum up, quoting Devaney
+in~\cite{Devaney}, a chaotic dynamical system ``is unpredictable because of the
+sensitive dependence on initial conditions. It cannot be broken down or
+simplified into two subsystems which do not interact because of topological
+transitivity. And in the midst of this random behavior, we nevertheless have an
+element of regularity''. Fundamentally different behaviors are consequently
+possible and occur in an unpredictable way.
-\begin{definition}
-The function $\varphi: \mathcal{S}_{10} \times\mathds{B}^{10} \rightarrow \big[ 0, 2^{10} \big[$ is defined by:
-$$
-\begin{array}{cccl}
-\varphi: & \mathcal{X}_{10} = \mathcal{S}_{10} \times\mathds{B}^{10}& \longrightarrow & \big[ 0, 2^{10} \big[ \\
- & (S,E) = \left((S^0, S^1, \hdots ); (E_0, \hdots, E_9)\right) & \longmapsto & \varphi \left((S,E)\right)
-\end{array}
-$$
-\noindent where $\varphi\left((S,E)\right)$ is the real number:
-\begin{itemize}
-\item whose integral part $e$ is $\displaystyle{\sum_{k=0}^9 2^{9-k} E_k}$, that is, the binary digits of $e$ are $E_0 ~ E_1 ~ \hdots ~ E_9$.
-\item whose decimal part $s$ is equal to $s = 0,S^0~ S^1~ S^2~ \hdots = \sum_{k=1}^{+\infty} 10^{-k} S^{k-1}.$
-\end{itemize}
-\end{definition}
+\subsection{Chaotic Iterations}
+\label{sec:chaotic iterations}
-$\varphi$ realizes the association between a point of $\mathcal{X}_{10}$ and a real number into $\big[ 0, 2^{10} \big[$. We must now translate the chaotic iterations $\Go$ on this real interval. To do so, two intermediate functions over $\big[ 0, 2^{10} \big[$ must be introduced:
+Let us consider a \emph{system} with a finite number $\mathsf{N} \in
+\mathds{N}^*$ of elements (or \emph{cells}), so that each cell has a
+Boolean \emph{state}. Having $\mathsf{N}$ Boolean values for these
+ cells leads to the definition of a particular \emph{state of the
+system}. A sequence which elements belong to $\llbracket 1;\mathsf{N}
+\rrbracket $ is called a \emph{strategy}. The set of all strategies is
+denoted by $\llbracket 1, \mathsf{N} \rrbracket^\mathds{N}.$
\begin{definition}
-\label{def:e et s}
-Let $x \in \big[ 0, 2^{10} \big[$ and:
-\begin{itemize}
-\item $e_0, \hdots, e_9$ the binary digits of the integral part of $x$: $\displaystyle{\lfloor x \rfloor = \sum_{k=0}^{9} 2^{9-k} e_k}$.
-\item $(s^k)_{k\in \mathds{N}}$ the digits of $x$, where the chosen decimal decomposition of $x$ is the one that does not have an infinite number of 9:
-$\displaystyle{x = \lfloor x \rfloor + \sum_{k=0}^{+\infty} s^k 10^{-k-1}}$.
-\end{itemize}
-$e$ and $s$ are thus defined as follows:
-$$
-\begin{array}{cccl}
-e: & \big[ 0, 2^{10} \big[ & \longrightarrow & \mathds{B}^{10} \\
- & x & \longmapsto & (e_0, \hdots, e_9)
-\end{array}
-$$
-\noindent and
-$$
-\begin{array}{cccl}
-s: & \big[ 0, 2^{10} \big[ & \longrightarrow & \llbracket 0, 9 \rrbracket^{\mathds{N}} \\
- & x & \longmapsto & (s^k)_{k \in \mathds{N}}
-\end{array}
-$$
+\label{Def:chaotic iterations}
+The set $\mathds{B}$ denoting $\{0,1\}$, let
+$f:\mathds{B}^{\mathsf{N}}\longrightarrow \mathds{B}^{\mathsf{N}}$ be
+a function and $S\in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}$ be a ``strategy''. The so-called
+\emph{chaotic iterations} are defined by $x^0\in
+\mathds{B}^{\mathsf{N}}$ and
+\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 }S^n\neq i \\
+ \left(f(x^{n-1})\right)_{S^n} & \text{ if }S^n=i.
+\end{array}\right.
+\end{equation}
\end{definition}
-We are now able to define the function $g$, whose goal is to translate the chaotic iterations $\Go$ on an interval of $\mathds{R}$.
+In other words, at the $n^{th}$ iteration, only the $S^{n}-$th cell is
+\textquotedblleft iterated\textquotedblright . Note that in a more
+general formulation, $S^n$ can be a subset of components and
+$\left(f(x^{n-1})\right)_{S^{n}}$ can be replaced by
+$\left(f(x^{k})\right)_{S^{n}}$, where $k<n$, describing for example,
+delays transmission~\cite{Robert1986,guyeux10}. Finally, let us remark that
+the term ``chaotic'', in the name of these iterations, has \emph{a
+priori} no link with the mathematical theory of chaos, presented above.
+
+
+Let us now recall how to define a suitable metric space where chaotic iterations
+are continuous. For further explanations, see, e.g., \cite{guyeux10}.
+
+Let $\delta $ be the \emph{discrete Boolean metric}, $\delta
+(x,y)=0\Leftrightarrow x=y.$ Given a function $f$, define the function:
+\begin{equation}
+\begin{array}{lrll}
+F_{f}: & \llbracket1;\mathsf{N}\rrbracket\times \mathds{B}^{\mathsf{N}} &
+\longrightarrow & \mathds{B}^{\mathsf{N}} \\
+& (k,E) & \longmapsto & \left( E_{j}.\delta (k,j)+f(E)_{k}.\overline{\delta
+(k,j)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},%
+\end{array}%
+\end{equation}%
+\noindent where + and . are the Boolean addition and product operations.
+Consider the phase space:
+\begin{equation}
+\mathcal{X} = \llbracket 1 ; \mathsf{N} \rrbracket^\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}
+\end{equation}
+\noindent where $\sigma$ is the \emph{shift} function defined by $\sigma
+(S^{n})_{n\in \mathds{N}}\in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}\longrightarrow (S^{n+1})_{n\in
+\mathds{N}}\in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}$ and $i$ is the \emph{initial function}
+$i:(S^{n})_{n\in \mathds{N}} \in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}\longrightarrow S^{0}\in \llbracket
+1;\mathsf{N}\rrbracket$. Then the chaotic iterations proposed in
+Definition \ref{Def:chaotic iterations} can be described by the following iterations:
+\begin{equation}
+\left\{
+\begin{array}{l}
+X^0 \in \mathcal{X} \\
+X^{k+1}=G_{f}(X^k).%
+\end{array}%
+\right.
+\end{equation}%
+
+With this formulation, a shift function appears as a component of chaotic
+iterations. The shift function is a famous example of a chaotic
+map~\cite{Devaney} but its presence is not sufficient enough to claim $G_f$ as
+chaotic.
+To study this claim, a new distance between two points $X = (S,E), Y =
+(\check{S},\check{E})\in
+\mathcal{X}$ has been introduced in \cite{guyeux10} as follows:
+\begin{equation}
+d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}),
+\end{equation}
+\noindent where
+\begin{equation}
+\left\{
+\begin{array}{lll}
+\displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}%
+}\delta (E_{k},\check{E}_{k})}, \\
+\displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}%
+\sum_{k=1}^{\infty }\dfrac{|S^k-\check{S}^k|}{10^{k}}}.%
+\end{array}%
+\right.
+\end{equation}
-\begin{definition}
-$g:\big[ 0, 2^{10} \big[ \longrightarrow \big[ 0, 2^{10} \big[$ is defined by:
-$$
-\begin{array}{cccl}
-g: & \big[ 0, 2^{10} \big[ & \longrightarrow & \big[ 0, 2^{10} \big[ \\
-& \\
- & x & \longmapsto & g(x)
-\end{array}
-$$
-\noindent where g(x) is the real number of $\big[ 0, 2^{10} \big[$ defined bellow:
+
+This new distance has been introduced to satisfy the following requirements.
\begin{itemize}
-\item its integral part has a binary decomposition equal to $e_0', \hdots, e_9'$, with:
-$$
-e_i' = \left\{
-\begin{array}{ll}
-e(x)_i & \textrm{ if } i \neq s^0\\
-e(x)_i + 1 \textrm{ (mod 2)} & \textrm{ if } i = s^0\\
-\end{array}
-\right.
-$$
-\item whose decimal part is $s(x)^1, s(x)^2, \hdots$
+\item When the number of different cells between two systems is increasing, then
+their distance should increase too.
+\item In addition, if two systems present the same cells and their respective
+strategies start with the same terms, then the distance between these two points
+must be small because the evolution of the two systems will be the same for a
+while. Indeed, the two dynamical systems start with the same initial condition,
+use the same update function, and as strategies are the same for a while, then
+components that are updated are the same too.
\end{itemize}
-\end{definition}
+The distance presented above follows these recommendations. Indeed, if the floor
+value $\lfloor d(X,Y)\rfloor $ is equal to $n$, then the systems $E, \check{E}$
+differ in $n$ cells ($d_e$ is indeed the Hamming distance). In addition, $d(X,Y) - \lfloor d(X,Y) \rfloor $ is a
+measure of the differences between strategies $S$ and $\check{S}$. More
+precisely, this floating part is less than $10^{-k}$ if and only if the first
+$k$ terms of the two strategies are equal. Moreover, if the $k^{th}$ digit is
+nonzero, then the $k^{th}$ terms of the two strategies are different.
+The impact of this choice for a distance will be investigate at the end of the document.
-\bigskip
+Finally, it has been established in \cite{guyeux10} that,
+\begin{proposition}
+Let $f$ be a map from $\mathds{B}^\mathsf{N}$ to itself. Then $G_{f}$ is continuous in
+the metric space $(\mathcal{X},d)$.
+\end{proposition}
-In other words, if $x = \displaystyle{\sum_{k=0}^{9} 2^{9-k} e_k + \sum_{k=0}^{+\infty} s^{k} ~10^{-k-1}}$, then: $$g(x) = \displaystyle{\sum_{k=0}^{9} 2^{9-k} (e_k + \delta(k,s^0) \textrm{ (mod 2)}) + \sum_{k=0}^{+\infty} s^{k+1} 10^{-k-1}}.$$
+The chaotic property of $G_f$ has been firstly established for the vectorial
+Boolean negation $f(x_1,\hdots, x_\mathsf{N}) = (\overline{x_1},\hdots, \overline{x_\mathsf{N}})$ \cite{guyeux10}. To obtain a characterization, we have secondly
+introduced the notion of asynchronous iteration graph recalled bellow.
-\subsection{Defining a metric on $\big[ 0, 2^{10} \big[$}
+Let $f$ be a map from $\mathds{B}^\mathsf{N}$ to itself. The
+{\emph{asynchronous iteration graph}} associated with $f$ is the
+directed graph $\Gamma(f)$ defined by: the set of vertices is
+$\mathds{B}^\mathsf{N}$; for all $x\in\mathds{B}^\mathsf{N}$ and
+$i\in \llbracket1;\mathsf{N}\rrbracket$,
+the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(i,x)$.
+The relation between $\Gamma(f)$ and $G_f$ is clear: there exists a
+path from $x$ to $x'$ in $\Gamma(f)$ if and only if there exists a
+strategy $s$ such that the parallel iteration of $G_f$ from the
+initial point $(s,x)$ reaches the point $x'$.
-Numerous metrics can be defined on the set $\big[ 0, 2^{10} \big[$, the most usual one being the Euclidian distance recalled bellow:
+We have finally proven in \cite{bcgr11:ip} that,
-\begin{notation}
-\index{distance!euclidienne}
-$\Delta$ is the Euclidian distance on $\big[ 0, 2^{10} \big[$, that is, $\Delta(x,y) = |y-x|^2$.
-\end{notation}
+\begin{theorem}
+\label{Th:Caractérisation des IC chaotiques}
+Let $f:\mathds{B}^\mathsf{N}\to\mathds{B}^\mathsf{N}$. $G_f$ is chaotic (according to Devaney)
+if and only if $\Gamma(f)$ is strongly connected.
+\end{theorem}
+
+This result of chaos has lead us to study the possibility to build a
+pseudo-random number generator (PRNG) based on the chaotic iterations.
+As $G_f$, defined on the domain $\llbracket 1 ; \mathsf{N} \rrbracket^{\mathds{N}}
+\times \mathds{B}^\mathsf{N}$, is build from Boolean networks $f : \mathds{B}^\mathsf{N}
+\rightarrow \mathds{B}^\mathsf{N}$, we can preserve the theoretical properties on $G_f$
+during implementations (due to the discrete nature of $f$). It is as if
+$\mathds{B}^\mathsf{N}$ represents the memory of the computer whereas $\llbracket 1 ; \mathsf{N}
+\rrbracket^{\mathds{N}}$ is its input stream (the seeds, for instance).
+
+\section{Application to Pseudo-Randomness}
+\label{sec:pseudo-random}
+\subsection{A First Pseudo-Random Number Generator}
+
+We have proposed in~\cite{bgw09:ip} a new family of generators that receives
+two PRNGs as inputs. These two generators are mixed with chaotic iterations,
+leading thus to a new PRNG that improves the statistical properties of each
+generator taken alone. Furthermore, our generator
+possesses various chaos properties that none of the generators used as input
+present.
+
+\begin{algorithm}[h!]
+%\begin{scriptsize}
+\KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$
+($n$ bits)}
+\KwOut{a configuration $x$ ($n$ bits)}
+$x\leftarrow x^0$\;
+$k\leftarrow b + \textit{XORshift}(b)$\;
+\For{$i=0,\dots,k$}
+{
+$s\leftarrow{\textit{XORshift}(n)}$\;
+$x\leftarrow{F_f(s,x)}$\;
+}
+return $x$\;
+%\end{scriptsize}
+\caption{PRNG with chaotic functions}
+\label{CI Algorithm}
+\end{algorithm}
+
+\begin{algorithm}[h!]
+\KwIn{the internal configuration $z$ (a 32-bit word)}
+\KwOut{$y$ (a 32-bit word)}
+$z\leftarrow{z\oplus{(z\ll13)}}$\;
+$z\leftarrow{z\oplus{(z\gg17)}}$\;
+$z\leftarrow{z\oplus{(z\ll5)}}$\;
+$y\leftarrow{z}$\;
+return $y$\;
\medskip
+\caption{An arbitrary round of \textit{XORshift} algorithm}
+\label{XORshift}
+\end{algorithm}
-This Euclidian distance does not reproduce exactly the notion of proximity induced by our first distance $d$ on $\X$. Indeed $d$ is finer than $\Delta$. This is the reason why we have to introduce the following metric:
-\begin{definition}
-Let $x,y \in \big[ 0, 2^{10} \big[$.
-$D$ denotes the function from $\big[ 0, 2^{10} \big[^2$ to $\mathds{R}^+$ defined by: $D(x,y) = D_e\left(e(x),e(y)\right) + D_s\left(s(x),s(y)\right)$, where:
-\begin{center}
-$\displaystyle{D_e(E,\check{E}) = \sum_{k=0}^\mathsf{9} \delta (E_k, \check{E}_k)}$, ~~and~ $\displaystyle{D_s(S,\check{S}) = \sum_{k = 1}^\infty \dfrac{|S^k-\check{S}^k|}{10^k}}$.
-\end{center}
-\end{definition}
+
+This generator is synthesized in Algorithm~\ref{CI Algorithm}.
+It takes as input: a function $f$;
+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 returns 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.
+
+
+We have proven in \cite{bcgr11:ip} that,
+\begin{theorem}
+ Let $f: \mathds{B}^{n} \rightarrow \mathds{B}^{n}$, $\Gamma(f)$ its
+ iteration graph, $\check{M}$ its adjacency
+ matrix and $M$ a $n\times n$ matrix defined as in the previous lemma.
+ If $\Gamma(f)$ is strongly connected, then
+ the output of the PRNG detailed in Algorithm~\ref{CI Algorithm} follows
+ a law that tends to the uniform distribution
+ if and only if $M$ is a double stochastic matrix.
+\end{theorem}
+
+This former generator as successively passed various batteries of statistical tests, as the NIST tests~\cite{bcgr11:ip}.
+
+\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 rewritten 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} for
+the fact that, 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}, 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 pseudo-random 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:
+
+\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{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:
+\begin{equation}
+\begin{array}{lrll}
+F_{f}: & \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} &
+\longrightarrow & \mathds{B}^{\mathsf{N}} \\
+& (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}
+\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}%
+
+Another time, 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
+\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 another time 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}
-$D$ is a distance on $\big[ 0, 2^{10} \big[$.
+The function $d$ defined in Eq.~\ref{nouveau d} is a metric on $\mathcal{X}$.
\end{proposition}
\begin{proof}
-The three axioms defining a distance must be checked.
-\begin{itemize}
-\item $D \geqslant 0$, because everything is positive in its definition. If $D(x,y)=0$, then $D_e(x,y)=0$, so the integral parts of $x$ and $y$ are equal (they have the same binary decomposition). Additionally, $D_s(x,y) = 0$, then $\forall k \in \mathds{N}^*, s(x)^k = s(y)^k$. In other words, $x$ and $y$ have the same $k-$th decimal digit, $\forall k \in \mathds{N}^*$. And so $x=y$.
-\item $D(x,y)=D(y,x)$.
-\item Finally, the triangular inequality is obtained due to the fact that both $\delta$ and $\Delta(x,y)=|x-y|$ satisfy it.
-\end{itemize}
+ $d_e$ is the Hamming distance. We will prove that $d_s$ is a distance
+too, thus $d$ will be a distance as sum of two distances.
+ \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}
-The convergence of sequences according to $D$ is not the same than the usual convergence related to the Euclidian metric. For instance, if $x^n \to x$ according to $D$, then necessarily the integral part of each $x^n$ is equal to the integral part of $x$ (at least after a given threshold), and the decimal part of $x^n$ corresponds to the one of $x$ ``as far as required''.
-To illustrate this fact, a comparison between $D$ and the Euclidian distance is given Figure \ref{fig:comparaison de distances}. These illustrations show that $D$ is richer and more refined than the Euclidian distance, and thus is more precise.
-
-
-\begin{figure}[t]
-\begin{center}
- \subfigure[Function $x \to dist(x;1,234) $ on the interval $(0;5)$.]{\includegraphics[scale=.35]{DvsEuclidien.pdf}}\quad
- \subfigure[Function $x \to dist(x;3) $ on the interval $(0;5)$.]{\includegraphics[scale=.35]{DvsEuclidien2.pdf}}
-\end{center}
-\caption{Comparison between $D$ (in blue) and the Euclidian distane (in green).}
-\label{fig:comparaison de distances}
-\end{figure}
+Before being able to study the topological behavior of the general
+chaotic iterations, we must firstly 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 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 $.\bigskip \newline
+In conclusion,
+$$
+\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}
-\subsection{The semiconjugacy}
-It is now possible to define a topological semiconjugacy between $\mathcal{X}$ and an interval of $\mathds{R}$:
+It is now possible to study the topological behavior of the general chaotic
+iterations. We will prove that,
\begin{theorem}
-Chaotic iterations on the phase space $\mathcal{X}$ are simple iterations on $\mathds{R}$, which is illustrated by the semiconjugacy of the diagram bellow:
-\begin{equation*}
-\begin{CD}
-\left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right) @>G_{f_0}>> \left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right)\\
- @V{\varphi}VV @VV{\varphi}V\\
-\left( ~\big[ 0, 2^{10} \big[, D~\right) @>>g> \left(~\big[ 0, 2^{10} \big[, D~\right)
-\end{CD}
-\end{equation*}
+\label{t:chaos des general}
+ The general chaotic iterations defined on Equation~\ref{general CIs} satisfy
+the Devaney's property of chaos.
\end{theorem}
-\begin{proof}
-$\varphi$ has been constructed in order to be continuous and onto.
-\end{proof}
-
-In other words, $\mathcal{X}$ is approximately equal to $\big[ 0, 2^\mathsf{N} \big[$.
+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'$: $$\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}
-\section{Efficient prng based on chaotic iterations}
-On parle du séquentiel avec des nombres 64 bits\\
-Faire le lien avec le paragraphe précédent (je considère que la stratégie s'appelle $S^i$\\
+\section{Efficient PRNG based on Chaotic Iterations}
+\label{sec:efficient prng}
In order to implement efficiently a PRNG based on chaotic iterations it is
possible to improve previous works [ref]. One solution consists in considering
-that the strategy used $S^i$ contains all the bits for which the negation is
-achieved out. Then instead of applying the negation on these bits we can simply
-apply the xor operator between the current number and the strategy $S^i$. In
+that the strategy used contains all the bits for which the negation is
+achieved out. Then in order to apply the negation on these bits we can simply
+apply the xor operator between the current number and the strategy. In
order to obtain the strategy we also use a classical PRNG.
+Here is an example with 16-bits numbers showing how the bitwise operations
+are
+applied. Suppose that $x$ and the strategy $S^i$ are defined in binary mode.
+Then the following table shows the result of $x$ xor $S^i$.
+$$
+\begin{array}{|cc|cccccccccccccccc|}
+\hline
+x &=&1&0&1&1&1&0&1&0&1&0&0&1&0&0&1&0\\
+\hline
+S^i &=&0&1&1&0&0&1&1&0&1&1&1&0&0&1&1&1\\
+\hline
+x \oplus S^i&=&1&1&0&1&1&1&0&0&0&1&1&1&0&1&0&1\\
+\hline
+
+\hline
+ \end{array}
+$$
+
+
+
+
+
+\lstset{language=C,caption={C code of the sequential chaotic iterations based
+PRNG},label=algo:seqCIprng}
+\begin{lstlisting}
+unsigned int CIprng() {
+ static unsigned int x = 123123123;
+ unsigned long t1 = xorshift();
+ unsigned long t2 = xor128();
+ unsigned long t3 = xorwow();
+ x = x^(unsigned int)t1;
+ x = x^(unsigned int)(t2>>32);
+ x = x^(unsigned int)(t3>>32);
+ x = x^(unsigned int)t2;
+ x = x^(unsigned int)(t1>>32);
+ x = x^(unsigned int)t3;
+ return x;
+}
+\end{lstlisting}
+
+
+
+
+
+In listing~\ref{algo:seqCIprng} a sequential version of our chaotic iterations
+based PRNG is presented. The xor operator is represented by \textasciicircum.
+This function uses three classical 64-bits PRNG: the \texttt{xorshift}, the
+\texttt{xor128} and the \texttt{xorwow}. In the following, we call them
+xor-like PRNGSs. These three PRNGs are presented in~\cite{Marsaglia2003}. As
+each xor-like PRNG used works with 64-bits and as our PRNG works with 32-bits,
+the use of \texttt{(unsigned int)} selects the 32 least significant bits whereas
+\texttt{(unsigned int)(t3$>>$32)} selects the 32 most significants bits of the
+variable \texttt{t}. So to produce a random number realizes 6 xor operations
+with 6 32-bits numbers produced by 3 64-bits PRNG. This version successes the
+BigCrush of the TestU01 battery~\cite{LEcuyerS07}.
+
+\section{Efficient PRNGs based on chaotic iterations on GPU}
+\label{sec:efficient prng gpu}
+
+In order to benefit from computing power of GPU, a program needs to define
+independent blocks of threads which can be computed simultaneously. In general,
+the larger the number of threads is, the more local memory is used and the less
+branching instructions are used (if, while, ...), the better performance is
+obtained on GPU. So with algorithm \ref{algo:seqCIprng} presented in the
+previous section, it is possible to build a similar program which computes PRNG
+on GPU. In the CUDA~\cite{Nvid10} environment, threads have a local
+identificator, called \texttt{ThreadIdx} relative to the block containing them.
+
+
+\subsection{Naive version for GPU}
+
+From the CPU version, it is possible to obtain a quite similar version for GPU.
+The principe consists in assigning the computation of a PRNG as in sequential to
+each thread of the GPU. Of course, it is essential that the three xor-like
+PRNGs used for our computation have different parameters. So we chose them
+randomly with another PRNG. As the initialisation is performed by the CPU, we
+have chosen to use the ISAAC PRNG~\cite{Jenkins96} to initalize all the
+parameters for the GPU version of our PRNG. The implementation of the three
+xor-like PRNGs is straightforward as soon as their parameters have been
+allocated in the GPU memory. Each xor-like PRNGs used works with an internal
+number $x$ which keeps the last generated random numbers. Other internal
+variables are also used by the xor-like PRNGs. More precisely, the
+implementation of the xor128, the xorshift and the xorwow respectively require
+4, 5 and 6 unsigned long as internal variables.
+
+\begin{algorithm}
+
+\KwIn{InternalVarXorLikeArray: array with internal variables of the 3 xor-like
+PRNGs in global memory\;
+NumThreads: Number of threads\;}
+\KwOut{NewNb: array containing random numbers in global memory}
+\If{threadIdx is concerned by the computation} {
+ retrieve data from InternalVarXorLikeArray[threadIdx] in local variables\;
+ \For{i=1 to n} {
+ compute a new PRNG as in Listing\ref{algo:seqCIprng}\;
+ store the new PRNG in NewNb[NumThreads*threadIdx+i]\;
+ }
+ store internal variables in InternalVarXorLikeArray[threadIdx]\;
+}
+
+\caption{main kernel for the chaotic iterations based PRNG GPU naive version}
+\label{algo:gpu_kernel}
+\end{algorithm}
+
+Algorithm~\ref{algo:gpu_kernel} presents a naive implementation of PRNG using
+GPU. According to the available memory in the GPU and the number of threads
+used simultenaously, the number of random numbers that a thread can generate
+inside a kernel is limited, i.e. the variable \texttt{n} in
+algorithm~\ref{algo:gpu_kernel}. For example, if $100,000$ threads are used and
+if $n=100$\footnote{in fact, we need to add the initial seed (a 32-bits number)}
+then the memory required to store internals variables of xor-like
+PRNGs\footnote{we multiply this number by $2$ in order to count 32-bits numbers}
+and random number of our PRNG is equals to $100,000\times ((4+5+6)\times
+2+(1+100))=1,310,000$ 32-bits numbers, i.e. about $52$Mb.
+
+All the tests performed to pass the BigCrush of TestU01 succeeded. Different
+number of threads, called \texttt{NumThreads} in our algorithm, have been tested
+upto $10$ millions.
+\newline
+\newline
+{\bf QUESTION : on laisse cette remarque, je suis mitigé !!!}
+
+\begin{remark}
+Algorithm~\ref{algo:gpu_kernel} has the advantage to manipulate independent
+PRNGs, so this version is easily usable on a cluster of computer. The only thing
+to ensure is to use a single ISAAC PRNG. For this, a simple solution consists in
+using a master node for the initialization which computes the initial parameters
+for all the differents nodes involves in the computation.
+\end{remark}
+
+\subsection{Improved version for GPU}
+
+As GPU cards using CUDA have shared memory between threads of the same block, it
+is possible to use this feature in order to simplify the previous algorithm,
+i.e., using less than 3 xor-like PRNGs. The solution consists in computing only
+one xor-like PRNG by thread, saving it into shared memory and using the results
+of some other threads in the same block of threads. In order to define which
+thread uses the result of which other one, we can use a permutation array which
+contains the indexes of all threads and for which a permutation has been
+performed. In Algorithm~\ref{algo:gpu_kernel2}, 2 permutations arrays are used.
+The variable \texttt{offset} is computed using the value of
+\texttt{permutation\_size}. Then we can compute \texttt{o1} and \texttt{o2}
+which represent the indexes of the other threads for which the results are used
+by the current thread. In the algorithm, we consider that a 64-bits xor-like
+PRNG is used, that is why both 32-bits parts are used.
+
+This version also succeeds to the {\it BigCrush} batteries of tests.
+
+\begin{algorithm}
+
+\KwIn{InternalVarXorLikeArray: array with internal variables of 1 xor-like PRNGs
+in global memory\;
+NumThreads: Number of threads\;
+tab1, tab2: Arrays containing permutations of size permutation\_size\;}
+
+\KwOut{NewNb: array containing random numbers in global memory}
+\If{threadId is concerned} {
+ retrieve data from InternalVarXorLikeArray[threadId] in local variables including shared memory and x\;
+ offset = threadIdx\%permutation\_size\;
+ o1 = threadIdx-offset+tab1[offset]\;
+ o2 = threadIdx-offset+tab2[offset]\;
+ \For{i=1 to n} {
+ t=xor-like()\;
+ t=t$\oplus$shmem[o1]$\oplus$shmem[o2]\;
+ shared\_mem[threadId]=t\;
+ x = x $\oplus$ t\;
+
+ store the new PRNG in NewNb[NumThreads*threadId+i]\;
+ }
+ store internal variables in InternalVarXorLikeArray[threadId]\;
+}
+
+\caption{main kernel for the chaotic iterations based PRNG GPU efficient
+version}
+\label{algo:gpu_kernel2}
+\end{algorithm}
+
+\subsection{Theoretical Evaluation of the Improved Version}
+
+A run of Algorithm~\ref{algo:gpu_kernel2} consists in three operations having
+the form of Equation~\ref{equation Oplus}, which is equivalent to the iterative
+system of Eq.~\ref{eq:generalIC}. That is, three iterations of the general chaotic
+iterations are realized between two stored values of the PRNG.
+To be certain that we are in the framework of Theorem~\ref{t:chaos des general},
+we must guarantee that this dynamical system iterates on the space
+$\mathcal{X} = \mathcal{P}\left(\llbracket 1, \mathsf{N} \rrbracket\right)^\mathds{N}\times\mathds{B}^\mathsf{N}$.
+The left term $x$ obviously belongs into $\mathds{B}^ \mathsf{N}$.
+To prevent from any flaws of chaotic properties, we must check that each right
+term, corresponding to terms of the strategies, can possibly be equal to any
+integer of $\llbracket 1, \mathsf{N} \rrbracket$.
+
+Such a result is obvious for the two first lines, as for the xor-like(), all the
+integers belonging into its interval of definition can occur at each iteration.
+It can be easily stated for the two last lines by an immediate mathematical
+induction.
+
+Thus Algorithm~\ref{algo:gpu_kernel2} is a concrete realization of the general
+chaotic iterations presented previously, and for this reason, it satisfies the
+Devaney's formulation of a chaotic behavior.
+
+\section{A cryptographically secure prng for GPU}
+
+It is possible to build a cryptographically secure prng based on the previous
+algorithm (algorithm~\ref{algo:gpu_kernel2}). It simply consists in replacing
+the {\it xor-like} algorithm by another cryptographically secure prng. In
+practice, we suggest to use the BBS algorithm~\cite{BBS} which takes the form:
+$$x_{n+1}=x_n^2~ mod~ M$$ where $M$ is the product of two prime numbers. Those
+prime numbers need to be congruent to 3 modulus 4. In practice, this PRNG is
+known to be slow and not efficient for the generation of random numbers. For
+current GPU cards, the modulus operation is the most time consuming
+operation. So in order to obtain quite reasonable performances, it is required
+to use only modulus on 32 bits integer numbers. Consequently $x_n^2$ need to be
+less than $2^{32}$ and the number $M$ need to be less than $2^{16}$. So in
+pratice we can choose prime numbers around 256 that are congruent to 3 modulus
+4. With 32 bits numbers, only the 4 least significant bits of $x_n$ can be
+chosen (the maximum number of undistinguishing is less or equals to
+$log_2(log_2(x_n))$). So to generate a 32 bits number, we need to use 8 times
+the BBS algorithm, with different combinations of $M$ is required.
+
+Currently this PRNG does not succeed to pass all the tests of TestU01.
+
+\section{Experiments}
+\label{sec:experiments}
+
+Different experiments have been performed in order to measure the generation
+speed. We have used a computer equiped with Tesla C1060 NVidia GPU card and an
+Intel Xeon E5530 cadenced at 2.40 GHz for our experiments and we have used
+another one equipped with a less performant CPU and a GeForce GTX 280. Both
+cards have 240 cores.
+
+In Figure~\ref{fig:time_xorlike_gpu} we compare the number of random numbers
+generated per second with the xor-like based PRNG. In this figure, the optimized
+version use the {\it xor64} described in~\cite{Marsaglia2003}. The naive version
+use the three xor-like PRNGs described in Listing~\ref{algo:seqCIprng}. In
+order to obtain the optimal performance we removed the storage of random numbers
+in the GPU memory. This step is time consuming and slows down the random numbers
+generation. Moreover, if one is interested by applications that consume random
+numbers directly when they are generated, their storage are completely
+useless. In this figure we can see that when the number of threads is greater
+than approximately 30,000 upto 5 millions the number of random numbers generated
+per second is almost constant. With the naive version, it is between 2.5 and
+3GSample/s. With the optimized version, it is approximately equals to
+20GSample/s. Finally we can remark that both GPU cards are quite similar. In
+practice, the Tesla C1060 has more memory than the GTX 280 and this memory
+should be of better quality.
+
\begin{figure}[htbp]
\begin{center}
-\fbox{
-\begin{minipage}{14cm}
-unsigned int CIprng() \{\\
- static unsigned int x = 123123123;\\
- unsigned long t1 = xorshift();\\
- unsigned long t2 = xor128();\\
- unsigned long t3 = xorwow();\\
- x = x\textasciicircum (unsigned int)t1;\\
- x = x\textasciicircum (unsigned int)(t2$>>$32);\\
- x = x\textasciicircum (unsigned int)(t3$>>$32);\\
- x = x\textasciicircum (unsigned int)t2;\\
- x = x\textasciicircum (unsigned int)(t1$>>$32);\\
- x = x\textasciicircum (unsigned int)t3;\\
- return x;\\
-\}
-\end{minipage}
-}
+ \includegraphics[scale=.7]{curve_time_xorlike_gpu.pdf}
\end{center}
-\caption{sequential Chaotic Iteration PRNG}
-\label{algo:seqCIprng}
+\caption{Number of random numbers generated per second with the xorlike based PRNG}
+\label{fig:time_xorlike_gpu}
\end{figure}
-In Figure~\ref{algo:seqCIprng} a sequential version of our chaotic iterations
-based PRNG is presented. This version uses three classical 64 bits PRNG: the
-\texttt{xorshift}, the \texttt{xor128} and the \texttt{xorwow}. These three
-PRNGs are presented in~\cite{Marsaglia2003}. As each PRNG used works with
-64-bits and as our PRNG works with 32 bits, the use of \texttt{(unsigned int)}
-selects the 32 least significant bits whereas \texttt{(unsigned int)(t3$>>$32)}
-selects the 32 most significants bits of the variable \texttt{t}. This version
-sucesses the BigCrush of the TestU01 battery [P. L’ecuyer and
- R. Simard. Testu01].
-\section{Efficient prng based on chaotic iterations on GPU}
+In comparison, Listing~\ref{algo:seqCIprng} allows us to generate about
+138MSample/s with only one core of the Xeon E5530.
+
+
+In Figure~\ref{fig:time_bbs_gpu} we highlight the performance of the optimized
+BBS based PRNG on GPU. Performances are less important. On the Tesla C1060 we
+obtain approximately 1.8GSample/s and on the GTX 280 about 1.6GSample/s.
+
+\begin{figure}[htbp]
+\begin{center}
+ \includegraphics[scale=.7]{curve_time_bbs_gpu.pdf}
+\end{center}
+\caption{Number of random numbers generated per second with the BBS based PRNG}
+\label{fig:time_bbs_gpu}
+\end{figure}
+
+Both these experimentations allows us to conclude that it is possible to
+generate a huge number of pseudo-random numbers with the xor-like version and
+about tens times less with the BBS based version. The former version has only
+chaotic properties whereas the latter also has cryptographically properties.
+
+
+%% \section{Cryptanalysis of the Proposed PRNG}
+
+
+%% Mettre ici la preuve de PCH
+
+%\section{The relativity of disorder}
+%\label{sec:de la relativité du désordre}
+
+%In the next two sections, we investigate the impact of the choices that have
+%lead to the definitions of measures in Sections \ref{sec:chaotic iterations} and \ref{deuxième def}.
+
+%\subsection{Impact of the topology's finenesse}
+
+%Let us firstly introduce the following notations.
+
+%\begin{notation}
+%$\mathcal{X}_\tau$ will denote the topological space
+%$\left(\mathcal{X},\tau\right)$, whereas $\mathcal{V}_\tau (x)$ will be the set
+%of all the neighborhoods of $x$ when considering the topology $\tau$ (or simply
+%$\mathcal{V} (x)$, if there is no ambiguity).
+%\end{notation}
+
+
+
+%\begin{theorem}
+%\label{Th:chaos et finesse}
+%Let $\mathcal{X}$ a set and $\tau, \tau'$ two topologies on $\mathcal{X}$ s.t.
+%$\tau'$ is finer than $\tau$. Let $f:\mathcal{X} \to \mathcal{X}$, continuous
+%both for $\tau$ and $\tau'$.
+
+%If $(\mathcal{X}_{\tau'},f)$ is chaotic according to Devaney, then
+%$(\mathcal{X}_\tau,f)$ is chaotic too.
+%\end{theorem}
+
+%\begin{proof}
+%Let us firstly establish the transitivity of $(\mathcal{X}_\tau,f)$.
+
+%Let $\omega_1, \omega_2$ two open sets of $\tau$. Then $\omega_1, \omega_2 \in
+%\tau'$, becaus $\tau'$ is finer than $\tau$. As $f$ is $\tau'-$transitive, we
+%can deduce that $\exists n \in \mathds{N}, \omega_1 \cap f^{(n)}(\omega_2) =
+%\varnothing$. Consequently, $f$ is $\tau-$transitive.
+
+%Let us now consider the regularity of $(\mathcal{X}_\tau,f)$, \emph{i.e.}, for
+%all $x \in \mathcal{X}$, and for all $\tau-$neighborhood $V$ of $x$, there is a
+%periodic point for $f$ into $V$.
+
+%Let $x \in \mathcal{X}$ and $V \in \mathcal{V}_\tau (x)$ a $\tau-$neighborhood
+%of $x$. By definition, $\exists \omega \in \tau, x \in \omega \subset V$.
+
+%But $\tau \subset \tau'$, so $\omega \in \tau'$, and then $V \in
+%\mathcal{V}_{\tau'} (x)$. As $(\mathcal{X}_{\tau'},f)$ is regular, there is a
+%periodic point for $f$ into $V$, and the regularity of $(\mathcal{X}_\tau,f)$ is
+%proven.
+%\end{proof}
+
+%\subsection{A given system can always be claimed as chaotic}
+
+%Let $f$ an iteration function on $\mathcal{X}$ having at least a fixed point.
+%Then this function is chaotic (in a certain way):
+
+%\begin{theorem}
+%Let $\mathcal{X}$ a nonempty set and $f: \mathcal{X} \to \X$ a function having
+%at least a fixed point.
+%Then $f$ is $\tau_0-$chaotic, where $\tau_0$ is the trivial (indiscrete)
+%topology on $\X$.
+%\end{theorem}
+
+
+%\begin{proof}
+%$f$ is transitive when $\forall \omega, \omega' \in \tau_0 \setminus
+%\{\varnothing\}, \exists n \in \mathds{N}, f^{(n)}(\omega) \cap \omega' \neq
+%\varnothing$.
+%As $\tau_0 = \left\{ \varnothing, \X \right\}$, this is equivalent to look for
+%an integer $n$ s.t. $f^{(n)}\left( \X \right) \cap \X \neq \varnothing$. For
+%instance, $n=0$ is appropriate.
+
+%Let us now consider $x \in \X$ and $V \in \mathcal{V}_{\tau_0} (x)$. Then $V =
+%\mathcal{X}$, so $V$ has at least a fixed point for $f$. Consequently $f$ is
+%regular, and the result is established.
+%\end{proof}
+
+
+
+
+%\subsection{A given system can always be claimed as non-chaotic}
+
+%\begin{theorem}
+%Let $\mathcal{X}$ be a set and $f: \mathcal{X} \to \X$.
+%If $\X$ is infinite, then $\left( \X_{\tau_\infty}, f\right)$ is not chaotic
+%(for the Devaney's formulation), where $\tau_\infty$ is the discrete topology.
+%\end{theorem}
+
+%\begin{proof}
+%Let us prove it by contradiction, assuming that $\left(\X_{\tau_\infty},
+%f\right)$ is both transitive and regular.
+
+%Let $x \in \X$ and $\{x\}$ one of its neighborhood. This neighborhood must
+%contain a periodic point for $f$, if we want that $\left(\X_{\tau_\infty},
+%f\right)$ is regular. Then $x$ must be a periodic point of $f$.
+
+%Let $I_x = \left\{ f^{(n)}(x), n \in \mathds{N}\right\}$. This set is finite
+%because $x$ is periodic, and $\mathcal{X}$ is infinite, then $\exists y \in
+%\mathcal{X}, y \notin I_x$.
+
+%As $\left(\X_{\tau_\infty}, f\right)$ must be transitive, for all open nonempty
+%sets $A$ and $B$, an integer $n$ must satisfy $f^{(n)}(A) \cap B \neq
+%\varnothing$. However $\{x\}$ and $\{y\}$ are open sets and $y \notin I_x
+%\Rightarrow \forall n, f^{(n)}\left( \{x\} \right) \cap \{y\} = \varnothing$.
+%\end{proof}
+
+
+
+
+
+
+%\section{Chaos on the order topology}
+%\label{sec: chaos order topology}
+%\subsection{The phase space is an interval of the real line}
+
+%\subsubsection{Toward a topological semiconjugacy}
+
+%In what follows, our intention is to establish, by using a topological
+%semiconjugacy, that chaotic iterations over $\mathcal{X}$ can be described as
+%iterations on a real interval. To do so, we must firstly introduce some
+%notations and terminologies.
+
+%Let $\mathcal{S}_\mathsf{N}$ be the set of sequences belonging into $\llbracket
+%1; \mathsf{N}\rrbracket$ and $\mathcal{X}_{\mathsf{N}} = \mathcal{S}_\mathsf{N}
+%\times \B^\mathsf{N}$.
+
+
+%\begin{definition}
+%The function $\varphi: \mathcal{S}_{10} \times\mathds{B}^{10} \rightarrow \big[
+%0, 2^{10} \big[$ is defined by:
+%\begin{equation}
+% \begin{array}{cccl}
+%\varphi: & \mathcal{X}_{10} = \mathcal{S}_{10} \times\mathds{B}^{10}&
+%\longrightarrow & \big[ 0, 2^{10} \big[ \\
+% & (S,E) = \left((S^0, S^1, \hdots ); (E_0, \hdots, E_9)\right) & \longmapsto &
+%\varphi \left((S,E)\right)
+%\end{array}
+%\end{equation}
+%where $\varphi\left((S,E)\right)$ is the real number:
+%\begin{itemize}
+%\item whose integral part $e$ is $\displaystyle{\sum_{k=0}^9 2^{9-k} E_k}$, that
+%is, the binary digits of $e$ are $E_0 ~ E_1 ~ \hdots ~ E_9$.
+%\item whose decimal part $s$ is equal to $s = 0,S^0~ S^1~ S^2~ \hdots =
+%\sum_{k=1}^{+\infty} 10^{-k} S^{k-1}.$
+%\end{itemize}
+%\end{definition}
+
+
+
+%$\varphi$ realizes the association between a point of $\mathcal{X}_{10}$ and a
+%real number into $\big[ 0, 2^{10} \big[$. We must now translate the chaotic
+%iterations $\Go$ on this real interval. To do so, two intermediate functions
+%over $\big[ 0, 2^{10} \big[$ must be introduced:
+
+
+%\begin{definition}
+%\label{def:e et s}
+%Let $x \in \big[ 0, 2^{10} \big[$ and:
+%\begin{itemize}
+%\item $e_0, \hdots, e_9$ the binary digits of the integral part of $x$:
+%$\displaystyle{\lfloor x \rfloor = \sum_{k=0}^{9} 2^{9-k} e_k}$.
+%\item $(s^k)_{k\in \mathds{N}}$ the digits of $x$, where the chosen decimal
+%decomposition of $x$ is the one that does not have an infinite number of 9:
+%$\displaystyle{x = \lfloor x \rfloor + \sum_{k=0}^{+\infty} s^k 10^{-k-1}}$.
+%\end{itemize}
+%$e$ and $s$ are thus defined as follows:
+%\begin{equation}
+%\begin{array}{cccl}
+%e: & \big[ 0, 2^{10} \big[ & \longrightarrow & \mathds{B}^{10} \\
+% & x & \longmapsto & (e_0, \hdots, e_9)
+%\end{array}
+%\end{equation}
+%and
+%\begin{equation}
+% \begin{array}{cccc}
+%s: & \big[ 0, 2^{10} \big[ & \longrightarrow & \llbracket 0, 9
+%\rrbracket^{\mathds{N}} \\
+% & x & \longmapsto & (s^k)_{k \in \mathds{N}}
+%\end{array}
+%\end{equation}
+%\end{definition}
+
+%We are now able to define the function $g$, whose goal is to translate the
+%chaotic iterations $\Go$ on an interval of $\mathds{R}$.
+
+%\begin{definition}
+%$g:\big[ 0, 2^{10} \big[ \longrightarrow \big[ 0, 2^{10} \big[$ is defined by:
+%\begin{equation}
+%\begin{array}{cccc}
+%g: & \big[ 0, 2^{10} \big[ & \longrightarrow & \big[ 0, 2^{10} \big[ \\
+% & x & \longmapsto & g(x)
+%\end{array}
+%\end{equation}
+%where g(x) is the real number of $\big[ 0, 2^{10} \big[$ defined bellow:
+%\begin{itemize}
+%\item its integral part has a binary decomposition equal to $e_0', \hdots,
+%e_9'$, with:
+% \begin{equation}
+%e_i' = \left\{
+%\begin{array}{ll}
+%e(x)_i & \textrm{ if } i \neq s^0\\
+%e(x)_i + 1 \textrm{ (mod 2)} & \textrm{ if } i = s^0\\
+%\end{array}
+%\right.
+%\end{equation}
+%\item whose decimal part is $s(x)^1, s(x)^2, \hdots$
+%\end{itemize}
+%\end{definition}
+
+%\bigskip
+
+
+%In other words, if $x = \displaystyle{\sum_{k=0}^{9} 2^{9-k} e_k +
+%\sum_{k=0}^{+\infty} s^{k} ~10^{-k-1}}$, then:
+%\begin{equation}
+%g(x) =
+%\displaystyle{\sum_{k=0}^{9} 2^{9-k} (e_k + \delta(k,s^0) \textrm{ (mod 2)}) +
+%\sum_{k=0}^{+\infty} s^{k+1} 10^{-k-1}}.
+%\end{equation}
+
+
+%\subsubsection{Defining a metric on $\big[ 0, 2^{10} \big[$}
+
+%Numerous metrics can be defined on the set $\big[ 0, 2^{10} \big[$, the most
+%usual one being the Euclidian distance recalled bellow:
+
+%\begin{notation}
+%\index{distance!euclidienne}
+%$\Delta$ is the Euclidian distance on $\big[ 0, 2^{10} \big[$, that is,
+%$\Delta(x,y) = |y-x|^2$.
+%\end{notation}
+
+%\medskip
+
+%This Euclidian distance does not reproduce exactly the notion of proximity
+%induced by our first distance $d$ on $\X$. Indeed $d$ is finer than $\Delta$.
+%This is the reason why we have to introduce the following metric:
+
+
+
+%\begin{definition}
+%Let $x,y \in \big[ 0, 2^{10} \big[$.
+%$D$ denotes the function from $\big[ 0, 2^{10} \big[^2$ to $\mathds{R}^+$
+%defined by: $D(x,y) = D_e\left(e(x),e(y)\right) + D_s\left(s(x),s(y)\right)$,
+%where:
+%\begin{center}
+%$\displaystyle{D_e(E,\check{E}) = \sum_{k=0}^\mathsf{9} \delta (E_k,
+%\check{E}_k)}$, ~~and~ $\displaystyle{D_s(S,\check{S}) = \sum_{k = 1}^\infty
+%\dfrac{|S^k-\check{S}^k|}{10^k}}$.
+%\end{center}
+%\end{definition}
+
+%\begin{proposition}
+%$D$ is a distance on $\big[ 0, 2^{10} \big[$.
+%\end{proposition}
+
+%\begin{proof}
+%The three axioms defining a distance must be checked.
+%\begin{itemize}
+%\item $D \geqslant 0$, because everything is positive in its definition. If
+%$D(x,y)=0$, then $D_e(x,y)=0$, so the integral parts of $x$ and $y$ are equal
+%(they have the same binary decomposition). Additionally, $D_s(x,y) = 0$, then
+%$\forall k \in \mathds{N}^*, s(x)^k = s(y)^k$. In other words, $x$ and $y$ have
+%the same $k-$th decimal digit, $\forall k \in \mathds{N}^*$. And so $x=y$.
+%\item $D(x,y)=D(y,x)$.
+%\item Finally, the triangular inequality is obtained due to the fact that both
+%$\delta$ and $\Delta(x,y)=|x-y|$ satisfy it.
+%\end{itemize}
+%\end{proof}
+
+
+%The convergence of sequences according to $D$ is not the same than the usual
+%convergence related to the Euclidian metric. For instance, if $x^n \to x$
+%according to $D$, then necessarily the integral part of each $x^n$ is equal to
+%the integral part of $x$ (at least after a given threshold), and the decimal
+%part of $x^n$ corresponds to the one of $x$ ``as far as required''.
+%To illustrate this fact, a comparison between $D$ and the Euclidian distance is
+%given Figure \ref{fig:comparaison de distances}. These illustrations show that
+%$D$ is richer and more refined than the Euclidian distance, and thus is more
+%precise.
+
+
+%\begin{figure}[t]
+%\begin{center}
+% \subfigure[Function $x \to dist(x;1,234) $ on the interval
+%$(0;5)$.]{\includegraphics[scale=.35]{DvsEuclidien.pdf}}\quad
+% \subfigure[Function $x \to dist(x;3) $ on the interval
+%$(0;5)$.]{\includegraphics[scale=.35]{DvsEuclidien2.pdf}}
+%\end{center}
+%\caption{Comparison between $D$ (in blue) and the Euclidian distane (in green).}
+%\label{fig:comparaison de distances}
+%\end{figure}
+
+
+
+
+%\subsubsection{The semiconjugacy}
+
+%It is now possible to define a topological semiconjugacy between $\mathcal{X}$
+%and an interval of $\mathds{R}$:
+
+%\begin{theorem}
+%Chaotic iterations on the phase space $\mathcal{X}$ are simple iterations on
+%$\mathds{R}$, which is illustrated by the semiconjugacy of the diagram bellow:
+%\begin{equation*}
+%\begin{CD}
+%\left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right) @>G_{f_0}>>
+%\left(~\mathcal{S}_{10} \times\mathds{B}^{10}, d~\right)\\
+% @V{\varphi}VV @VV{\varphi}V\\
+%\left( ~\big[ 0, 2^{10} \big[, D~\right) @>>g> \left(~\big[ 0, 2^{10} \big[,
+%D~\right)
+%\end{CD}
+%\end{equation*}
+%\end{theorem}
+
+%\begin{proof}
+%$\varphi$ has been constructed in order to be continuous and onto.
+%\end{proof}
+
+%In other words, $\mathcal{X}$ is approximately equal to $\big[ 0, 2^\mathsf{N}
+%\big[$.
+
+
+
+
+
+
+%\subsection{Study of the chaotic iterations described as a real function}
+
+
+%\begin{figure}[t]
+%\begin{center}
+% \subfigure[ICs on the interval
+%$(0,9;1)$.]{\includegraphics[scale=.35]{ICs09a1.pdf}}\quad
+% \subfigure[ICs on the interval
+%$(0,7;1)$.]{\includegraphics[scale=.35]{ICs07a95.pdf}}\\
+% \subfigure[ICs on the interval
+%$(0,5;1)$.]{\includegraphics[scale=.35]{ICs05a1.pdf}}\quad
+% \subfigure[ICs on the interval
+%$(0;1)$]{\includegraphics[scale=.35]{ICs0a1.pdf}}
+%\end{center}
+%\caption{Representation of the chaotic iterations.}
+%\label{fig:ICs}
+%\end{figure}
+
+
+
+
+%\begin{figure}[t]
+%\begin{center}
+% \subfigure[ICs on the interval
+%$(510;514)$.]{\includegraphics[scale=.35]{ICs510a514.pdf}}\quad
+% \subfigure[ICs on the interval
+%$(1000;1008)$]{\includegraphics[scale=.35]{ICs1000a1008.pdf}}
+%\end{center}
+%\caption{ICs on small intervals.}
+%\label{fig:ICs2}
+%\end{figure}
+
+%\begin{figure}[t]
+%\begin{center}
+% \subfigure[ICs on the interval
+%$(0;16)$.]{\includegraphics[scale=.3]{ICs0a16.pdf}}\quad
+% \subfigure[ICs on the interval
+%$(40;70)$.]{\includegraphics[scale=.45]{ICs40a70.pdf}}\quad
+%\end{center}
+%\caption{General aspect of the chaotic iterations.}
+%\label{fig:ICs3}
+%\end{figure}
+
+
+%We have written a Python program to represent the chaotic iterations with the
+%vectorial negation on the real line $\mathds{R}$. Various representations of
+%these CIs are given in Figures \ref{fig:ICs}, \ref{fig:ICs2} and \ref{fig:ICs3}.
+%It can be remarked that the function $g$ is a piecewise linear function: it is
+%linear on each interval having the form $\left[ \dfrac{n}{10},
+%\dfrac{n+1}{10}\right[$, $n \in \llbracket 0;2^{10}\times 10 \rrbracket$ and its
+%slope is equal to 10. Let us justify these claims:
+
+%\begin{proposition}
+%\label{Prop:derivabilite des ICs}
+%Chaotic iterations $g$ defined on $\mathds{R}$ have derivatives of all orders on
+%$\big[ 0, 2^{10} \big[$, except on the 10241 points in $I$ defined by $\left\{
+%\dfrac{n}{10} ~\big/~ n \in \llbracket 0;2^{10}\times 10\rrbracket \right\}$.
+
+%Furthermore, on each interval of the form $\left[ \dfrac{n}{10},
+%\dfrac{n+1}{10}\right[$, with $n \in \llbracket 0;2^{10}\times 10 \rrbracket$,
+%$g$ is a linear function, having a slope equal to 10: $\forall x \notin I,
+%g'(x)=10$.
+%\end{proposition}
+
+
+%\begin{proof}
+%Let $I_n = \left[ \dfrac{n}{10}, \dfrac{n+1}{10}\right[$, with $n \in \llbracket
+%0;2^{10}\times 10 \rrbracket$. All the points of $I_n$ have the same integral
+%prat $e$ and the same decimal part $s^0$: on the set $I_n$, functions $e(x)$
+%and $x \mapsto s(x)^0$ of Definition \ref{def:e et s} only depend on $n$. So all
+%the images $g(x)$ of these points $x$:
+%\begin{itemize}
+%\item Have the same integral part, which is $e$, except probably the bit number
+%$s^0$. In other words, this integer has approximately the same binary
+%decomposition than $e$, the sole exception being the digit $s^0$ (this number is
+%then either $e+2^{10-s^0}$ or $e-2^{10-s^0}$, depending on the parity of $s^0$,
+%\emph{i.e.}, it is equal to $e+(-1)^{s^0}\times 2^{10-s^0}$).
+%\item A shift to the left has been applied to the decimal part $y$, losing by
+%doing so the common first digit $s^0$. In other words, $y$ has been mapped into
+%$10\times y - s^0$.
+%\end{itemize}
+%To sum up, the action of $g$ on the points of $I$ is as follows: first, make a
+%multiplication by 10, and second, add the same constant to each term, which is
+%$\dfrac{1}{10}\left(e+(-1)^{s^0}\times 2^{10-s^0}\right)-s^0$.
+%\end{proof}
+
+%\begin{remark}
+%Finally, chaotic iterations are elements of the large family of functions that
+%are both chaotic and piecewise linear (like the tent map).
+%\end{remark}
+
+
+
+%\subsection{Comparison of the two metrics on $\big[ 0, 2^\mathsf{N} \big[$}
+
+%The two propositions bellow allow to compare our two distances on $\big[ 0,
+%2^\mathsf{N} \big[$:
+
+%\begin{proposition}
+%Id: $\left(~\big[ 0, 2^\mathsf{N} \big[,\Delta~\right) \to \left(~\big[ 0,
+%2^\mathsf{N} \big[, D~\right)$ is not continuous.
+%\end{proposition}
+
+%\begin{proof}
+%The sequence $x^n = 1,999\hdots 999$ constituted by $n$ 9 as decimal part, is
+%such that:
+%\begin{itemize}
+%\item $\Delta (x^n,2) \to 0.$
+%\item But $D(x^n,2) \geqslant 1$, then $D(x^n,2)$ does not converge to 0.
+%\end{itemize}
+
+%The sequential characterization of the continuity concludes the demonstration.
+%\end{proof}
+
+
+
+%A contrario:
+
+%\begin{proposition}
+%Id: $\left(~\big[ 0, 2^\mathsf{N} \big[,D~\right) \to \left(~\big[ 0,
+%2^\mathsf{N} \big[, \Delta ~\right)$ is a continuous fonction.
+%\end{proposition}
+
+%\begin{proof}
+%If $D(x^n,x) \to 0$, then $D_e(x^n,x) = 0$ at least for $n$ larger than a given
+%threshold, because $D_e$ only returns integers. So, after this threshold, the
+%integral parts of all the $x^n$ are equal to the integral part of $x$.
+
+%Additionally, $D_s(x^n, x) \to 0$, then $\forall k \in \mathds{N}^*, \exists N_k
+%\in \mathds{N}, n \geqslant N_k \Rightarrow D_s(x^n,x) \leqslant 10^{-k}$. This
+%means that for all $k$, an index $N_k$ can be found such that, $\forall n
+%\geqslant N_k$, all the $x^n$ have the same $k$ firsts digits, which are the
+%digits of $x$. We can deduce the convergence $\Delta(x^n,x) \to 0$, and thus the
+%result.
+%\end{proof}
+
+%The conclusion of these propositions is that the proposed metric is more precise
+%than the Euclidian distance, that is:
+
+%\begin{corollary}
+%$D$ is finer than the Euclidian distance $\Delta$.
+%\end{corollary}
+
+%This corollary can be reformulated as follows:
+
+%\begin{itemize}
+%\item The topology produced by $\Delta$ is a subset of the topology produced by
+%$D$.
+%\item $D$ has more open sets than $\Delta$.
+%\item It is harder to converge for the topology $\tau_D$ inherited by $D$, than
+%to converge with the one inherited by $\Delta$, which is denoted here by
+%$\tau_\Delta$.
+%\end{itemize}
+
+
+%\subsection{Chaos of the chaotic iterations on $\mathds{R}$}
+%\label{chpt:Chaos des itérations chaotiques sur R}
+
+
+
+%\subsubsection{Chaos according to Devaney}
+
+%We have recalled previously that the chaotic iterations $\left(\Go,
+%\mathcal{X}_d\right)$ are chaotic according to the formulation of Devaney. We
+%can deduce that they are chaotic on $\mathds{R}$ too, when considering the order
+%topology, because:
+%\begin{itemize}
+%\item $\left(\Go, \mathcal{X}_d\right)$ and $\left(g, \big[ 0, 2^{10}
+%\big[_D\right)$ are semiconjugate by $\varphi$,
+%\item Then $\left(g, \big[ 0, 2^{10} \big[_D\right)$ is a system chaotic
+%according to Devaney, because the semiconjugacy preserve this character.
+%\item But the topology generated by $D$ is finer than the topology generated by
+%the Euclidian distance $\Delta$ -- which is the order topology.
+%\item According to Theorem \ref{Th:chaos et finesse}, we can deduce that the
+%chaotic iterations $g$ are indeed chaotic, as defined by Devaney, for the order
+%topology on $\mathds{R}$.
+%\end{itemize}
+
+%This result can be formulated as follows.
+
+%\begin{theorem}
+%\label{th:IC et topologie de l'ordre}
+%The chaotic iterations $g$ on $\mathds{R}$ are chaotic according to the
+%Devaney's formulation, when $\mathds{R}$ has his usual topology, which is the
+%order topology.
+%\end{theorem}
+
+%Indeed this result is weaker than the theorem establishing the chaos for the
+%finer topology $d$. However the Theorem \ref{th:IC et topologie de l'ordre}
+%still remains important. Indeed, we have studied in our previous works a set
+%different from the usual set of study ($\mathcal{X}$ instead of $\mathds{R}$),
+%in order to be as close as possible from the computer: the properties of
+%disorder proved theoretically will then be preserved when computing. However, we
+%could wonder whether this change does not lead to a disorder of a lower quality.
+%In other words, have we replaced a situation of a good disorder lost when
+%computing, to another situation of a disorder preserved but of bad quality.
+%Theorem \ref{th:IC et topologie de l'ordre} prove exactly the contrary.
+%
+
+
+
+
+
+
+\section{Security Analysis}
+
+
+
+
+In this section the concatenation of two strings $u$ and $v$ is classically
+denoted by $uv$.
+In a cryptographic context, a pseudo-random generator is a deterministic
+algorithm $G$ transforming strings into strings and such that, for any
+seed $w$ of length $N$, $G(w)$ (the output of $G$ on the input $w$) has size
+$\ell_G(N)$ with $\ell_G(N)>N$.
+The notion of {\it secure} PRNGs can now be defined as follows.
+
+\begin{definition}
+A cryptographic PRNG $G$ is secure if for any probabilistic polynomial time
+algorithm $D$, for any positive polynomial $p$, and for all sufficiently
+large $k$'s,
+$$| \mathrm{Pr}[D(G(U_k))=1]-Pr[D(U_{\ell_G(k)}=1]|< \frac{1}{p(N)},$$
+where $U_r$ is the uniform distribution over $\{0,1\}^r$ and the
+probabilities are taken over $U_N$, $U_{\ell_G(N)}$ as well as over the
+internal coin tosses of $D$.
+\end{definition}
+
+Intuitively, it means that there is no polynomial time algorithm that can
+distinguish a perfect uniform random generator from $G$ with a non
+negligible probability. The interested reader is referred
+to~\cite[chapter~3]{Goldreich} for more information. Note that it is
+quite easily possible to change the function $\ell$ into any polynomial
+function $\ell^\prime$ satisfying $\ell^\prime(N)>N)$~\cite[Chapter 3.3]{Goldreich}.
+
+The generation schema developed in (\ref{equation Oplus}) is based on a
+pseudo-random generator. Let $H$ be a cryptographic PRNG. We may assume,
+without loss of generality, that for any string $S_0$ of size $N$, the size
+of $H(S_0)$ is $kN$, with $k>2$. It means that $\ell_H(N)=kN$.
+Let $S_1,\ldots,S_k$ be the
+strings of length $N$ such that $H(S_0)=S_1 \ldots S_k$ ($H(S_0)$ is the concatenation of
+the $S_i$'s). The cryptographic PRNG $X$ defined in (\ref{equation Oplus})
+is the algorithm mapping any string of length $2N$ $x_0S_0$ into the string
+$(x_0\oplus S_0 \oplus S_1)(x_0\oplus S_0 \oplus S_1\oplus S_2)\ldots
+(x_o\bigoplus_{i=0}^{i=k}S_i)$. Particularly one has $\ell_{X}(2N)=kN=\ell_H(N)$.
+We claim now that if this PRNG is secure,
+then the new one is secure too.
+
+\begin{proposition}
+If $H$ is a secure cryptographic PRNG, then $X$ is a secure cryptographic
+PRNG too.
+\end{proposition}
+
+\begin{proof}
+The proposition is proved by contraposition. Assume that $X$ is not
+secure. By Definition, there exists a polynomial time probabilistic
+algorithm $D$, a positive polynomial $p$, such that for all $k_0$ there exists
+$N\geq \frac{k_0}{2}$ satisfying
+$$| \mathrm{Pr}[D(X(U_{2N}))=1]-\mathrm{Pr}[D(U_{kN}=1]|\geq \frac{1}{p(2N)}.$$
+We describe a new probabilistic algorithm $D^\prime$ on an input $w$ of size
+$kN$:
+\begin{enumerate}
+\item Decompose $w$ into $w=w_1\ldots w_{k}$, where each $w_i$ has size $N$.
+\item Pick a string $y$ of size $N$ uniformly at random.
+\item Compute $z=(y\oplus w_1)(y\oplus w_1\oplus w_2)\ldots (y
+ \bigoplus_{i=1}^{i=k} w_i).$
+\item Return $D(z)$.
+\end{enumerate}
+
+
+Consider for each $y\in \mathbb{B}^{kN}$ the function $\varphi_{y}$
+from $\mathbb{B}^{kN}$ into $\mathbb{B}^{kN}$ mapping $w=w_1\ldots w_k$
+(each $w_i$ has length $N$) to
+$(y\oplus w_1)(y\oplus w_1\oplus w_2)\ldots (y
+ \bigoplus_{i=1}^{i=k_1} w_i).$ By construction, one has for every $w$,
+\begin{equation}\label{PCH-1}
+D^\prime(w)=D(\varphi_y(w)),
+\end{equation}
+where $y$ is randomly generated.
+Moreover, for each $y$, $\varphi_{y}$ is injective: if
+$(y\oplus w_1)(y\oplus w_1\oplus w_2)\ldots (y\bigoplus_{i=1}^{i=k_1}
+w_i)=(y\oplus w_1^\prime)(y\oplus w_1^\prime\oplus w_2^\prime)\ldots
+(y\bigoplus_{i=1}^{i=k} w_i^\prime)$, then for every $1\leq j\leq k$,
+$y\bigoplus_{i=1}^{i=j} w_i^\prime=y\bigoplus_{i=1}^{i=j} w_i$. It follows,
+by a direct induction, that $w_i=w_i^\prime$. Furthermore, since $\mathbb{B}^{kN}$
+is finite, each $\varphi_y$ is bijective. Therefore, and using (\ref{PCH-1}),
+one has
+\begin{equation}\label{PCH-2}
+\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(\varphi_y(U_{kN}))=1]=\mathrm{Pr}[D(U_{kN})=1].
+\end{equation}
+
+Now, using (\ref{PCH-1}) again, one has for every $x$,
+\begin{equation}\label{PCH-3}
+D^\prime(H(x))=D(\varphi_y(H(x))),
+\end{equation}
+where $y$ is randomly generated. By construction, $\varphi_y(H(x))=X(yx)$,
+thus
+\begin{equation}\label{PCH-3}
+D^\prime(H(x))=D(yx),
+\end{equation}
+where $y$ is randomly generated.
+It follows that
+
+\begin{equation}\label{PCH-4}
+\mathrm{Pr}[D^\prime(H(U_{N}))=1]=\mathrm{Pr}[D(U_{2N})=1].
+\end{equation}
+ From (\ref{PCH-2}) and (\ref{PCH-4}), one can deduce that
+there exist a polynomial time probabilistic
+algorithm $D^\prime$, a positive polynomial $p$, such that for all $k_0$ there exists
+$N\geq \frac{k_0}{2}$ satisfying
+$$| \mathrm{Pr}[D(H(U_{N}))=1]-\mathrm{Pr}[D(U_{kN}=1]|\geq \frac{1}{p(2N)},$$
+proving that $H$ is not secure, a contradiction.
+\end{proof}
-On parle du passage du sequentiel au GPU
-\section{Experiments}
-On passe le BigCrush\\
-On donne des temps de générations sur GPU/CPU\\
-On donne des temps de générations de nombre sur GPU puis on rappatrie sur CPU / CPU ? bof bof, on verra
\section{Conclusion}
-\bibliographystyle{plain}
+
+
+In this paper we have presented a new class of PRNGs based on chaotic
+iterations. We have proven that these PRNGs are chaotic in the sense of Devenay.
+We also propose a PRNG cryptographically secure and its implementation on GPU.
+
+An efficient implementation on GPU based on a xor-like PRNG allows us to
+generate a huge number of pseudo-random numbers per second (about
+20Gsample/s). This PRNG succeeds to pass the hardest batteries of TestU01.
+
+In future work we plan to extend this work for parallel PRNG for clusters or
+grid computing. We also plan to improve the BBS version in order to succeed all
+the tests of TestU01.
+
+
+
+\bibliographystyle{plain}
\bibliography{mabase}
\end{document}
