Merge branch 'master' of ssh://info.iut-bm.univ-fcomte.fr/prng_gpu

[prng_gpu.git] / prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 6c6c980902aed3f6118d9295261631f4b886fffd..55fc756560f07eab5d8a70a102c4798e8551a695 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -1,4 +1,5 @@
-\documentclass{article}
+%\documentclass{article}
+\documentclass[10pt,journal,letterpaper,compsoc]{IEEEtran}

 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
 \usepackage{fullpage}
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
 \usepackage{fullpage}


@@ -38,10 +39,10 @@
 \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

 
 

+\IEEEcompsoctitleabstractindextext{

 \begin{abstract}
 In this paper we present a new pseudorandom number generator (PRNG) on
 graphics processing units  (GPU). This PRNG is based  on the so-called chaotic iterations.  It
 \begin{abstract}
 In this paper we present a new pseudorandom number generator (PRNG) on
 graphics processing units  (GPU). This PRNG is based  on the so-called chaotic iterations.  It


@@ -56,6 +57,13 @@ A chaotic version of the Blum-Goldwasser asymmetric key encryption scheme is fin
 
 
 \end{abstract}
 
 
 \end{abstract}

+}
+
+\maketitle
+
+\IEEEdisplaynotcompsoctitleabstractindextext
+\IEEEpeerreviewmaketitle
+

 
 \section{Introduction}
 
 
 \section{Introduction}
 


@@ -216,7 +224,10 @@ We can finally remark that, to the best of our knowledge, no GPU implementation
 \label{section:BASIC RECALLS}
 
 This section is devoted to basic definitions and terminologies in the fields of
 \label{section:BASIC RECALLS}
 
 This section is devoted to basic definitions and terminologies in the fields of

