debut correct english

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 4feac7cc64b8730163298a05ba2edca48d894eeb..ed7e927f4472ce25eb079ffbc4b004c94fca63bb 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -48,7 +48,7 @@ graphics processing units  (GPU). This PRNG is based  on the so-called chaotic i
 is firstly proven  to be chaotic according to the Devaney's  formulation. We thus propose  an efficient
 implementation  for  GPU that successfully passes the   {\it BigCrush} tests, deemed to be the  hardest
 battery of tests in TestU01.  Experiments show that this PRNG can generate
 is firstly proven  to be chaotic according to the Devaney's  formulation. We thus propose  an efficient
 implementation  for  GPU that successfully passes the   {\it BigCrush} tests, deemed to be the  hardest
 battery of tests in TestU01.  Experiments show that this PRNG can generate

-about 20 billions of random numbers  per second on Tesla C1060 and NVidia GTX280
+about 20 billion of random numbers  per second on Tesla C1060 and NVidia GTX280

 cards.
 It is then established that, under reasonable assumptions, the proposed PRNG can be cryptographically 
 secure.
 cards.
 It is then established that, under reasonable assumptions, the proposed PRNG can be cryptographically 
 secure.


@@ -59,7 +59,7 @@ A chaotic version of the Blum-Goldwasser asymmetric key encryption scheme is fin
 
 \section{Introduction}
 
 
 \section{Introduction}
 

-Randomness is of importance in many fields as scientific simulations or cryptography. 
+Randomness is of importance in many fields such as scientific simulations or cryptography. 

 ``Random numbers'' can mainly be generated either by a deterministic and reproducible algorithm
 called a pseudorandom number generator (PRNG), or by a physical non-deterministic 
 process having all the characteristics of a random noise, called a truly random number
 ``Random numbers'' can mainly be generated either by a deterministic and reproducible algorithm
 called a pseudorandom number generator (PRNG), or by a physical non-deterministic 
 process having all the characteristics of a random noise, called a truly random number


@@ -67,18 +67,18 @@ generator (TRNG).
 In this paper, we focus on reproducible generators, useful for instance in
 Monte-Carlo based simulators or in several cryptographic schemes.
 These domains need PRNGs that are statistically irreproachable. 
 In this paper, we focus on reproducible generators, useful for instance in
 Monte-Carlo based simulators or in several cryptographic schemes.
 These domains need PRNGs that are statistically irreproachable. 

-On some fields as in numerical simulations, speed is a strong requirement
+In some fields such as in numerical simulations, speed is a strong requirement

 that is usually attained by using parallel architectures. In that case,
 that is usually attained by using parallel architectures. In that case,

-a recurrent problem is that a deflate of the statistical qualities is often
+a recurrent problem is that a deflation of the statistical qualities is often

 reported, when the parallelization of a good PRNG is realized.
 This is why ad-hoc PRNGs for each possible architecture must be found to
 achieve both speed and randomness.
 On the other side, speed is not the main requirement in cryptography: the great
 reported, when the parallelization of a good PRNG is realized.
 This is why ad-hoc PRNGs for each possible architecture must be found to
 achieve both speed and randomness.
 On the other side, speed is not the main requirement in cryptography: the great

-need is to define \emph{secure} generators being able to withstand malicious
+need is to define \emph{secure} generators able to withstand malicious

 attacks. Roughly speaking, an attacker should not be able in practice to make 
 the distinction between numbers obtained with the secure generator and a true random
 sequence. 
 attacks. Roughly speaking, an attacker should not be able in practice to make 
 the distinction between numbers obtained with the secure generator and a true random
 sequence. 

-Finally, a small part of the community working in this domain focus on a
+Finally, a small part of the community working in this domain focuses on a

 third requirement, that is to define chaotic generators.
 The main idea is to take benefits from a chaotic dynamical system to obtain a
 generator that is unpredictable, disordered, sensible to its seed, or in other word chaotic.
 third requirement, that is to define chaotic generators.
 The main idea is to take benefits from a chaotic dynamical system to obtain a
 generator that is unpredictable, disordered, sensible to its seed, or in other word chaotic.


