X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/2174d791963cf35c69e4cb1fa51771521f34d9d5..3add2868094bc67744e89777e13ce7087b53e01e:/prng_gpu.tex?ds=sidebyside

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 96098bb..c504e98 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -34,7 +34,7 @@
 
 \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}
 
@@ -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.
-\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$
-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\}$.
 
 
@@ -89,7 +89,7 @@ necessarily the same period).
 \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}
@@ -119,7 +119,7 @@ possible and occur in an unpredictable way.
 
 
 
-\subsection{Chaotic iterations}
+\subsection{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
-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}
@@ -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
-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
@@ -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
-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}
@@ -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. 
-
 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.
+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}
-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
-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.
 
-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
-$\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
@@ -265,17 +266,17 @@ We have finally proven in \cite{bcgr11:ip} that,
 
 \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. 
-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
-$\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}
@@ -350,9 +351,9 @@ We have proven in \cite{bcgr11:ip} that,
   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
@@ -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
-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:
@@ -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 
-$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}),
@@ -584,6 +585,66 @@ $G_{f}$ is consequently continuous.
 \end{proof}
 
 
+It is now possible to study the topological behavior of the general chaotic
+iterations. We will prove that,
+
+\begin{theorem}
+\label{t:chaos des general}
+ The general chaotic iterations defined on Equation~\ref{general CIs} satisfy
+the Devaney's property of chaos.
+\end{theorem}
+
+Let us firstly prove the following lemma.
+
+\begin{lemma}[Strong transitivity]
+\label{strongTrans}
+ For all couples $X,Y \in \mathcal{X}$ and any neighborhood $V$ of $X$, we can 
+find $n \in \mathds{N}^*$ and $X' \in V$ such that $G^n(X')=Y$.
+\end{lemma}
+
+\begin{proof}
+ Let $X=(S,E)$, $\varepsilon>0$, and $k_0 = \lfloor log_{10}(\varepsilon)+1 \rfloor$. 
+Any point $X'=(S',E')$ such that $E'=E$ and $\forall k \leqslant k_0, S'^k=S^k$, 
+are in the open ball $\mathcal{B}\left(X,\varepsilon\right)$. Let us define 
+$\check{X} = \left(\check{S},\check{E}\right)$, where $\check{X}= G^{k_0}(X)$.
+We denote by $s\subset \llbracket 1; \mathsf{N} \rrbracket$ the set of coordinates
+that are different between $\check{E}$ and the state of $Y$. Thus each point $X'$ of
+the form $(S',E')$ where $E'=E$ and $S'$ starts with 
+$(S^0, S^1, \hdots, S^{k_0},s,\hdots)$, verifies the following properties:
+\begin{itemize}
+ \item $X'$ is in $\mathcal{B}\left(X,\varepsilon\right)$,
+ \item the state of $G_f^{k_0+1}(X')$ is the state of $Y$.
+\end{itemize}
+Finally the point $\left(\left(S^0, S^1, \hdots, S^{k_0},s,s^0, s^1, \hdots\right); E\right)$, 
+where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties
+claimed in the lemma.
+\end{proof}
+
+We can now prove the Theorem~\ref{t:chaos des general}...
+
+\begin{proof}[Theorem~\ref{t:chaos des general}]
+Firstly, strong transitivity implies transitivity.
+
+Let $(S,E) \in\mathcal{X}$ and $\varepsilon >0$. To
+prove that $G_f$ is regular, it is sufficient to prove that
+there exists a strategy $\tilde S$ such that the distance between
+$(\tilde S,E)$ and $(S,E)$ is less than $\varepsilon$, and such that
+$(\tilde S,E)$ is a periodic point.
+
+Let $t_1=\lfloor-\log_{10}(\varepsilon)\rfloor$, and let $E'$ be the
+configuration that we obtain from $(S,E)$ after $t_1$ iterations of
+$G_f$. As $G_f$ is strongly transitive, there exists a strategy $S'$ 
+and $t_2\in\mathds{N}$ such
+that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$.
+
+Consider the strategy $\tilde S$ that alternates the first $t_1$ terms
+of $S$ and the first $t_2$ terms of $S'$: $$\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}