pas mal de petites modifs

[book_gpu.git] / BookGPU / Chapters / chapter18 / ch18.tex

diff --git a/BookGPU/Chapters/chapter18/ch18.tex b/BookGPU/Chapters/chapter18/ch18.tex
index ed41c6ef8cd5155873c14ac025bf844153cd1082..9c9a85a4f057d9b63baca6308b6fa8145f399288 100755 (executable)
--- a/BookGPU/Chapters/chapter18/ch18.tex
+++ b/BookGPU/Chapters/chapter18/ch18.tex
@@ -10,7 +10,7 @@
 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
 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 
+a pseudorandom number generator (PRNG)\index{PRNG}, or by a physical non-deterministic 

 process having all the characteristics of a random noise, called a truly random number
 generator (TRNG). In this chapter, we focus on
 reproducible generators, useful for instance in Monte-Carlo based
 process having all the characteristics of a random noise, called a truly random number
 generator (TRNG). In this chapter, we focus on
 reproducible generators, useful for instance in Monte-Carlo based


@@ -64,7 +64,7 @@ Let us finish this introduction 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 in the well-known TestU01 package~\cite{LEcuyerS07}.
+This battery can be found in the well-known TestU01 package~\cite{LEcuyerS07}\index{TestU01}.

 More precisely, each time we performed a test on a PRNG, we ran it
 twice in order to observe if all $p-$values are inside [0.01, 0.99]. In
 fact, we observed that few $p-$values (less than ten) are sometimes
 More precisely, each time we performed a test on a PRNG, we ran it
 twice in order to observe if all $p-$values are inside [0.01, 0.99]. In
 fact, we observed that few $p-$values (less than ten) are sometimes


@@ -97,7 +97,7 @@ with basic notions on topology (see for instance~\cite{Devaney}).
 
 
 Chaos theory studies the behavior of dynamical systems that are perfectly predictable, yet appear to be wildly amorphous and without meaningful. 
 
 
 Chaos theory studies the behavior of dynamical systems that are perfectly predictable, yet appear to be wildly amorphous and without meaningful. 

-Chaotic systems are highly sensitive to initial conditions, 
+Chaotic systems\index{chaotic systems} are highly sensitive to initial conditions, 

 which is popularly referred to as the butterfly effect. 
 In other words, small differences in initial conditions (such as those due to rounding errors in numerical computation) yield widely diverging outcomes, 
 rendering long-term prediction impossible in general \cite{kellert1994wake}. This happens even though these systems are deterministic, meaning that their future behavior is fully determined by their initial conditions, with no random elements involved \cite{kellert1994wake}. That is, the deterministic nature of these systems does not make them predictable \cite{kellert1994wake,Werndl01032009}. This behavior is known as deterministic chaos, or simply chaos. It has been well-studied in mathematics and
 which is popularly referred to as the butterfly effect. 
 In other words, small differences in initial conditions (such as those due to rounding errors in numerical computation) yield widely diverging outcomes, 
 rendering long-term prediction impossible in general \cite{kellert1994wake}. This happens even though these systems are deterministic, meaning that their future behavior is fully determined by their initial conditions, with no random elements involved \cite{kellert1994wake}. That is, the deterministic nature of these systems does not make them predictable \cite{kellert1994wake,Werndl01032009}. This behavior is known as deterministic chaos, or simply chaos. It has been well-studied in mathematics and


@@ -108,7 +108,7 @@ recalled thereafter.
 
 
 
 
 
 