@@ -95,7 +95,7 @@ This is why the use of chaos for PRNG still remains marginal and disputable.
 The authors' opinion is that topological properties of disorder, as they are
 properly defined in the mathematical theory of chaos, can reinforce the quality
 of a PRNG. But they are not substitutable for security or statistical perfection.
 The authors' opinion is that topological properties of disorder, as they are
 properly defined in the mathematical theory of chaos, can reinforce the quality
 of a PRNG. But they are not substitutable for security or statistical perfection.

-Indeed, to the authors' point of view, such properties can be useful in the two following situations. On the
+Indeed, to the authors' mind, such properties can be useful in the two following situations. On the

 one hand, a post-treatment based on a chaotic dynamical system can be applied
 to a PRNG statistically deflective, in order to improve its statistical 
 properties. Such an improvement can be found, for instance, in~\cite{bgw09:ip,bcgr11:ip}.
 one hand, a post-treatment based on a chaotic dynamical system can be applied
 to a PRNG statistically deflective, in order to improve its statistical 
 properties. Such an improvement can be found, for instance, in~\cite{bgw09:ip,bcgr11:ip}.


@@ -110,7 +110,7 @@ Let us finish this paragraph by noticing that, in this paper,
 statistical perfection refers to the ability to pass the whole 
 {\it BigCrush} battery of tests, which is widely considered as the most
 stringent statistical evaluation of a sequence claimed as random.
 statistical perfection refers to the ability to pass the whole 
 {\it BigCrush} battery of tests, which is widely considered as the most
 stringent statistical evaluation of a sequence claimed as random.

-This battery can be found into the well-known TestU01 package~\cite{LEcuyerS07}.
+This battery can be found in the well-known TestU01 package~\cite{LEcuyerS07}.

 Chaos, for its part, refers to the well-established definition of a
 chaotic dynamical system proposed by Devaney~\cite{Devaney}.
 
 Chaos, for its part, refers to the well-established definition of a
 chaotic dynamical system proposed by Devaney~\cite{Devaney}.
 


@@ -131,11 +131,11 @@ applications. Therefore,  it is important  to be able to  generate pseudorandom
 numbers inside a GPU when a scientific application runs in it. This remark
 motivates our proposal of a chaotic and statistically perfect PRNG for GPU.  
 Such device
 numbers inside a GPU when a scientific application runs in it. This remark
 motivates our proposal of a chaotic and statistically perfect PRNG for GPU.  
 Such device

-allows us to generated almost 20 billions of pseudorandom numbers per second.
+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.
 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 rewritten of the Blum-Goldwasser asymmetric
