a pseudorandom number generator (PRNG)\index{PRNG}, or by a physical nondeterministic
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 MonteCarlo-based
+reproducible generators, useful for instance in Monte Carlo-based
simulators. These domains need PRNGs that are statistically
irreproachable. In some fields such as in numerical simulations,
speed is a strong requirement that is usually attained by using
parallel architectures. In that case, 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 adhoc PRNGs for each possible architecture must be found to
+is why ad hoc PRNGs for each possible architecture must be found to
achieve both speed and randomness. On the other hand, speed is not
the main requirement in cryptography: the most important point is to
define \emph{secure} generators able to withstand malicious
These generators are finally experimented in Section~\ref{sec:experiments}.
-\section{Basic remindees}
+\section{Basic reminders}
\label{section:BASIC RECALLS}
This section is devoted to basic definitions and terminologies in the fields of
Chaos theory studies the behavior of dynamical systems that are perfectly predictable, yet appear to be wildly amorphous and meaningless.
-Chaotic systems\index{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,
in general rendering long-term prediction impossible \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
-\subsection{Chaotic iterations}\index{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
-\lstset{language=C,caption={C code of the sequential PRNG based on chaotic iterations},label={algo:seqCIPRNG}}
-\begin{small}
-\begin{lstlisting}
-
-unsigned int CIPRNG() {
- static unsigned int x = 123123123;
- unsigned long t1 = xorshift();
- unsigned long t2 = xor128();
- unsigned long t3 = xorwow();
- x = x^(unsigned int)t1;
- x = x^(unsigned int)(t2>>32);
- x = x^(unsigned int)(t3>>32);
- x = x^(unsigned int)t2;
- x = x^(unsigned int)(t1>>32);
- x = x^(unsigned int)t3;
- return x;
-}
-\end{lstlisting}
-\end{small}
-
+\lstinputlisting[label=algo:seqCIPRNG,caption={C code of the sequential PRNG based on chaotic iterations}]{Chapters/chapter18/code2.cu}
In Listing~\ref{algo:seqCIPRNG} a sequential version of the proposed PRNG based
on chaotic iterations is presented, which extends the generator family
-formerly presented in~\cite{bgw09:ip,guyeux10}. The xor operator is represented by
+formerly presented in~\cite{bgw09:ip,guyeux10}. The \texttt{xor} operator is represented by
\textasciicircum. This function uses three classical 64-bit PRNGs, namely the
\texttt{xorshift}, the \texttt{xor128}, and the
\texttt{xorwow}~\cite{Marsaglia2003}. In the following, we call them ``xor-like
more local memory is used, and the less branching instructions are
used (if, while, etc.) and so, the better the performances on GPU are.
Obviously, having these requirements in mind, it is possible to build
-a program similar to the one presented in Listing
-\ref{algo:seqCIPRNG}, which computes pseudorandom numbers on GPU. To
+a program similar to the one presented in Listing~\ref{algo:seqCIPRNG}, which computes pseudorandom numbers on GPU. To
do so, we must first recall that in the CUDA~\cite{Nvid10}
environment, threads have a local identifier called
\texttt{ThreadIdx}, which is relative to the block containing
\If{threadIdx is concerned by the computation} {
retrieve data from InternalVarXorLikeArray[threadIdx] in local variables\;
\For{i=1 to n} {
- compute a new PRNG as in Listing\ref{algo:seqCIPRNG}\;
+ compute a new PRNG as in Listing~\ref{algo:seqCIPRNG}\;
store the new PRNG in NewNb[NumThreads*threadIdx+i]\;
}
store internal variables in InternalVarXorLikeArray[threadIdx]\;
store internal variables in InternalVarXorLikeArray[threadIdx]\;
}
\end{small}
-\caption{Main kernel for the chaotic iterations based PRNG GPU efficient
+\caption{main kernel for the chaotic iterations based PRNG GPU efficient
version\label{IR}}
\label{algo:gpu_kernel2}
\end{algorithm}