-\subsection{On Devaney's Definition of Chaos}
+\subsection{On Devaney's Definition of Chaos}\index{chaos}

 \label{sec:dev}
 Consider a metric space $(\mathcal{X},d)$ and a continuous function $f:\mathcal{X}\longrightarrow \mathcal{X}$, for one-dimensional dynamical systems of the form:
 \begin{equation}
 \label{sec:dev}
 Consider a metric space $(\mathcal{X},d)$ and a continuous function $f:\mathcal{X}\longrightarrow \mathcal{X}$, for one-dimensional dynamical systems of the form:
 \begin{equation}


@@ -120,14 +120,14 @@ the following definition of chaotic behavior, formulated by Devaney~\cite{Devane
 \begin{definition}
  A dynamical system of Form~(\ref{Devaney}) is said to be chaotic if the following conditions hold.
 \begin{itemize}
 \begin{definition}
  A dynamical system of Form~(\ref{Devaney}) is said to be chaotic if the following conditions hold.
 \begin{itemize}

-\item Topological transitivity:
+\item Topological transitivity\index{topological transitivity}:

 
 \begin{equation}
 \forall U,V \textrm{ open sets of } \mathcal{X},~\exists k>0, f^k(U) \cap V \neq \varnothing .
 \end{equation}
 
 Intuitively, a topologically transitive map has points that eventually move under iteration from one arbitrarily small neighborhood to any other. Consequently, the dynamical system cannot be decomposed into two disjoint open sets that are invariant under the map. Note that if a map possesses a dense orbit, then it is clearly topologically transitive.
 
 \begin{equation}
 \forall U,V \textrm{ open sets of } \mathcal{X},~\exists k>0, f^k(U) \cap V \neq \varnothing .
 \end{equation}
 
 Intuitively, a topologically transitive map has points that eventually move under iteration from one arbitrarily small neighborhood to any other. Consequently, the dynamical system cannot be decomposed into two disjoint open sets that are invariant under the map. Note that if a map possesses a dense orbit, then it is clearly topologically transitive.

-\item Density of periodic points in $\mathcal{X}$.
+\item Density of periodic points in $\mathcal{X}$\index{density of periodic points}.

 
 Let $P=\{p\in \mathcal{X}|\exists n \in \mathds{N}^{\ast}:f^n(p)=p\}$ the set of periodic points of $f$. Then $P$ is dense in $\mathcal{X}$:
 
 
 Let $P=\{p\in \mathcal{X}|\exists n \in \mathds{N}^{\ast}:f^n(p)=p\}$ the set of periodic points of $f$. Then $P$ is dense in $\mathcal{X}$:
 


@@ -136,7 +136,7 @@ Let $P=\{p\in \mathcal{X}|\exists n \in \mathds{N}^{\ast}:f^n(p)=p\}$ the set of
 \end{equation}
 
 Density of periodic orbits means that every point in the space is approached arbitrarily closely by periodic orbits. Topologically mixing systems failing this condition may not display sensitivity to initial conditions presented below, and hence may not be chaotic.
 \end{equation}
 
 Density of periodic orbits means that every point in the space is approached arbitrarily closely by periodic orbits. Topologically mixing systems failing this condition may not display sensitivity to initial conditions presented below, and hence may not be chaotic.

-\item Sensitive dependence on initial conditions:
+\item Sensitive dependence on initial conditions\index{sensitive dependence on initial conditions}:

 
 $\exists \varepsilon>0,$ $\forall x \in \mathcal{X},$ $\forall \delta >0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$ and $d\left(f^n(x),f^n(y)\right) \geqslant \varepsilon.$
 
 
 $\exists \varepsilon>0,$ $\forall x \in \mathcal{X},$ $\forall \delta >0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$ and $d\left(f^n(x),f^n(y)\right) \geqslant \varepsilon.$
 


@@ -154,7 +154,7 @@ When $f$ is chaotic, then the system $(\mathcal{X}, f)$ is chaotic and quoting D
 
 
 
 
 
 

-\subsection{Chaotic iterations}
+\subsection{Chaotic iterations}\index{chaotic iterations}

 \label{subsection:Chaotic iterations}
 
 Let us now introduce an example of a dynamical systems family that has
 \label{subsection:Chaotic iterations}
 
 Let us now introduce an example of a dynamical systems family that has


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

 
 

-\begin{figure}[htbp]
-\begin{center}
-  \includegraphics[scale=0.65]{Chapters/chapter18/figures/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{figure}
-
-All  these  experiments allow  us  to conclude  that  it  is possible  to
+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.
 generate a very large quantity of pseudorandom  numbers statistically perfect with the  xor-like version.

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