X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/f34b3c375a174c19a28052a60bc942cf22d76a00..8cbe6d4faae325510cbbb002936afe1c4e19202b:/prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 74b5d86..7eb93d1 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -41,8 +41,8 @@
 \author{Jacques M. Bahi, Rapha\"{e}l Couturier,  Christophe
 Guyeux, and Pierre-Cyrille HÃ©am\thanks{Authors in alphabetic order}}
    
-\maketitle
 
+\IEEEcompsoctitleabstractindextext{
 \begin{abstract}
 In this paper we present a new pseudorandom number generator (PRNG) on
 graphics processing units  (GPU). This PRNG is based  on the so-called chaotic iterations.  It
@@ -57,6 +57,13 @@ A chaotic version of the Blum-Goldwasser asymmetric key encryption scheme is fin
 
 
 \end{abstract}
+}
+
+\maketitle
+
+\IEEEdisplaynotcompsoctitleabstractindextext
+\IEEEpeerreviewmaketitle
+
 
 \section{Introduction}
 
@@ -217,7 +224,10 @@ We can finally remark that, to the best of our knowledge, no GPU implementation
 \label{section:BASIC RECALLS}
 
 This section is devoted to basic definitions and terminologies in the fields of
-topological chaos and chaotic iterations.
+topological chaos and chaotic iterations. We assume the reader is familiar
+with basic notions on topology (see for instance~\cite{Devaney}).
+
+
 \subsection{Devaney's Chaotic Dynamical Systems}
 
 In the sequel $S^{n}$ denotes the $n^{th}$ term of a sequence $S$ and $V_{i}$
@@ -230,7 +240,7 @@ Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f :
 \mathcal{X} \rightarrow \mathcal{X}$.
 
 \begin{definition}
-$f$ is said to be \emph{topologically transitive} if, for any pair of open sets
+The function $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}
@@ -249,7 +259,7 @@ necessarily the same period).
 
 
 \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
+The function $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and
 topologically transitive.
 \end{definition}
 
@@ -257,12 +267,12 @@ The chaos property is strongly linked to the notion of ``sensitivity'', defined
 on a metric space $(\mathcal{X},d)$ by:
 
 \begin{definition}
-\label{sensitivity} $f$ has \emph{sensitive dependence on initial conditions}
+\label{sensitivity} The function $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 $.
 
-$\delta$ is called the \emph{constant of sensitivity} of $f$.
+The constant $\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
@@ -321,17 +331,15 @@ 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:
-%%RAPH : ici j'ai coupÃ© la derniÃ¨re ligne en 2, c'est moche mais bon
-\begin{equation}
+(x,y)=0\Leftrightarrow x=y.$ Given a function $f$, define the function
+$F_{f}:  \llbracket1;\mathsf{N}\rrbracket\times \mathds{B}^{\mathsf{N}} 
+\longrightarrow  \mathds{B}^{\mathsf{N}}$
+\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)+ \right.\\
-&       &              & \left. f(E)_{k}.\overline{\delta
-(k,j)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},%
+& (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}%
+\end{equation*}%
 \noindent where + and . are the Boolean addition and product operations.
 Consider the phase space:
 \begin{equation}
@@ -584,11 +592,11 @@ 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:
+the general form: $\forall    n\in     \mathds{N}^{\ast     }$, $  \forall     i\in
+\llbracket1;\mathsf{N}\rrbracket $,
 
 \begin{equation}
-\forall    n\in     \mathds{N}^{\ast     },    \forall     i\in
-\llbracket1;\mathsf{N}\rrbracket ,x_i^n=\left\{
+  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.
@@ -613,15 +621,13 @@ Let us introduce the following function:
 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:
-%%RAPH : j'ai coupÃ© la derniÃ¨re ligne en 2, c'est moche
-\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)+\right.\\
-&       &             &\left.f(E)_{j}.\overline{\chi(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},%
+$F_{f}:  \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} 
+\longrightarrow \mathds{B}^{\mathsf{N}}$
+\begin{equation*}
+\begin{array}{rll}
+ (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+f(E)_{j}.\overline{\chi(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket}%
 \end{array}%
-\end{equation}%
+\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:
@@ -631,7 +637,7 @@ Consider the phase space:
 \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}
+G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), %\label{Gf} %%RAPH, j'ai virÃ© ce label qui existe dÃ©jÃ  avant...
 \end{equation}
 \noindent where $\sigma$ is the \emph{shift} function defined by $\sigma
 (S^{n})_{n\in \mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow (S^{n+1})_{n\in
@@ -751,16 +757,16 @@ thus after $n_{2}$, the $k+2$ first terms of $S^n$ and $S$ are equal.
 \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
+10^{-(k+1)}\leqslant \varepsilon $.
+
 In conclusion,
 %%RAPH : ici j'ai rajoutÃ© une ligne
-\begin{flushleft}$$
-\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)
+$
+\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 .
-$$
-\end{flushleft}
+$
 $G_{f}$ is consequently continuous.
 \end{proof}
 
@@ -800,7 +806,7 @@ where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties
 claimed in the lemma.
 \end{proof}
 
-We can now prove Theorem~\ref{t:chaos des general}...
+We can now prove the Theorem~\ref{t:chaos des general}.
 
 \begin{proof}[Theorem~\ref{t:chaos des general}]
 Firstly, strong transitivity implies transitivity.
@@ -1225,8 +1231,10 @@ $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
+$\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(\varphi_y(U_{kN}))=1]$ and,
+therefore, 
 \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].
+\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(U_{kN})=1].
 \end{equation}
 
 Now, using (\ref{PCH-1}) again, one has  for every $x$,
@@ -1235,7 +1243,7 @@ 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}
+\begin{equation}%\label{PCH-3}      %%RAPH : j'ai virÃ© ce label qui existe dÃ©jÃ , il est 3 ligne avant
 D^\prime(H(x))=D(yx),
 \end{equation}
 where $y$ is randomly generated. 
