modif

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 4feac7cc64b8730163298a05ba2edca48d894eeb..777ebbf2761f384c8fa44d9a5af107cda30fba60 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -38,7 +38,7 @@
 \begin{document}
 
 \author{Jacques M. Bahi, Rapha\"{e}l Couturier,  Christophe
 \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
 
    
 \maketitle
 


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


@@ -825,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 
 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.
 
 
 obtain some statistical improvements while preserving speed.
 
 


@@ -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}.
 


@@ -906,7 +905,7 @@ a   program    similar   to    the   one   presented    in  Listing
 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
 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
+them. Furthermore, in  CUDA, parts of  the code that are executed by the  GPU, are

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


@@ -914,10 +913,10 @@ 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. 
 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
 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


@@ -951,7 +950,7 @@ NumThreads: number of threads\;}
 
 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
 
 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)},
 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)},


@@ -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  necessarily paid by  a speed
+reduction.

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


@@ -1110,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.
 
 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.
 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.


@@ -1130,17 +1128,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
 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
 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
 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}
 
 internal coin tosses of $D$. 
 \end{definition}
 


@@ -1149,7 +1147,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
 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,
 
 The generation schema developed in (\ref{equation Oplus}) is based on a
 pseudorandom generator. Let $H$ be a cryptographic PRNG. We may assume,


@@ -1160,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
 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.
 
 We claim now that if this PRNG is secure,
 then the new one is secure too.
 


@@ -1224,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
 \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)},$$
 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}
 
 
 \end{proof}
 
 


@@ -1257,21 +1255,21 @@ 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
 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
 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 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
 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
 \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


@@ -1279,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
 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.
 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.


@@ -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
+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).

 
 

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

 
 
 
 
 
 


@@ -1399,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 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}
 
 
 \end{enumerate}
 
 


@@ -1419,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)$.
 
 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.
 
 By doing so, the proposed generator is used in place of BBS, leading to
 the inheritance of all the properties presented in this paper.
 


@@ -1430,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
 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
 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