\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}$
\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}
\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}
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 $.
-$\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
claimed in the lemma.
\end{proof}
-We can now prove the Theorem~\ref{t:chaos des general}...
+We can now prove the Theorem~\ref{t:chaos des general}.
\begin{proof}[Theorem~\ref{t:chaos des general}]
Firstly, strong transitivity implies transitivity.
-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 necessary paid by a speed
-reduction.
+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 necessary paid by a speed
+reduction.
\begin{figure}[htbp]
\begin{center}
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 $m$ of length $m$, $G(m)$ (the output of $G$ on the input $m$) 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}
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 last four bits of the result of $BBS1$. Thus an operation of the form
$t<<=4; t|=BBS1(bbs1)\&15\;$ realizes in $t$ a left shift of 4 bits, and then
puts the 4 last bits of $BBS1(bbs1)$ in the four last positions of $t$. Let us
-remark that to initialize $t$ is not a necessity as we fill it 4 bits by 4 bits,
-until having obtained 32-bits. The two last new shifts are realized in order to
-enlarge the small periods of the BBS used here, to introduce a kind of
+remark that the initialization $t$ is not a necessity as we fill it 4 bits by 4
+bits, until having obtained 32-bits. The two last new shifts are realized in
+order to enlarge the small periods of the BBS used here, to introduce a kind of
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$.
+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
+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).
-It should be noticed that this generator has another time the form $x^{n+1} = x^n \oplus S^n$,
+It should be noticed that this generator has once more the form $x^{n+1} = x^n \oplus S^n$,
where $S^n$ is referred in this algorithm as $t$: each iteration of this
PRNG ends with $x = x \wedge t$. This $S^n$ is only constituted
by secure bits produced by the BBS generator, and thus, due to
Proposition~\ref{cryptopreuve}, the resulted PRNG is cryptographically
-secure
+secure.
