Autres modifs

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 54314090ce6387b5e399d36c10d1363ba6ecbc0d..11dd246f44d0012ce3cda2c421af4b48e7c26113 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -34,7 +34,7 @@
 
 \newcommand{\alert}[1]{\begin{color}{blue}\textit{#1}\end{color}}
 
 
 \newcommand{\alert}[1]{\begin{color}{blue}\textit{#1}\end{color}}
 

-\title{Efficient generation of pseudo random numbers based on chaotic iterations
+\title{Efficient Generation of Pseudo-Random Bumbers based on Chaotic Iterations

 on GPU}
 \begin{document}
 
 on GPU}
 \begin{document}
 


@@ -59,11 +59,11 @@ Interet de générer des nombres alea sur GPU
 \label{section:BASIC RECALLS}
 This section is devoted to basic definitions and terminologies in the fields of
 topological chaos and chaotic iterations.
 \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}
+\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$
 
 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$

-denotes the $k^{th}$ composition of a function $f$. Finally, the following
+is for the $k^{th}$ composition of a function $f$. Finally, the following

 notation is used: $\llbracket1;N\rrbracket=\{1,2,\hdots,N\}$.
 
 
 notation is used: $\llbracket1;N\rrbracket=\{1,2,\hdots,N\}$.
 
 


@@ -89,7 +89,7 @@ necessarily the same period).
 \end{definition}
 
 
 \end{definition}
 
 

-\begin{definition}
+\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}
 $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and
 topologically transitive.
 \end{definition}


@@ -119,7 +119,7 @@ possible and occur in an unpredictable way.
 
 
 
 
 
 

-\subsection{Chaotic iterations}
+\subsection{Chaotic Iterations}

 \label{sec:chaotic iterations}
 
 
 \label{sec:chaotic iterations}
 
 


@@ -135,7 +135,7 @@ denoted by $\llbracket 1, \mathsf{N} \rrbracket^\mathds{N}.$
 \label{Def:chaotic iterations}
 The      set       $\mathds{B}$      denoting      $\{0,1\}$,      let
 $f:\mathds{B}^{\mathsf{N}}\longrightarrow  \mathds{B}^{\mathsf{N}}$ be
 \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
+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}
 \emph{chaotic      iterations}     are     defined      by     $x^0\in
 \mathds{B}^{\mathsf{N}}$ and
 \begin{equation}


@@ -155,7 +155,7 @@ $\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
 $\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, recalled above.
+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
 
 
 Let us now recall how to define a suitable metric space where chaotic iterations


@@ -185,8 +185,8 @@ G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), \label{Gf}
 (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
 (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 defined in
-(\ref{sec:chaotic iterations}) can be described by the following iterations:
+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}
 \begin{equation}
 \left\{
 \begin{array}{l}


@@ -200,7 +200,6 @@ 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. 
 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:
 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:


@@ -238,22 +237,24 @@ 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.
 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.

 
 Finally, it has been established in \cite{guyeux10} that,
 
 \begin{proposition}
 
 Finally, it has been established in \cite{guyeux10} that,
 
 \begin{proposition}

-Let $f$ be a map from $\mathds{B}^n$ to itself. Then $G_{f}$ is continuous in
+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}
 
 The chaotic property of $G_f$ has been firstly established for the vectorial
 the metric space $(\mathcal{X},d)$.
 \end{proposition}
 
 The chaotic property of $G_f$ has been firstly established for the vectorial

-Boolean negation \cite{guyeux10}. To obtain a characterization, we have secondly
+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.
 
 introduced the notion of asynchronous iteration graph recalled bellow.
 

-Let $f$ be a map from $\mathds{B}^n$ to itself. The
+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
 {\emph{asynchronous iteration graph}} associated with $f$ is the
 directed graph $\Gamma(f)$ defined by: the set of vertices is

-$\mathds{B}^n$; for all $x\in\mathds{B}^n$ and $i\in \llbracket1;n\rrbracket$,
+$\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
 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


@@ -265,17 +266,17 @@ We have finally proven in \cite{bcgr11:ip} that,
 
 \begin{theorem}
 \label{Th:Caractérisation   des   IC   chaotiques}  
 
 \begin{theorem}
 \label{Th:Caractérisation   des   IC   chaotiques}  

-Let $f:\mathds{B}^n\to\mathds{B}^n$. $G_f$ is chaotic  (according to  Devaney) 
+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. 
 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 ;  n \rrbracket^{\mathds{N}} 
-\times \mathds{B}^n$, is build from Boolean networks $f : \mathds{B}^n
-\rightarrow \mathds{B}^n$, we can preserve the theoretical properties on $G_f$
+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
 during implementations (due to the discrete nature of $f$). It is as if

-$\mathds{B}^n$ represents the memory of the computer whereas $\llbracket 1 ;  n
+$\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}
 \rrbracket^{\mathds{N}}$ is its input stream (the seeds, for instance).
 
 \section{Application to Pseudo-Randomness}


@@ -350,9 +351,9 @@ We have proven in \cite{bcgr11:ip} that,
   if and only if $M$ is a double stochastic matrix.
 \end{theorem} 
 
   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}
+\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
 
 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


@@ -404,10 +405,10 @@ 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
 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 more 
-fastly, does not deflate their topological chaos properties.
+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}
+\subsection{Proofs of Chaos of the General Formulation of the Chaotic Iterations}

 
 Let us consider the discrete dynamical systems in chaotic iterations having 
 the general form:
 
 Let us consider the discrete dynamical systems in chaotic iterations having 
 the general form:


@@ -477,7 +478,7 @@ 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 
 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 introduced.
+$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}),
 Let us introduce:
 \begin{equation}
 d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}),