+Last, but not least, we propose a rewritting 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
 key encryption protocol by using the proposed method.
 
 The remainder of this paper  is organized as follows. In Section~\ref{section:related


@@ -165,8 +165,8 @@ summarized and intended future work is presented.
 \section{Related works on GPU based PRNGs}
 \label{section:related works}
 
 \section{Related works on GPU based PRNGs}
 \label{section:related works}
 

-Numerous research works on defining GPU based PRNGs have yet been proposed  in the
-literature, so that completeness is impossible.
+Numerous research works on defining GPU based PRNGs have already been proposed  in the
+literature, so that exhaustivity is impossible.

 This is why authors of this document only give reference to the most significant attempts 
 in this domain, from their subjective point of view. 
 The  quantity of pseudorandom numbers generated per second is mentioned here 
 This is why authors of this document only give reference to the most significant attempts 
 in this domain, from their subjective point of view. 
 The  quantity of pseudorandom numbers generated per second is mentioned here 


@@ -184,7 +184,7 @@ chaos or cryptography in this document.
 In \cite{ZRKB10}, the authors propose  different versions of efficient GPU PRNGs
 based on  Lagged Fibonacci or Hybrid  Taus.  They have  used these
 PRNGs   for  Langevin   simulations   of  biomolecules   fully  implemented   on
 In \cite{ZRKB10}, the authors propose  different versions of efficient GPU PRNGs
 based on  Lagged Fibonacci or Hybrid  Taus.  They have  used these
 PRNGs   for  Langevin   simulations   of  biomolecules   fully  implemented   on

-GPU. Performance of  the GPU versions are far better than  those obtained with a
+GPU. Performances of  the GPU versions are far better than  those obtained with a

 CPU, and these PRNGs succeed to pass the {\it BigCrush} battery of TestU01. 
 However the evaluations of the proposed PRNGs are only statistical ones.
 
 CPU, and these PRNGs succeed to pass the {\it BigCrush} battery of TestU01. 
 However the evaluations of the proposed PRNGs are only statistical ones.
 


@@ -200,7 +200,7 @@ However, we notice that authors can ``only'' generate between 11 and 16GSamples/
 with a GTX 280  GPU, which should be compared with
 the results presented in this document.
 We can remark too that the PRNGs proposed in~\cite{conf/fpga/ThomasHL09} are only
 with a GTX 280  GPU, which should be compared with
 the results presented in this document.
 We can remark too that the PRNGs proposed in~\cite{conf/fpga/ThomasHL09} are only

-able to pass the {\it Crush} battery, which is very easy compared to the {\it Big Crush} one.
+able to pass the {\it Crush} battery, which is far easier than the {\it Big Crush} one.

 
 Lastly, Cuda  has developed  a  library for  the  generation of  pseudorandom numbers  called
 Curand~\cite{curand11}.        Several       PRNGs        are       implemented, among
 
 Lastly, Cuda  has developed  a  library for  the  generation of  pseudorandom numbers  called
 Curand~\cite{curand11}.        Several       PRNGs        are       implemented, among


@@ -210,7 +210,7 @@ their  fastest version provides  15GSamples/s on  the new  Fermi C2050  card.
 But their PRNGs cannot pass the whole TestU01 battery (only one test is failed).
 \newline
 \newline
 But their PRNGs cannot pass the whole TestU01 battery (only one test is failed).
 \newline
 \newline

-We can finally remark that, to the best of our knowledge, no GPU implementation have been proven to be chaotic, and the cryptographically secure property is surprisingly never regarded.
+We can finally remark that, to the best of our knowledge, no GPU implementation has been proven to be chaotic, and the cryptographically secure property has surprisingly never been considered.

 
 \section{Basic Recalls}
 \label{section:BASIC RECALLS}
 
 \section{Basic Recalls}
 \label{section:BASIC RECALLS}


@@ -384,9 +384,9 @@ their distance should increase too.
 \item In addition, if two systems present the same cells and their respective
 strategies start with the same terms, then the distance between these two points
 must be small because the evolution of the two systems will be the same for a
 \item In addition, if two systems present the same cells and their respective
 strategies start with the same terms, then the distance between these two points
 must be small because the evolution of the two systems will be the same for a

-while. Indeed, the two dynamical systems start with the same initial condition,
-use the same update function, and as strategies are the same for a while, then
-components that are updated are the same too.
+while. Indeed, both dynamical systems start with the same initial condition,
+use the same update function, and as strategies are the same for a while, furthermore
+updated components are the same as well.

 \end{itemize}
 The distance presented above follows these recommendations. Indeed, if the floor
 value $\lfloor d(X,Y)\rfloor $ is equal to $n$, then the systems $E, \check{E}$
 \end{itemize}
 The distance presented above follows these recommendations. Indeed, if the floor
 value $\lfloor d(X,Y)\rfloor $ is equal to $n$, then the systems $E, \check{E}$


@@ -395,7 +395,7 @@ 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.
 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.
+The impact of this choice for a distance will be investigated at the end of the document.

 
 Finally, it has been established in \cite{guyeux10} that,
 
 
 Finally, it has been established in \cite{guyeux10} that,
 


@@ -445,15 +445,15 @@ Finally, we have established in \cite{bcgr11:ip} that,
 \end{theorem} 
 
 
 \end{theorem} 
 
 

-These results of chaos and uniform distribution have lead us to study the possibility to build a
+These results of chaos and uniform distribution have led us to study the possibility of building a

 pseudorandom number generator (PRNG) based on the chaotic iterations. 
 As $G_f$, defined on the domain   $\llbracket 1 ;  \mathsf{N} \rrbracket^{\mathds{N}} 
 pseudorandom number generator (PRNG) based on the chaotic iterations. 
 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}