-topological chaos and chaotic iterations.
+topological chaos and chaotic iterations. We assume the reader is familiar
+with basic notions on topology (see for instance~\cite{Devaney}).
+
+

 \subsection{Devaney's Chaotic Dynamical Systems}
 
 In the sequel $S^{n}$ denotes the $n^{th}$ term of a sequence $S$ and $V_{i}$
 \subsection{Devaney's Chaotic Dynamical Systems}
 
 In the sequel $S^{n}$ denotes the $n^{th}$ term of a sequence $S$ and $V_{i}$


@@ -229,7 +240,7 @@ Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f :
 \mathcal{X} \rightarrow \mathcal{X}$.
 
 \begin{definition}
 \mathcal{X} \rightarrow \mathcal{X}$.
 
 \begin{definition}

-$f$ is said to be \emph{topologically transitive} if, for any pair of open sets
+The function $f$ is said to be \emph{topologically transitive} if, for any pair of open sets

 $U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq
 \varnothing$.
 \end{definition}
 $U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq
 \varnothing$.
 \end{definition}


@@ -248,7 +259,7 @@ necessarily the same period).
 
 
 \begin{definition}[Devaney's formulation of chaos~\cite{Devaney}]
 
 
 \begin{definition}[Devaney's formulation of chaos~\cite{Devaney}]

-$f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and
+The function $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and

 topologically transitive.
 \end{definition}
 
 topologically transitive.
 \end{definition}
 


@@ -256,12 +267,12 @@ The chaos property is strongly linked to the notion of ``sensitivity'', defined
 on a metric space $(\mathcal{X},d)$ by:
 
 \begin{definition}
 on a metric space $(\mathcal{X},d)$ by:
 
 \begin{definition}

-\label{sensitivity} $f$ has \emph{sensitive dependence on initial conditions}
+\label{sensitivity} The function $f$ has \emph{sensitive dependence on initial conditions}

 if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any
 neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that
 $d\left(f^{n}(x), f^{n}(y)\right) >\delta $.
 
 if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any
 neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that
 $d\left(f^{n}(x), f^{n}(y)\right) >\delta $.
 

-$\delta$ is called the \emph{constant of sensitivity} of $f$.
+The constant $\delta$ is called the \emph{constant of sensitivity} of $f$.

 \end{definition}
 
 Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is
 \end{definition}
 
 Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is


@@ -321,11 +332,13 @@ are continuous. For further explanations, see, e.g., \cite{guyeux10}.
 
 Let $\delta $ be the \emph{discrete Boolean metric}, $\delta
 (x,y)=0\Leftrightarrow x=y.$ Given a function $f$, define the function:
 
 Let $\delta $ be the \emph{discrete Boolean metric}, $\delta
 (x,y)=0\Leftrightarrow x=y.$ Given a function $f$, define the function:

+%%RAPH : ici j'ai coupé la dernière ligne en 2, c'est moche mais bon

 \begin{equation}
 \begin{array}{lrll}
 F_{f}: & \llbracket1;\mathsf{N}\rrbracket\times \mathds{B}^{\mathsf{N}} &
 \longrightarrow & \mathds{B}^{\mathsf{N}} \\
 \begin{equation}
 \begin{array}{lrll}
 F_{f}: & \llbracket1;\mathsf{N}\rrbracket\times \mathds{B}^{\mathsf{N}} &
 \longrightarrow & \mathds{B}^{\mathsf{N}} \\

-& (k,E) & \longmapsto & \left( E_{j}.\delta (k,j)+f(E)_{k}.\overline{\delta
+& (k,E) & \longmapsto & \left( E_{j}.\delta (k,j)+ \right.\\
+&       &              & \left. f(E)_{k}.\overline{\delta

 (k,j)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},%
 \end{array}%
 \end{equation}%
 (k,j)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},%
 \end{array}%
 \end{equation}%


@@ -467,8 +480,9 @@ generator taken alone. Furthermore, our generator
 possesses various chaos properties that none of the generators used as input
 present.
 
 possesses various chaos properties that none of the generators used as input
 present.
 

+

 \begin{algorithm}[h!]
 \begin{algorithm}[h!]

-%\begin{scriptsize}
+\begin{small}

 \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$
 ($n$ bits)}
 \KwOut{a configuration $x$ ($n$ bits)}
 \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$
 ($n$ bits)}
 \KwOut{a configuration $x$ ($n$ bits)}


@@ -480,12 +494,16 @@ $s\leftarrow{\textit{XORshift}(n)}$\;
 $x\leftarrow{F_f(s,x)}$\;
 }
 return $x$\;
 $x\leftarrow{F_f(s,x)}$\;
 }
 return $x$\;

-%\end{scriptsize}
+\end{small}

 \caption{PRNG with chaotic functions}
 \label{CI Algorithm}
 \end{algorithm}
 
 \caption{PRNG with chaotic functions}
 \label{CI Algorithm}
 \end{algorithm}
 

+
+
+

 \begin{algorithm}[h!]
 \begin{algorithm}[h!]

+\begin{small}

 \KwIn{the internal configuration $z$ (a 32-bit word)}
 \KwOut{$y$ (a 32-bit word)}
 $z\leftarrow{z\oplus{(z\ll13)}}$\;
 \KwIn{the internal configuration $z$ (a 32-bit word)}
 \KwOut{$y$ (a 32-bit word)}
 $z\leftarrow{z\oplus{(z\ll13)}}$\;


@@ -493,7 +511,7 @@ $z\leftarrow{z\oplus{(z\gg17)}}$\;
 $z\leftarrow{z\oplus{(z\ll5)}}$\;
 $y\leftarrow{z}$\;
 return $y$\;
 $z\leftarrow{z\oplus{(z\ll5)}}$\;
 $y\leftarrow{z}$\;
 return $y$\;

-\medskip
+\end{small}

 \caption{An arbitrary round of \textit{XORshift} algorithm}
 \label{XORshift}
 \end{algorithm}
 \caption{An arbitrary round of \textit{XORshift} algorithm}
 \label{XORshift}
 \end{algorithm}


@@ -605,12 +623,13 @@ Let us introduce the following function:
 where $\mathcal{P}\left(X\right)$ is for the powerset of the set $X$, that is, $Y \in \mathcal{P}\left(X\right) \Longleftrightarrow Y \subset X$.
 
 Given a function $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, define the function:
 where $\mathcal{P}\left(X\right)$ is for the powerset of the set $X$, that is, $Y \in \mathcal{P}\left(X\right) \Longleftrightarrow Y \subset X$.
 
 Given a function $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, define the function:

+%%RAPH : j'ai coupé la dernière ligne en 2, c'est moche

 \begin{equation}
 \begin{array}{lrll}
 F_{f}: & \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} &
 \longrightarrow & \mathds{B}^{\mathsf{N}} \\
 \begin{equation}
 \begin{array}{lrll}
 F_{f}: & \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} &
 \longrightarrow & \mathds{B}^{\mathsf{N}} \\

