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

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 7d94e0c..777ebbf 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -38,7 +38,7 @@
 \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
 
@@ -135,7 +135,7 @@ allows us to generate almost 20 billion of pseudorandom numbers per second.
 Furthermore, we show that the proposed post-treatment preserves the
 cryptographical security of the inputted PRNG, when this last has such a 
 property.
-Last, but not least, we propose a rewritting of the Blum-Goldwasser asymmetric
+Last, but not least, we propose a rewriting of the Blum-Goldwasser asymmetric
 key encryption protocol by using the proposed method.
 
 The remainder of this paper  is organized as follows. In Section~\ref{section:related
@@ -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. 
-This rewritting can be understood as follows. The $n-$th term $S^n$ of the
+This rewriting can be understood as follows. The $n-$th term $S^n$ of the
 sequence $S$, which is an integer of $\mathsf{N}$ binary digits, presents
 the list of cells to update in the state $x^n$ of the system (represented
 as an integer having $\mathsf{N}$ bits too). More precisely, the $k-$th 
@@ -950,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
-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)},
@@ -1128,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
-seed $k$ of length $k$, $G(k)$ (the output of $G$ on the input $k$) has size
-$\ell_G(k)$ with $\ell_G(k)>k$.
+seed $s$ of length $m$, $G(s)$ (the output of $G$ on the input $s$) has size
+$\ell_G(m)$ with $\ell_G(m)>m$.
 The notion of {\it secure} PRNGs can now be defined as follows. 
 
 \begin{definition}
 A cryptographic PRNG $G$ is secure if for any probabilistic polynomial time
 algorithm $D$, for any positive polynomial $p$, and for all sufficiently
-large $k$'s,
-$$| \mathrm{Pr}[D(G(U_k))=1]-Pr[D(U_{\ell_G(k)})=1]|< \frac{1}{p(k)},$$
+large $m$'s,
+$$| \mathrm{Pr}[D(G(U_m))=1]-Pr[D(U_{\ell_G(m)})=1]|< \frac{1}{p(m)},$$
 where $U_r$ is the uniform distribution over $\{0,1\}^r$ and the
-probabilities are taken over $U_N$, $U_{\ell_G(N)}$ as well as over the
+probabilities are taken over $U_m$, $U_{\ell_G(m)}$ as well as over the
 internal coin tosses of $D$. 
 \end{definition}
 
@@ -1147,7 +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
-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,
@@ -1255,7 +1255,7 @@ lesser than $2^{16}$.  So in practice we can choose prime numbers around
 indistinguishable    bits    is    lesser    than   or    equals    to
 $log_2(log_2(M))$). In other words, to generate a  32-bits number, we need to use
 8 times  the BBS  algorithm with possibly different  combinations of  $M$. This
-approach is  not sufficient to be able to pass  all the TestU01,
+approach is  not sufficient to be able to pass  all the tests of TestU01,
 as small values of  $M$ for the BBS  lead to
   small periods. So, in  order to add randomness  we have proceeded with
 the followings  modifications. 
@@ -1344,7 +1344,7 @@ variability.  In these operations, we make twice a left shift of $t$ of \emph{at
   most}  3 bits,  represented by  \texttt{shift} in  the algorithm,  and  we put
 \emph{exactly} the \texttt{shift}  last bits from a BBS  into the \texttt{shift}
 last bits of $t$. For this, an array named \texttt{array\_shift}, containing the
-correspondance between the  shift and the number obtained  with \texttt{shift} 1
+correspondence between the  shift and the number obtained  with \texttt{shift} 1
 to make the \texttt{and} operation is used. For example, with a left shift of 0,
 we  make an  and operation  with 0,  with  a left  shift of  3, we  make an  and
 operation with 7 (represented by 111 in binary mode).