X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/c8b95c6c1d99f1ab0375abf07c90613c94d4e261..4ad2ccae91afa1f83fad9be3c87213a9b8d81734:/prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 6c6c980..a57e2a0 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -1,4 +1,5 @@
-\documentclass{article}
+%\documentclass{article}
+\documentclass[10pt,journal,letterpaper,compsoc]{IEEEtran}
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
 \usepackage{fullpage}
@@ -38,10 +39,10 @@
 \begin{document}
 
 \author{Jacques M. Bahi, Rapha\"{e}l Couturier,  Christophe
-Guyeux, and Pierre-Cyrille Heam\thanks{Authors in alphabetic order}}
+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
@@ -56,6 +57,13 @@ A chaotic version of the Blum-Goldwasser asymmetric key encryption scheme is fin
 
 
 \end{abstract}
+}
+
+\maketitle
+
+\IEEEdisplaynotcompsoctitleabstractindextext
+\IEEEpeerreviewmaketitle
+
 
 \section{Introduction}
 
@@ -153,7 +161,7 @@ We show in Section~\ref{sec:security analysis} that, if the inputted
 generator is cryptographically secure, then it is the case too for the
 generator provided by the post-treatment.
 Such a proof leads to the proposition of a cryptographically secure and
-chaotic generator on GPU based on the famous Blum Blum Shum
+chaotic generator on GPU based on the famous Blum Blum Shub
 in Section~\ref{sec:CSGPU}, and to an improvement of the
 Blum-Goldwasser protocol in Sect.~\ref{Blum-Goldwasser}.
 This research work ends by a conclusion section, in which the contribution is
@@ -216,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}$
@@ -229,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}
@@ -248,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}
 
@@ -256,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
@@ -320,15 +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:
-\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)+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}
@@ -467,8 +478,9 @@ generator taken alone. Furthermore, our generator
 possesses various chaos properties that none of the generators used as input
 present.
 
+
 \begin{algorithm}[h!]
-%\begin{scriptsize}
+\begin{small}
 \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$
 ($n$ bits)}
 \KwOut{a configuration $x$ ($n$ bits)}
@@ -480,12 +492,16 @@ $s\leftarrow{\textit{XORshift}(n)}$\;
 $x\leftarrow{F_f(s,x)}$\;
 }
 return $x$\;
-%\end{scriptsize}
+\end{small}
 \caption{PRNG with chaotic functions}
 \label{CI Algorithm}
 \end{algorithm}
 
+
+
+
 \begin{algorithm}[h!]
+\begin{small}
 \KwIn{the internal configuration $z$ (a 32-bit word)}
 \KwOut{$y$ (a 32-bit word)}
 $z\leftarrow{z\oplus{(z\ll13)}}$\;
@@ -493,7 +509,7 @@ $z\leftarrow{z\oplus{(z\gg17)}}$\;
 $z\leftarrow{z\oplus{(z\ll5)}}$\;
 $y\leftarrow{z}$\;
 return $y$\;
-\medskip
+\end{small}
 \caption{An arbitrary round of \textit{XORshift} algorithm}
 \label{XORshift}
 \end{algorithm}
@@ -576,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.
@@ -605,14 +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:
-\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},%
+$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:
@@ -622,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
@@ -649,17 +664,21 @@ Let us introduce:
 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 once more the Hamming distance}, \\
-\displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}%
-\sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}.%
-\end{array}%
-\right.
-\end{equation}
+\noindent where $ \displaystyle{d_{e}(E,\check{E})} = \displaystyle{\sum_{k=1}^{\mathsf{N}%
+ }\delta (E_{k},\check{E}_{k})}$  is once more the Hamming distance, and
+$  \displaystyle{d_{s}(S,\check{S})}  =  \displaystyle{\dfrac{9}{\mathsf{N}}%
+ \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}$,
+%%RAPH : ici, j'ai supprimÃ© tous les sauts Ã  la ligne
+%% \begin{equation}
+%% \left\{
+%% \begin{array}{lll}
+%% \displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}%
+%% }\delta (E_{k},\check{E}_{k})} \textrm{ is once more the Hamming distance}, \\
+%% \displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}%
+%% \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}.%
+%% \end{array}%
+%% \right.
+%% \end{equation}
 where $|X|$ is the cardinality of a set $X$ and $A\Delta B$ is for the symmetric difference, defined for sets A, B as
 $A\,\Delta\,B = (A \setminus B) \cup (B \setminus A)$.
 
@@ -738,14 +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,
-$$
-\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)
+%%RAPH : ici j'ai rajoutÃ© une ligne
+$
+\forall \varepsilon >0,$ $\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N}
+,$ $\forall n\geqslant N_{0},$
+$ d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right)
 \leqslant \varepsilon .
-$$
+$
 $G_{f}$ is consequently continuous.
 \end{proof}
 