-& (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+f(E)_{j}.\overline{\chi
-(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},%
+& (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+\right.\\
+&       &             &\left.f(E)_{j}.\overline{\chi(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},%

 \end{array}%
 \end{equation}%
 where + and . are the Boolean addition and product operations, and $\overline{x}$ 
 \end{array}%
 \end{equation}%
 where + and . are the Boolean addition and product operations, and $\overline{x}$ 


@@ -622,7 +641,7 @@ Consider the phase space:
 \end{equation}
 \noindent and the map defined on $\mathcal{X}$:
 \begin{equation}
 \end{equation}
 \noindent and the map defined on $\mathcal{X}$:
 \begin{equation}

-G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), \label{Gf}
+G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), %\label{Gf} %%RAPH, j'ai viré ce label qui existe déjà avant...

 \end{equation}
 \noindent where $\sigma$ is the \emph{shift} function defined by $\sigma
 (S^{n})_{n\in \mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow (S^{n+1})_{n\in
 \end{equation}
 \noindent where $\sigma$ is the \emph{shift} function defined by $\sigma
 (S^{n})_{n\in \mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow (S^{n+1})_{n\in


@@ -649,17 +668,21 @@ Let us introduce:
 d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}),
 \label{nouveau d}
 \end{equation}
 d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}),
 \label{nouveau d}
 \end{equation}

-\noindent where
-\begin{equation}
-\left\{
-\begin{array}{lll}
-\displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}%
-}\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}%
-\right.
-\end{equation}
+\noindent where $ \displaystyle{d_{e}(E,\check{E})} = \displaystyle{\sum_{k=1}^{\mathsf{N}%
+ }\delta (E_{k},\check{E}_{k})}$  is once more the Hamming distance, and
+$  \displaystyle{d_{s}(S,\check{S})}  =  \displaystyle{\dfrac{9}{\mathsf{N}}%
+ \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}$,
+%%RAPH : ici, j'ai supprimé tous les sauts à la ligne
+%% \begin{equation}
+%% \left\{
+%% \begin{array}{lll}
+%% \displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}%
+%% }\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}%
+%% \right.
+%% \end{equation}

 where $|X|$ is the cardinality of a set $X$ and $A\Delta B$ is for the symmetric difference, defined for sets A, B as
 $A\,\Delta\,B = (A \setminus B) \cup (B \setminus A)$.
 
 where $|X|$ is the cardinality of a set $X$ and $A\Delta B$ is for the symmetric difference, defined for sets A, B as
 $A\,\Delta\,B = (A \setminus B) \cup (B \setminus A)$.
 


@@ -740,12 +763,14 @@ G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are the same ($G_{f}$ is a shift of strategies)
 the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $%
 10^{-(k+1)}\leqslant \varepsilon $.\bigskip \newline
 In conclusion,
 the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $%
 10^{-(k+1)}\leqslant \varepsilon $.\bigskip \newline
 In conclusion,

-$$
+%%RAPH : ici j'ai rajouté une ligne
+\begin{flushleft}$$

 \forall \varepsilon >0,\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N}%
 \forall \varepsilon >0,\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N}%

-,\forall n\geqslant N_{0},
- d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right)
+,\forall n\geqslant N_{0},$$
+$$ d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right)

 \leqslant \varepsilon .
 $$
 \leqslant \varepsilon .
 $$

+\end{flushleft}

 $G_{f}$ is consequently continuous.
 \end{proof}
 
 $G_{f}$ is consequently continuous.
 \end{proof}
 


@@ -785,7 +810,11 @@ 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}
 

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

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

+>>>>>>> e55d237aba022a66cc2d7650d295b29169878f45

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


@@ -803,8 +832,10 @@ and $t_2\in\mathds{N}$ such
 that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$.
 
 Consider the strategy $\tilde S$ that alternates the first $t_1$ terms
 that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$.
 
 Consider the strategy $\tilde S$ that alternates the first $t_1$ terms

