new

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 1129a07e18b89155ea4519ec23c979dbe397df71..efcc4d5b9e498fac895b84012b17d34325efea9e 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -949,17 +949,18 @@ It is  possible to build a  cryptographically secure prng based  on the previous
 algorithm (algorithm~\ref{algo:gpu_kernel2}).   It simply consists  in replacing
 the  {\it  xor-like} algorithm  by  another  cryptographically  secure prng.  In
 practice, we suggest  to use the BBS algorithm~\cite{BBS}  which takes the form:
 algorithm (algorithm~\ref{algo:gpu_kernel2}).   It simply consists  in replacing
 the  {\it  xor-like} algorithm  by  another  cryptographically  secure prng.  In
 practice, we suggest  to use the BBS algorithm~\cite{BBS}  which takes the form:

-$$x_{n+1}=x_n^2~ mod~  M$$ where M  is the product  of the prime  numbers. Those
+$$x_{n+1}=x_n^2~ mod~ M$$  where $M$ is the product of  two prime numbers. Those

 prime numbers  need to be congruent  to 3 modulus  4. In practice, this  PRNG is
 known to  be slow and  not efficient for  the generation of random  numbers. For
 current  GPU   cards,  the  modulus   operation  is  the  most   time  consuming
 operation. So in  order to obtain quite reasonable  performances, it is required
 to use only modulus on 32  bits integer numbers. Consequently $x_n^2$ need to be
 less than  $2^{32}$ and the  number $M$  need to be  less than $2^{16}$.   So in
 prime numbers  need to be congruent  to 3 modulus  4. In practice, this  PRNG is
 known to  be slow and  not efficient for  the generation of random  numbers. For
 current  GPU   cards,  the  modulus   operation  is  the  most   time  consuming
 operation. So in  order to obtain quite reasonable  performances, it is required
 to use only modulus on 32  bits integer numbers. Consequently $x_n^2$ need to be
 less than  $2^{32}$ and the  number $M$  need to be  less than $2^{16}$.   So in

-pratice we can choose prime number around 256 that are congruent to 3 modulus 4.
-With 32 bits numbers,  only the 4 least significant bits of  $x_n$ can be chosen
-(the   maximum    number   of   undistinguishing   is   less    or   equals   to
-$log_2(log_2(x_n))$).
+pratice we can  choose prime numbers around 256 that are  congruent to 3 modulus
+4.  With  32 bits numbers,  only the  4 least significant  bits of $x_n$  can be
+chosen  (the   maximum  number  of   undistinguishing  is  less  or   equals  to
+$log_2(log_2(x_n))$). So  to generate a 32 bits  number, we need to  use 8 times
+the BBS algorithm, with different combinations of $M$ is required.

 
 \section{Experiments}
 \label{sec:experiments}
 
 \section{Experiments}
 \label{sec:experiments}