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

diff --git a/prng_gpu.tex b/prng_gpu.tex
index ed7e927..7d94e0c 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -824,7 +824,7 @@ given PRNG.
 An iteration of the system is simply the bitwise exclusive or between
 the last computed state and the current strategy.
 Topological properties of disorder exhibited by chaotic 
-iterations can be inherited by the inputted generator, hoping by doing so to 
+iterations can be inherited by the inputted generator, we hope by doing so to 
 obtain some statistical improvements while preserving speed.
 
 
@@ -902,7 +902,7 @@ used  (if,  while,  ...),  the  better the  performances  on  GPU  is.
 Obviously, having these requirements in  mind, it is possible to build
 a   program    similar   to    the   one   presented    in  Listing 
 \ref{algo:seqCIPRNG}, which computes  pseudorandom numbers on GPU.  To
-do  so,  we  must   firstly  remind  that  in  the  CUDA~\cite{Nvid10}
+do  so,  we  must   firstly  recall  that  in  the  CUDA~\cite{Nvid10}
 environment,    threads    have     a    local    identifier    called
 \texttt{ThreadIdx},  which   is  relative  to   the  block  containing
 them. Furthermore, in  CUDA, parts of  the code that are executed by the  GPU, are
@@ -916,7 +916,7 @@ It is possible to deduce from the CPU version a quite similar version adapted to
 The simple principle consists in making each thread of the GPU computing the CPU version of our PRNG.  
 Of course,  the  three xor-like
 PRNGs  used in these computations must have different  parameters. 
-In a given thread, these lasts are
+In a given thread, these parameters are
 randomly picked from another PRNGs. 
 The  initialization stage is performed by  the CPU.
 To do it, the  ISAAC  PRNG~\cite{Jenkins96} is used to  set  all  the
@@ -1095,7 +1095,7 @@ In Figure~\ref{fig:time_bbs_gpu} we highlight  the performances of the optimized
 BBS-based PRNG on GPU.  On  the Tesla C1060 we obtain approximately 700MSample/s
 and  on the  GTX 280  about  670MSample/s, which  is obviously  slower than  the
 xorlike-based PRNG on GPU. However, we  will show in the next sections that this
-new PRNG  has a strong  level of  security, which is  necessary paid by  a speed
+new PRNG  has a strong  level of  security, which is  necessarily paid by  a speed
 reduction.
 
 \begin{figure}[htbp]
@@ -1108,7 +1108,7 @@ reduction.
 
 All  these  experiments allow  us  to conclude  that  it  is possible  to
 generate a very large quantity of pseudorandom  numbers statistically perfect with the  xor-like version.
-In a certain extend, it is the case too with the secure BBS-based version, the speed deflation being
+To a certain extend, it is also the case with the secure BBS-based version, the speed deflation being
 explained by the fact that the former  version has ``only''
 chaotic properties and statistical perfection, whereas the latter is also cryptographically secure,
 as it is shown in the next sections.