+\times \mathds{B}^\mathsf{N}$, is built 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$). Indeed, it is as if
 $\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, in PRNG, or a physical noise in TRNG).
 \rightarrow \mathds{B}^\mathsf{N}$, we can preserve the theoretical properties on $G_f$
 during implementations (due to the discrete nature of $f$). Indeed, it is as if
 $\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, in PRNG, or a physical noise in TRNG).

-Let us finally remark that the vectorial negation satisfies the hypotheses of the two theorems above.
+Let us finally remark that the vectorial negation satisfies the hypotheses of both theorems above.

 
 \section{Application to Pseudorandomness}
 \label{sec:pseudorandom}
 
 \section{Application to Pseudorandomness}
 \label{sec:pseudorandom}


@@ -507,7 +507,7 @@ It takes as input: a Boolean function $f$ satisfying Theorem~\ref{Th:Caractéris
 an integer $b$, ensuring that the number of executed iterations is at least $b$
 and at most $2b+1$; and an initial configuration $x^0$.
 It returns the new generated configuration $x$.  Internally, it embeds two
 an integer $b$, ensuring that the number of executed iterations is at least $b$
 and at most $2b+1$; and an initial configuration $x^0$.
 It returns the new generated configuration $x$.  Internally, it embeds two

-\textit{XORshift}$(k)$ PRNGs~\cite{Marsaglia2003} that returns integers
+\textit{XORshift}$(k)$ PRNGs~\cite{Marsaglia2003} that return integers

 uniformly distributed
 into $\llbracket 1 ; k \rrbracket$.
 \textit{XORshift} is a category of very fast PRNGs designed by George Marsaglia,
 uniformly distributed
 into $\llbracket 1 ; k \rrbracket$.
 \textit{XORshift} is a category of very fast PRNGs designed by George Marsaglia,


@@ -536,7 +536,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. 
 \label{equation Oplus}
 \end{equation}
 where $\oplus$ is for the bitwise exclusive or between two integers. 

-This rewritten can be understood as follows. The $n-$th term $S^n$ of the
+This rewritting 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 
 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 


@@ -560,13 +560,12 @@ where $f$ is the vectorial negation and $\forall n \in \mathds{N}$,
 $\mathcal{S}^n \subset \llbracket 1, \mathsf{N} \rrbracket$ is such that
 $k \in \mathcal{S}^n$ if and only if the $k-$th digit in the binary
 decomposition of $S^n$ is 1. Such chaotic iterations are more general
 $\mathcal{S}^n \subset \llbracket 1, \mathsf{N} \rrbracket$ is such that
 $k \in \mathcal{S}^n$ if and only if the $k-$th digit in the binary
 decomposition of $S^n$ is 1. Such chaotic iterations are more general

-than the ones presented in Definition \ref{Def:chaotic iterations} for 
-the fact that, instead of updating only one term at each iteration,
+than the ones presented in Definition \ref{Def:chaotic iterations} because, instead of updating only one term at each iteration,

 we select a subset of components to change.
 
 
 Obviously, replacing Algorithm~\ref{CI Algorithm} by 
 we select a subset of components to change.
 
 
 Obviously, replacing Algorithm~\ref{CI Algorithm} by 

-Equation~\ref{equation Oplus}, possible when the iteration function is
+Equation~\ref{equation Oplus}, which is possible when the iteration function is

 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 
 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 


@@ -640,7 +639,7 @@ X^{k+1}=G_{f}(X^k).%
 \right.
 \end{equation}%
 
 \right.
 \end{equation}%
 

-Another time, a shift function appears as a component of these general chaotic 
+Once more, a shift function appears as a component of these general chaotic 

 iterations. 
 
 To study the Devaney's chaos property, a distance between two points 
 iterations. 
 
 To study the Devaney's chaos property, a distance between two points 


@@ -655,7 +654,7 @@ d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}),
 \left\{
 \begin{array}{lll}
 \displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}%
 \left\{
 \begin{array}{lll}
 \displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}%