@@ -785,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.
@@ -803,8 +824,10 @@ 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
+of $S$ and the first $t_2$ terms of $S'$: 
+%%RAPH : j'ai coupÃ© la ligne en 2
+$$\tilde
+S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,$$$$\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It
 is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after
 $t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic
 point. Since $\tilde S_t=S_t$ for $t<t_1$, by the choice of $t_1$, we
@@ -827,38 +850,41 @@ Topological properties of disorder exhibited by chaotic
 iterations can be inherited by the inputted generator, we hope by doing so to 
 obtain some statistical improvements while preserving speed.
 
-
-Let us give an example using 16-bits numbers, to clearly understand how the bitwise xor operations
-are
-done.  
-Suppose  that $x$ and the  strategy $S^i$ are given as
-binary vectors.
-Table~\ref{TableExemple} shows the result of $x \oplus S^i$.
-
-\begin{table}
-$$
-\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}
-$$
-\caption{Example of an arbitrary round of the proposed generator}
-\label{TableExemple}
-\end{table}
-
-
-
-
-\lstset{language=C,caption={C code of the sequential PRNG based on chaotic iteration\
-s},label=algo:seqCIPRNG}
+%%RAPH : j'ai virÃ© tout ca
+%% Let us give an example using 16-bits numbers, to clearly understand how the bitwise xor operations
+%% are
+%% done.  
+%% Suppose  that $x$ and the  strategy $S^i$ are given as
+%% binary vectors.
+%% Table~\ref{TableExemple} shows the result of $x \oplus S^i$.
+
+%% \begin{table}
+%% \begin{scriptsize}
+%% $$
+%% \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}
+%% $$
+%% \end{scriptsize}
+%% \caption{Example of an arbitrary round of the proposed generator}
+%% \label{TableExemple}
+%% \end{table}
+
+
+
+
+\lstset{language=C,caption={C code of the sequential PRNG based on chaotic iterations},label=algo:seqCIPRNG}
+\begin{small}
 \begin{lstlisting}
+
 unsigned int CIPRNG() {
   static unsigned int x = 123123123;
   unsigned long t1 = xorshift();
@@ -873,7 +899,7 @@ unsigned int CIPRNG() {
   return x;
 }
 \end{lstlisting}
-
+\end{small}
 
 
 
@@ -929,8 +955,9 @@ number  $x$  that saves  the  last  generated  pseudorandom number. Additionally
 implementation of the  xor128, the xorshift, and the  xorwow respectively require
 4, 5, and 6 unsigned long as internal variables.
 
-\begin{algorithm}
 
+\begin{algorithm}
+\begin{small}
 \KwIn{InternalVarXorLikeArray: array with internal variables of the 3 xor-like
 PRNGs in global memory\;
 NumThreads: number of threads\;}
@@ -943,11 +970,13 @@ NumThreads: number of threads\;}
   }
   store internal variables in InternalVarXorLikeArray[threadIdx]\;
 }
-
+\end{small}
 \caption{Main kernel of the GPU ``naive'' version of the PRNG based on chaotic iterations}
 \label{algo:gpu_kernel}
 \end{algorithm}
 
+
+
 Algorithm~\ref{algo:gpu_kernel}  presents a naive  implementation of the proposed  PRNG on
 GPU.  Due to the available  memory in the  GPU and the number  of threads
 used simultaneously,  the number  of random numbers  that a thread  can generate
@@ -994,7 +1023,7 @@ bits).
 This version  can also pass the whole {\it BigCrush} battery of tests.
 
 \begin{algorithm}
-
+\begin{small}
 \KwIn{InternalVarXorLikeArray: array with internal variables of 1 xor-like PRNGs
 in global memory\;
 NumThreads: Number of threads\;
@@ -1016,7 +1045,7 @@ array\_comb1, array\_comb2: Arrays containing combinations of size combination\_
   }
   store internal variables in InternalVarXorLikeArray[threadId]\;
 }
-
+\end{small}
 \caption{Main kernel for the chaotic iterations based PRNG GPU efficient
 version\label{IR}}
 \label{algo:gpu_kernel2} 
@@ -1081,7 +1110,7 @@ As a  comparison,   Listing~\ref{algo:seqCIPRNG}  leads   to the  generation of
 
 \begin{figure}[htbp]
 \begin{center}
-  \includegraphics[scale=.7]{curve_time_xorlike_gpu.pdf}
+  \includegraphics[width=\columnwidth]{curve_time_xorlike_gpu.pdf}
 \end{center}
 \caption{Quantity of pseudorandom numbers generated per second with the xorlike-based PRNG}
 \label{fig:time_xorlike_gpu}
@@ -1100,7 +1129,7 @@ reduction.
 
 \begin{figure}[htbp]
 \begin{center}
-  \includegraphics[scale=.7]{curve_time_bbs_gpu.pdf}
+  \includegraphics[width=\columnwidth]{curve_time_bbs_gpu.pdf}
 \end{center}
 \caption{Quantity of pseudorandom numbers generated per second using the BBS-based PRNG}
 \label{fig:time_bbs_gpu}