@@ -1158,7 +1158,7 @@ strings of length $N$ such that $H(S_0)=S_1 \ldots S_k$ ($H(S_0)$ is the concate
 the $S_i$'s). The cryptographic PRNG $X$ defined in (\ref{equation Oplus})
 is the algorithm mapping any string of length $2N$ $x_0S_0$ into the string
 $(x_0\oplus S_0 \oplus S_1)(x_0\oplus S_0 \oplus S_1\oplus S_2)\ldots
-(x_o\bigoplus_{i=0}^{i=k}S_i)$. Particularly one has $\ell_{X}(2N)=kN=\ell_H(N)$. 
+(x_o\bigoplus_{i=0}^{i=k}S_i)$. One in particular has $\ell_{X}(2N)=kN=\ell_H(N)$. 
 We claim now that if this PRNG is secure,
 then the new one is secure too.
 
@@ -1222,11 +1222,11 @@ It follows that
 \mathrm{Pr}[D^\prime(H(U_{N}))=1]=\mathrm{Pr}[D(U_{2N})=1].
 \end{equation}
  From (\ref{PCH-2}) and (\ref{PCH-4}), one can deduce that
-there exist a polynomial time probabilistic
+there exists a polynomial time probabilistic
 algorithm $D^\prime$, a positive polynomial $p$, such that for all $k_0$ there exists
 $N\geq \frac{k_0}{2}$ satisfying 
 $$| \mathrm{Pr}[D(H(U_{N}))=1]-\mathrm{Pr}[D(U_{kN}=1]|\geq \frac{1}{p(2N)},$$
-proving that $H$ is not secure, a contradiction. 
+proving that $H$ is not secure, which is a contradiction. 
 \end{proof}
 
 
@@ -1257,19 +1257,19 @@ $log_2(log_2(M))$). In other words, to generate a  32-bits number, we need to us
 8 times  the BBS  algorithm with possibly different  combinations of  $M$. This
 approach is  not sufficient to be able to pass  all the TestU01,
 as small values of  $M$ for the BBS  lead to
-  small periods. So, in  order to add randomness  we proceed with
+  small periods. So, in  order to add randomness  we have proceeded with
 the followings  modifications. 
 \begin{itemize}
 \item
 Firstly, we  define 16 arrangement arrays  instead of 2  (as described in
 Algorithm \ref{algo:gpu_kernel2}), but only 2 of them are used at each call of
-the  PRNG kernels. In  practice, the  selection of   combinations
+the  PRNG kernels. In  practice, the  selection of   combination
 arrays to be used is different for all the threads. It is determined
 by using  the three last bits  of two internal variables  used by BBS.
 %This approach  adds more randomness.   
 In Algorithm~\ref{algo:bbs_gpu},
 character  \& is for the  bitwise AND. Thus using  \&7 with  a number
-gives the last 3 bits, providing so a number between 0 and 7.
+gives the last 3 bits, thus providing a number between 0 and 7.
 \item
 Secondly, after the  generation of the 8 BBS numbers  for each thread, we
 have a 32-bits number whose period is possibly quite small. So
@@ -1277,7 +1277,7 @@ to add randomness,  we generate 4 more BBS numbers   to
 shift  the 32-bits  numbers, and  add up to  6 new  bits.  This  improvement is
 described  in Algorithm~\ref{algo:bbs_gpu}.  In  practice, the last 2 bits
 of the first new BBS number are  used to make a left shift of at most
-3 bits. The  last 3 bits of the  second new BBS number are  add to the
+3 bits. The  last 3 bits of the  second new BBS number are  added to the
 strategy whatever the value of the first left shift. The third and the
 fourth new BBS  numbers are used similarly to apply  a new left shift
 and add 3 new bits.
@@ -1401,7 +1401,7 @@ When Alice receives $\left[(c_0, \dots, c_{L-1}), y\right]$, she can recover $m$
 \item Using the secret key $(p,q)$, she computes $r_p = y^{((p+1)/4)^{L}}~mod~p$ and $r_q = y^{((q+1)/4)^{L}}~mod~q$.
 \item The initial seed can be obtained using the following procedure: $x_0=q(q^{-1}~{mod}~p)r_p + p(p^{-1}~{mod}~q)r_q~{mod}~N$.
 \item She recomputes the bit-vector $b$ by using BBS and $x_0$.
-\item Alice computes finally the plaintext by XORing the keystream with the ciphertext: $ m = c \oplus  b$.
+\item Alice finally computes the plaintext by XORing the keystream with the ciphertext: $ m = c \oplus  b$.
 \end{enumerate}
 
 
@@ -1421,7 +1421,7 @@ instead of $\left(m_0 \oplus b_0, m_1 \oplus b_1, \hdots, m_{L-1} \oplus b_{L-1}
 
 The same decryption stage as in Blum-Goldwasser leads to the sequence 
 $\left(m_0 \oplus S^0, m_1 \oplus S^0, \hdots, m_{L-1} \oplus S^0 \right)$.
-Thus, with a simple use of $S^0$, Alice can obtained the plaintext.
+Thus, with a simple use of $S^0$, Alice can obtain the plaintext.
 By doing so, the proposed generator is used in place of BBS, leading to
 the inheritance of all the properties presented in this paper.
 
@@ -1432,7 +1432,7 @@ In  this  paper, a formerly proposed PRNG based on chaotic iterations
 has been generalized to improve its speed. It has been proven to be
 chaotic according to Devaney.
 Efficient implementations on  GPU using xor-like  PRNGs as input generators
-shown that a very large quantity of pseudorandom numbers can be generated per second (about
+have shown that a very large quantity of pseudorandom numbers can be generated per second (about
 20Gsamples/s), and that these proposed PRNGs succeed to pass the hardest battery in TestU01,
 namely the BigCrush.
 Furthermore, we have shown that when the inputted generator is cryptographically