-of $S$ and the first $t_2$ terms of $S'$: $$\tilde
-S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It
+of $S$ and the first $t_2$ terms of $S'$: 
+%%RAPH : j'ai coupé la ligne en 2
+$$\tilde
+S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,$$$$\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It

 is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after
 $t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic
 point. Since $\tilde S_t=S_t$ for $t<t_1$, by the choice of $t_1$, we
 is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after
 $t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic
 point. Since $\tilde S_t=S_t$ for $t<t_1$, by the choice of $t_1$, we


@@ -827,38 +858,41 @@ Topological properties of disorder exhibited by chaotic
 iterations can be inherited by the inputted generator, we hope by doing so to 
 obtain some statistical improvements while preserving speed.
 
 iterations can be inherited by the inputted generator, we hope by doing so to 
 obtain some statistical improvements while preserving speed.
 

-
-Let us give an example using 16-bits numbers, to clearly understand how the bitwise xor operations
-are
-done.  
-Suppose  that $x$ and the  strategy $S^i$ are given as
-binary vectors.
-Table~\ref{TableExemple} shows the result of $x \oplus S^i$.
-
-\begin{table}
-$$
-\begin{array}{|cc|cccccccccccccccc|}
-\hline
-x      &=&1&0&1&1&1&0&1&0&1&0&0&1&0&0&1&0\\
-\hline
-S^i      &=&0&1&1&0&0&1&1&0&1&1&1&0&0&1&1&1\\
-\hline
-x \oplus S^i&=&1&1&0&1&1&1&0&0&0&1&1&1&0&1&0&1\\
-\hline
-
-\hline
- \end{array}
-$$
-\caption{Example of an arbitrary round of the proposed generator}
-\label{TableExemple}
-\end{table}
-
-
-
-
-\lstset{language=C,caption={C code of the sequential PRNG based on chaotic iteration\
-s},label=algo:seqCIPRNG}
+%%RAPH : j'ai viré tout ca
+%% Let us give an example using 16-bits numbers, to clearly understand how the bitwise xor operations
+%% are
+%% done.  
+%% Suppose  that $x$ and the  strategy $S^i$ are given as
+%% binary vectors.
+%% Table~\ref{TableExemple} shows the result of $x \oplus S^i$.
+
+%% \begin{table}
+%% \begin{scriptsize}
+%% $$
+%% \begin{array}{|cc|cccccccccccccccc|}
+%% \hline
+%% x      &=&1&0&1&1&1&0&1&0&1&0&0&1&0&0&1&0\\
+%% \hline
+%% S^i      &=&0&1&1&0&0&1&1&0&1&1&1&0&0&1&1&1\\
+%% \hline
+%% x \oplus S^i&=&1&1&0&1&1&1&0&0&0&1&1&1&0&1&0&1\\
+%% \hline
+
+%% \hline
+%%  \end{array}
+%% $$
+%% \end{scriptsize}
+%% \caption{Example of an arbitrary round of the proposed generator}
+%% \label{TableExemple}
+%% \end{table}
+
+
+
+
+\lstset{language=C,caption={C code of the sequential PRNG based on chaotic iterations},label=algo:seqCIPRNG}
+\begin{small}

 \begin{lstlisting}
 \begin{lstlisting}

+

 unsigned int CIPRNG() {
   static unsigned int x = 123123123;
   unsigned long t1 = xorshift();
 unsigned int CIPRNG() {
   static unsigned int x = 123123123;
   unsigned long t1 = xorshift();


@@ -873,7 +907,7 @@ unsigned int CIPRNG() {
   return x;
 }
 \end{lstlisting}
   return x;
 }
 \end{lstlisting}

-
+\end{small}

 
 
 
 
 
 


@@ -929,8 +963,9 @@ number  $x$  that saves  the  last  generated  pseudorandom number. Additionally
 implementation of the  xor128, the xorshift, and the  xorwow respectively require
 4, 5, and 6 unsigned long as internal variables.
 
 implementation of the  xor128, the xorshift, and the  xorwow respectively require
 4, 5, and 6 unsigned long as internal variables.
 

-\begin{algorithm}

 
 

+\begin{algorithm}
+\begin{small}

 \KwIn{InternalVarXorLikeArray: array with internal variables of the 3 xor-like
 PRNGs in global memory\;
 NumThreads: number of threads\;}
 \KwIn{InternalVarXorLikeArray: array with internal variables of the 3 xor-like
 PRNGs in global memory\;
 NumThreads: number of threads\;}


@@ -943,11 +978,13 @@ NumThreads: number of threads\;}
   }
   store internal variables in InternalVarXorLikeArray[threadIdx]\;
 }
   }
   store internal variables in InternalVarXorLikeArray[threadIdx]\;
 }