-}\delta (E_{k},\check{E}_{k})}\textrm{ is another time the Hamming distance}, \\
+}\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}%
 \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}%


@@ -671,7 +670,7 @@ The function $d$ defined in Eq.~\ref{nouveau d} is a metric on $\mathcal{X}$.
 
 \begin{proof}
  $d_e$ is the Hamming distance. We will prove that $d_s$ is a distance
 
 \begin{proof}
  $d_e$ is the Hamming distance. We will prove that $d_s$ is a distance

-too, thus $d$ will be a distance as sum of two distances.
+too, thus $d$, as being the sum of two distances, will also be a distance.

  \begin{itemize}
 \item Obviously, $d_s(S,\check{S})\geqslant 0$, and if $S=\check{S}$, then 
 $d_s(S,\check{S})=0$. Conversely, if $d_s(S,\check{S})=0$, then 
  \begin{itemize}
 \item Obviously, $d_s(S,\check{S})\geqslant 0$, and if $S=\check{S}$, then 
 $d_s(S,\check{S})=0$. Conversely, if $d_s(S,\check{S})=0$, then 


@@ -688,7 +687,7 @@ inequality is obtained.
 
 
 Before being able to study the topological behavior of the general 
 
 
 Before being able to study the topological behavior of the general 

-chaotic iterations, we must firstly establish that:
+chaotic iterations, we must first establish that:

 
 \begin{proposition}
  For all $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, the function $G_f$ is continuous on 
 
 \begin{proposition}
  For all $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, the function $G_f$ is continuous on 


@@ -724,7 +723,7 @@ so, after the $max(n_0, n_1)^{th}$ term, the distance $d$ between these two poin
 G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is convergent to
 0. Let $\varepsilon >0$. \medskip
 \begin{itemize}
 G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is convergent to
 0. Let $\varepsilon >0$. \medskip
 \begin{itemize}

