X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/10e6981881d8b6f0b35ee256f3540d0a0c052324..8cbe6d4faae325510cbbb002936afe1c4e19202b:/prng_gpu.tex?ds=sidebyside

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 7d94e0c..7eb93d1 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}
 
@@ -135,7 +143,7 @@ allows us to generate almost 20 billion of pseudorandom numbers per second.
 Furthermore, we show that the proposed post-treatment preserves the
 cryptographical security of the inputted PRNG, when this last has such a 
 property.
-Last, but not least, we propose a rewritting of the Blum-Goldwasser asymmetric
+Last, but not least, we propose a rewriting of the Blum-Goldwasser asymmetric
 key encryption protocol by using the proposed method.
 
 The remainder of this paper  is organized as follows. In Section~\ref{section:related
@@ -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}
@@ -536,7 +552,7 @@ x^0 \in \llbracket 0, 2^\mathsf{N}-1 \rrbracket, S \in \llbracket 0, 2^\mathsf{N
 \label{equation Oplus}
 \end{equation}
 where $\oplus$ is for the bitwise exclusive or between two integers. 
-This rewritting can be understood as follows. The $n-$th term $S^n$ of the
+This rewriting 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 
@@ -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,14 +970,16 @@ 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 simultenaously,  the number  of random numbers  that a thread  can generate
+used simultaneously,  the number  of random numbers  that a thread  can generate
 inside   a    kernel   is   limited  (\emph{i.e.},    the    variable   \texttt{n}   in
 algorithm~\ref{algo:gpu_kernel}). For instance, if  $100,000$ threads are used and
 if $n=100$\footnote{in fact, we need to add the initial seed (a 32-bits number)},
@@ -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. 
@@ -1255,7 +1286,7 @@ lesser than $2^{16}$.  So in practice we can choose prime numbers around
 indistinguishable    bits    is    lesser    than   or    equals    to
 $log_2(log_2(M))$). In other words, to generate a  32-bits number, we need to use
 8 times  the BBS  algorithm with possibly different  combinations of  $M$. This
-approach is  not sufficient to be able to pass  all the TestU01,
+approach is  not sufficient to be able to pass  all the tests of TestU01,
 as small values of  $M$ for the BBS  lead to
   small periods. So, in  order to add randomness  we have proceeded with
 the followings  modifications. 
@@ -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}
@@ -1344,7 +1375,7 @@ variability.  In these operations, we make twice a left shift of $t$ of \emph{at
   most}  3 bits,  represented by  \texttt{shift} in  the algorithm,  and  we put
 \emph{exactly} the \texttt{shift}  last bits from a BBS  into the \texttt{shift}
 last bits of $t$. For this, an array named \texttt{array\_shift}, containing the
-correspondance between the  shift and the number obtained  with \texttt{shift} 1
+correspondence between the  shift and the number obtained  with \texttt{shift} 1
 to make the \texttt{and} operation is used. For example, with a left shift of 0,
 we  make an  and operation  with 0,  with  a left  shift of  3, we  make an  and
 operation with 7 (represented by 111 in binary mode).
@@ -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 