@@ -1128,17 +1157,17 @@ In this section the concatenation of two strings $u$ and $v$ is classically
 denoted by $uv$.
 In a cryptographic context, a pseudorandom generator is a deterministic
 algorithm $G$ transforming strings  into strings and such that, for any
-seed $k$ of length $k$, $G(k)$ (the output of $G$ on the input $k$) has size
-$\ell_G(k)$ with $\ell_G(k)>k$.
+seed $s$ of length $m$, $G(s)$ (the output of $G$ on the input $s$) has size
+$\ell_G(m)$ with $\ell_G(m)>m$.
 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(k)},$$
+large $m$'s,
+$$| \mathrm{Pr}[D(G(U_m))=1]-Pr[D(U_{\ell_G(m)})=1]|< \frac{1}{p(m)},$$
 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
+probabilities are taken over $U_m$, $U_{\ell_G(m)}$ as well as over the
 internal coin tosses of $D$. 
 \end{definition}
 
@@ -1147,7 +1176,7 @@ 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}.
+function $\ell^\prime$ satisfying $\ell^\prime(m)>m)$~\cite[Chapter 3.3]{Goldreich}.
 
 The generation schema developed in (\ref{equation Oplus}) is based on a
 pseudorandom generator. Let $H$ be a cryptographic PRNG. We may assume,
@@ -1202,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$,
@@ -1212,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. 
@@ -1239,7 +1270,7 @@ It is  possible to build a  cryptographically secure PRNG based  on the previous
 algorithm (Algorithm~\ref{algo:gpu_kernel2}).   Due to Proposition~\ref{cryptopreuve},
 it simply consists  in replacing
 the  {\it  xor-like} PRNG  by  a  cryptographically  secure one.  
-We have chosen the Blum Blum Shum generator~\cite{BBS} (usually denoted by BBS) having the form:
+We have chosen the Blum Blum Shub generator~\cite{BBS} (usually denoted by BBS) having the form:
 $$x_{n+1}=x_n^2~ mod~ M$$  where $M$ is the product of  two prime numbers (these
 prime numbers  need to be congruent  to 3 modulus  4). BBS is known to be
 very slow and only usable for cryptographic applications. 
@@ -1290,7 +1321,7 @@ variable for BBS number 8 is stored in place 1.
 \end{itemize}
 
 \begin{algorithm}
-
+\begin{small}
 \KwIn{InternalVarBBSArray: array with internal variables of the 8 BBS
 in global memory\;
 NumThreads: Number of threads\;
@@ -1326,7 +1357,7 @@ array\_shift[4]=\{0,1,3,7\}\;
   }
   store internal variables in InternalVarXorLikeArray[threadId] using a rotation\;
 }
-
+\end{small}
 \caption{main kernel for the BBS based PRNG GPU}
 \label{algo:bbs_gpu}
 \end{algorithm}
@@ -1414,9 +1445,11 @@ Alice will pick randomly $S^0$ in $\llbracket 0, 2^{\mathsf{N}-1}\rrbracket$ too
 her new public key will be $(S^0, N)$.
 
 To encrypt his message, Bob will compute
-\begin{equation}
-c = \left(m_0 \oplus (b_0 \oplus S^0), m_1 \oplus (b_0 \oplus b_1 \oplus S^0), \hdots, m_{L-1} \oplus (b_0 \oplus b_1 \hdots \oplus b_{L-1} \oplus S^0) \right)
-\end{equation}
+%%RAPH : ici, j'ai mis un simple $
+%\begin{equation}
+$c = \left(m_0 \oplus (b_0 \oplus S^0), m_1 \oplus (b_0 \oplus b_1 \oplus S^0), \hdots, \right.$
+$ \left. m_{L-1} \oplus (b_0 \oplus b_1 \hdots \oplus b_{L-1} \oplus S^0) \right)$
+%%\end{equation}
 instead of $\left(m_0 \oplus b_0, m_1 \oplus b_1, \hdots, m_{L-1} \oplus b_{L-1} \right)$. 
 
 The same decryption stage as in Blum-Goldwasser leads to the sequence 
@@ -1438,10 +1471,10 @@ namely the BigCrush.
 Furthermore, we have shown that when the inputted generator is cryptographically
 secure, then it is the case too for the PRNG we propose, thus leading to
 the possibility to develop fast and secure PRNGs using the GPU architecture.
-Thoughts about an improvement of the Blum-Goldwasser cryptosystem, using the 
-proposed method, has been finally proposed.
+An improvement of the Blum-Goldwasser cryptosystem, making it 
+behaves chaotically, has finally been proposed.
 
-In future  work we plan to extend these researches, building a parallel PRNG for  clusters or
+In future  work we plan to extend this research, building a parallel PRNG for  clusters or
 grid computing. Topological properties of the various proposed generators will be investigated,
 and the use of other categories of PRNGs as input will be studied too. The improvement
 of Blum-Goldwasser will be deepened. Finally, we