-\item If $\varepsilon \geqslant 1$, we see that distance
+\item If $\varepsilon \geqslant 1$, we see that the distance

 between $\left( G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is
 strictly less than 1 after the $max(n_{0},n_{1})^{th}$ term (same state).
 \medskip
 between $\left( G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is
 strictly less than 1 after the $max(n_{0},n_{1})^{th}$ term (same state).
 \medskip


@@ -786,7 +785,7 @@ where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties
 claimed in the lemma.
 \end{proof}
 
 claimed in the lemma.
 \end{proof}
 

-We can now prove the Theorem~\ref{t:chaos des general}...
+We can now prove Theorem~\ref{t:chaos des general}...

 
 \begin{proof}[Theorem~\ref{t:chaos des general}]
 Firstly, strong transitivity implies transitivity.
 
 \begin{proof}[Theorem~\ref{t:chaos des general}]
 Firstly, strong transitivity implies transitivity.


@@ -888,7 +887,7 @@ works with 32-bits, we use the command \texttt{(unsigned int)}, that selects the
 32 least  significant bits  of a given  integer, and the  code \texttt{(unsigned
   int)(t$>>$32)} in order to obtain the 32 most significant bits of \texttt{t}.
 
 32 least  significant bits  of a given  integer, and the  code \texttt{(unsigned
   int)(t$>>$32)} in order to obtain the 32 most significant bits of \texttt{t}.
 

-So producing a pseudorandom number needs 6 xor operations with 6 32-bits numbers
+Thus producing a pseudorandom number needs 6 xor operations with 6 32-bits numbers

 that  are provided by  3 64-bits  PRNGs.  This  version successfully  passes the
 stringent BigCrush battery of tests~\cite{LEcuyerS07}.
 
 that  are provided by  3 64-bits  PRNGs.  This  version successfully  passes the
 stringent BigCrush battery of tests~\cite{LEcuyerS07}.
 


@@ -903,10 +902,10 @@ 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
 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  recall  that  in  the  CUDA~\cite{Nvid10}
+do  so,  we  must   firstly  remind  that  in  the  CUDA~\cite{Nvid10}

 environment,    threads    have     a    local    identifier    called
 \texttt{ThreadIdx},  which   is  relative  to   the  block  containing
 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
+them. Furthermore, in  CUDA, parts of  the code that are executed by the  GPU, are

 called {\it kernels}.
 
 
 called {\it kernels}.
 
 


@@ -914,7 +913,7 @@ called {\it kernels}.
 
  
 It is possible to deduce from the CPU version a quite similar version adapted to GPU.
 
  
 It is possible to deduce from the CPU version a quite similar version adapted to GPU.

-The simple principle consists to make each thread of the GPU computing the CPU version of our PRNG.  
+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
 Of course,  the  three xor-like
 PRNGs  used in these computations must have different  parameters. 
 In a given thread, these lasts are


@@ -962,14 +961,14 @@ and  the pseudorandom  numbers generated by  our  PRNG,  is  equal to  $100,000\
 
 This generator is able to pass the whole BigCrush battery of tests, for all
 the versions that have been tested depending on their number of threads 
 
 This generator is able to pass the whole BigCrush battery of tests, for all
 the versions that have been tested depending on their number of threads 

-(called \texttt{NumThreads} in our algorithm, tested until $10$ millions).
+(called \texttt{NumThreads} in our algorithm, tested up to $5$ million).

 
 \begin{remark}
 
 \begin{remark}

-The proposed algorithm has  the  advantage to  manipulate  independent
+The proposed algorithm has  the  advantage of  manipulating  independent

 PRNGs, so this version is easily adaptable on a cluster of computers too. The only thing
 to ensure is to use a single ISAAC PRNG. To achieve this requirement, a simple solution consists in
 using a master node for the initialization. This master node computes the initial parameters
 PRNGs, so this version is easily adaptable on a cluster of computers too. The only thing
 to ensure is to use a single ISAAC PRNG. To achieve this requirement, a simple solution consists in
 using a master node for the initialization. This master node computes the initial parameters

-for all the differents nodes involves in the computation.
+for all the different nodes involved in the computation.

 \end{remark}
 
 \subsection{Improved Version for GPU}
 \end{remark}
 
 \subsection{Improved Version for GPU}


@@ -992,7 +991,7 @@ been chosen. In practice, we  use the xor128 proposed in~\cite{Marsaglia2003} in
 which  unsigned longs  (64 bits)  have been  replaced by  unsigned  integers (32
 bits).
 
 which  unsigned longs  (64 bits)  have been  replaced by  unsigned  integers (32
 bits).
 

-This version also can pass the whole {\it BigCrush} battery of tests.
+This version  can also pass the whole {\it BigCrush} battery of tests.

 
 \begin{algorithm}
 
 
 \begin{algorithm}
 


@@ -1034,7 +1033,7 @@ and two values previously obtained by two other threads).
 To be certain that we are in the framework of Theorem~\ref{t:chaos des general},
 we must guarantee that this dynamical system iterates on the space 
 $\mathcal{X} = \mathcal{P}\left(\llbracket 1, \mathsf{N} \rrbracket\right)^\mathds{N}\times\mathds{B}^\mathsf{N}$.
 To be certain that we are in the framework of Theorem~\ref{t:chaos des general},
 we must guarantee that this dynamical system iterates on the space 
 $\mathcal{X} = \mathcal{P}\left(\llbracket 1, \mathsf{N} \rrbracket\right)^\mathds{N}\times\mathds{B}^\mathsf{N}$.

-The left term $x$ obviously belongs into $\mathds{B}^ \mathsf{N}$.
+The left term $x$ obviously belongs to $\mathds{B}^ \mathsf{N}$.

 To prevent from any flaws of chaotic properties, we must check that the right 
 term (the last $t$), corresponding to the strategies,  can possibly be equal to any
 integer of $\llbracket 1, \mathsf{N} \rrbracket$. 
 To prevent from any flaws of chaotic properties, we must check that the right 
 term (the last $t$), corresponding to the strategies,  can possibly be equal to any
 integer of $\llbracket 1, \mathsf{N} \rrbracket$. 


@@ -1071,7 +1070,7 @@ into the GPU memory has been removed. This step is time consuming and slows down
 generation.  Moreover this   storage  is  completely
 useless, in case of applications that consume the pseudorandom
 numbers  directly   after generation. We can see  that when the number of  threads is greater
 generation.  Moreover this   storage  is  completely
 useless, in case of applications that consume the pseudorandom
 numbers  directly   after generation. We can see  that when the number of  threads is greater

-than approximately 30,000 and lower than 5 millions, the number of pseudorandom numbers generated
+than approximately 30,000 and lower than 5 million, the number of pseudorandom numbers generated

 per second  is almost constant.  With the  naive version, this value ranges from 2.5 to
 3GSamples/s.   With  the  optimized   version,  it  is  approximately  equal to
 20GSamples/s. Finally  we can remark  that both GPU  cards are quite  similar, but in
 per second  is almost constant.  With the  naive version, this value ranges from 2.5 to
 3GSamples/s.   With  the  optimized   version,  it  is  approximately  equal to
 20GSamples/s. Finally  we can remark  that both GPU  cards are quite  similar, but in


@@ -1092,13 +1091,12 @@ As a  comparison,   Listing~\ref{algo:seqCIPRNG}  leads   to the  generation of
 
 
 
 
 
 

-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
-reduction. 
+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
+reduction.

 
 \begin{figure}[htbp]
 \begin{center}
 
 \begin{figure}[htbp]
 \begin{center}


@@ -1339,20 +1337,24 @@ on the variable  $t$ and stores the result in  $t$, and $BBS1(bbs1)\&15$ selects
 the last  four bits  of the  result of $BBS1$.   Thus an  operation of  the form
 $t<<=4; t|=BBS1(bbs1)\&15\;$  realizes in $t$ a  left shift of 4  bits, and then
 puts the 4 last bits of $BBS1(bbs1)$  in the four last positions of $t$.  Let us
 the last  four bits  of the  result of $BBS1$.   Thus an  operation of  the form
 $t<<=4; t|=BBS1(bbs1)\&15\;$  realizes in $t$ a  left shift of 4  bits, and then
 puts the 4 last bits of $BBS1(bbs1)$  in the four last positions of $t$.  Let us

-remark that to initialize $t$ is not a necessity as we fill it 4 bits by 4 bits,
-until having obtained 32-bits.  The two last new shifts are realized in order to
-enlarge  the  small periods  of  the  BBS used  here,  to  introduce  a kind  of
+remark that the initialization $t$ is not a  necessity as we fill it 4 bits by 4
+bits, until  having obtained 32-bits.  The  two last new shifts  are realized in
+order to enlarge the small periods of  the BBS used here, to introduce a kind of

 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}
 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$.
+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
+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).

 
 

-It should  be noticed that this generator has another time the form $x^{n+1} = x^n \oplus S^n$,
+It should  be noticed that this generator has once more the form $x^{n+1} = x^n \oplus S^n$,

 where $S^n$ is referred in this algorithm as $t$: each iteration of this
 PRNG ends with $x = x \wedge t$. This $S^n$ is only constituted
 by secure bits produced by the BBS generator, and thus, due to
 Proposition~\ref{cryptopreuve}, the resulted PRNG is cryptographically
 where $S^n$ is referred in this algorithm as $t$: each iteration of this
 PRNG ends with $x = x \wedge t$. This $S^n$ is only constituted
 by secure bits produced by the BBS generator, and thus, due to
 Proposition~\ref{cryptopreuve}, the resulted PRNG is cryptographically

-secure
+secure.