-
+\end{small}

 \caption{Main kernel of the GPU ``naive'' version of the PRNG based on chaotic iterations}
 \label{algo:gpu_kernel}
 \end{algorithm}
 
 \caption{Main kernel of the GPU ``naive'' version of the PRNG based on chaotic iterations}
 \label{algo:gpu_kernel}
 \end{algorithm}
 

+
+

 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 simultaneously,  the number  of random numbers  that a thread  can generate
 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 simultaneously,  the number  of random numbers  that a thread  can generate


@@ -994,7 +1031,7 @@ bits).
 This version  can also pass the whole {\it BigCrush} battery of tests.
 
 \begin{algorithm}
 This version  can also pass the whole {\it BigCrush} battery of tests.
 
 \begin{algorithm}

-
+\begin{small}

 \KwIn{InternalVarXorLikeArray: array with internal variables of 1 xor-like PRNGs
 in global memory\;
 NumThreads: Number of threads\;
 \KwIn{InternalVarXorLikeArray: array with internal variables of 1 xor-like PRNGs
 in global memory\;
 NumThreads: Number of threads\;


@@ -1016,7 +1053,7 @@ array\_comb1, array\_comb2: Arrays containing combinations of size combination\_
   }
   store internal variables in InternalVarXorLikeArray[threadId]\;
 }
   }
   store internal variables in InternalVarXorLikeArray[threadId]\;
 }

-
+\end{small}

 \caption{Main kernel for the chaotic iterations based PRNG GPU efficient
 version\label{IR}}
 \label{algo:gpu_kernel2} 
 \caption{Main kernel for the chaotic iterations based PRNG GPU efficient
 version\label{IR}}
 \label{algo:gpu_kernel2} 


@@ -1081,7 +1118,7 @@ As a  comparison,   Listing~\ref{algo:seqCIPRNG}  leads   to the  generation of
 
 \begin{figure}[htbp]
 \begin{center}
 
 \begin{figure}[htbp]
 \begin{center}

-  \includegraphics[scale=.7]{curve_time_xorlike_gpu.pdf}
+  \includegraphics[width=\columnwidth]{curve_time_xorlike_gpu.pdf}

 \end{center}
 \caption{Quantity of pseudorandom numbers generated per second with the xorlike-based PRNG}
 \label{fig:time_xorlike_gpu}
 \end{center}
 \caption{Quantity of pseudorandom numbers generated per second with the xorlike-based PRNG}
 \label{fig:time_xorlike_gpu}


@@ -1100,7 +1137,7 @@ reduction.
 
 \begin{figure}[htbp]
 \begin{center}
 
 \begin{figure}[htbp]
 \begin{center}

-  \includegraphics[scale=.7]{curve_time_bbs_gpu.pdf}
+  \includegraphics[width=\columnwidth]{curve_time_bbs_gpu.pdf}

 \end{center}
 \caption{Quantity of pseudorandom numbers generated per second using the BBS-based PRNG}
 \label{fig:time_bbs_gpu}
 \end{center}
 \caption{Quantity of pseudorandom numbers generated per second using the BBS-based PRNG}
 \label{fig:time_bbs_gpu}


@@ -1128,17 +1165,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}
 


@@ -1147,7 +1184,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,


@@ -1202,8 +1239,10 @@ $y\bigoplus_{i=1}^{i=j} w_i^\prime=y\bigoplus_{i=1}^{i=j} w_i$. It follows,
 by a direct induction, that $w_i=w_i^\prime$. Furthermore, since $\mathbb{B}^{kN}$
 is finite, each $\varphi_y$ is bijective. Therefore, and using (\ref{PCH-1}),
 one has
 by a direct induction, that $w_i=w_i^\prime$. Furthermore, since $\mathbb{B}^{kN}$
 is finite, each $\varphi_y$ is bijective. Therefore, and using (\ref{PCH-1}),
 one has

+$\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(\varphi_y(U_{kN}))=1]$ and,
+therefore, 

 \begin{equation}\label{PCH-2}
 \begin{equation}\label{PCH-2}

-\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(\varphi_y(U_{kN}))=1]=\mathrm{Pr}[D(U_{kN})=1].
+\mathrm{Pr}[D^\prime(U_{kN})=1]=\mathrm{Pr}[D(U_{kN})=1].

 \end{equation}
 
 Now, using (\ref{PCH-1}) again, one has  for every $x$,
 \end{equation}
 
 Now, using (\ref{PCH-1}) again, one has  for every $x$,


@@ -1212,7 +1251,7 @@ D^\prime(H(x))=D(\varphi_y(H(x))),
 \end{equation}
 where $y$ is randomly generated. By construction, $\varphi_y(H(x))=X(yx)$,
 thus
 \end{equation}
 where $y$ is randomly generated. By construction, $\varphi_y(H(x))=X(yx)$,
 thus

-\begin{equation}\label{PCH-3}
+\begin{equation}%\label{PCH-3}      %%RAPH : j'ai viré ce label qui existe déjà, il est 3 ligne avant

 D^\prime(H(x))=D(yx),
 \end{equation}
 where $y$ is randomly generated. 
 D^\prime(H(x))=D(yx),
 \end{equation}
 where $y$ is randomly generated. 


@@ -1290,7 +1329,7 @@ variable for BBS number 8 is stored in place 1.
 \end{itemize}
 
 \begin{algorithm}
 \end{itemize}
 
 \begin{algorithm}

-
+\begin{small}

 \KwIn{InternalVarBBSArray: array with internal variables of the 8 BBS
 in global memory\;
 NumThreads: Number of threads\;
 \KwIn{InternalVarBBSArray: array with internal variables of the 8 BBS
 in global memory\;
 NumThreads: Number of threads\;


@@ -1326,7 +1365,7 @@ array\_shift[4]=\{0,1,3,7\}\;
   }
   store internal variables in InternalVarXorLikeArray[threadId] using a rotation\;
 }
   }
   store internal variables in InternalVarXorLikeArray[threadId] using a rotation\;
 }

-
+\end{small}

 \caption{main kernel for the BBS based PRNG GPU}
 \label{algo:bbs_gpu}
 \end{algorithm}
 \caption{main kernel for the BBS based PRNG GPU}
 \label{algo:bbs_gpu}
 \end{algorithm}


@@ -1414,9 +1453,11 @@ Alice will pick randomly $S^0$ in $\llbracket 0, 2^{\mathsf{N}-1}\rrbracket$ too
 her new public key will be $(S^0, N)$.
 
 To encrypt his message, Bob will compute
 her new public key will be $(S^0, N)$.
 
 To encrypt his message, Bob will compute

-\begin{equation}
-c = \left(m_0 \oplus (b_0 \oplus S^0), m_1 \oplus (b_0 \oplus b_1 \oplus S^0), \hdots, m_{L-1} \oplus (b_0 \oplus b_1 \hdots \oplus b_{L-1} \oplus S^0) \right)
-\end{equation}
+%%RAPH : ici, j'ai mis un simple $
+%\begin{equation}
+$c = \left(m_0 \oplus (b_0 \oplus S^0), m_1 \oplus (b_0 \oplus b_1 \oplus S^0), \hdots, \right.$
+$ \left. m_{L-1} \oplus (b_0 \oplus b_1 \hdots \oplus b_{L-1} \oplus S^0) \right)$
+%%\end{equation}

 instead of $\left(m_0 \oplus b_0, m_1 \oplus b_1, \hdots, m_{L-1} \oplus b_{L-1} \right)$. 
 
 The same decryption stage as in Blum-Goldwasser leads to the sequence 
 instead of $\left(m_0 \oplus b_0, m_1 \oplus b_1, \hdots, m_{L-1} \oplus b_{L-1} \right)$. 
 
 The same decryption stage as in Blum-Goldwasser leads to the sequence