pch

diff --git a/mabase.bib b/mabase.bib
index 6699bd31599bdb633642a479bab221ac4d92b4a5..fe714bdd975a1d9b49b0dd9786069284edd7b868 100644 (file)
--- a/mabase.bib
+++ b/mabase.bib
@@ -112,6 +112,14 @@
   timestamp = {2009.06.29}
 }
 
   timestamp = {2009.06.29}
 }
 

+@Book{Goldreich,
+  author =      {Oded Goldreich},
+  ALTeditor =      {},
+  title =      {Foundations of Cryptography: Basic Tools},
+  publisher =      {Cambridge University Press},
+  year =      {2007},
+}
+

 @INPROCEEDINGS{DBLP:conf/cec/HiggsSHS10,
   author = {Trent Higgs and Bela Stantic and Tamjidul Hoque and Abdul Sattar},
   title = {Genetic algorithm feature-based resampling for protein structure
 @INPROCEEDINGS{DBLP:conf/cec/HiggsSHS10,
   author = {Trent Higgs and Bela Stantic and Tamjidul Hoque and Abdul Sattar},
   title = {Genetic algorithm feature-based resampling for protein structure

diff --git a/prng_gpu.tex b/prng_gpu.tex
index de8f46488c1cd1b4843a1f759bbea5433f41cb71..0a88df58f8b1204d8d1f118090fd03f9bcdb229c 100644 (file)
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -216,7 +216,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 +232,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 +251,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 +259,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


@@ -786,7 +789,7 @@ 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}
 

-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.
 
 \begin{proof}[Theorem~\ref{t:chaos des general}]
 Firstly, strong transitivity implies transitivity.


@@ -1129,17 +1132,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 $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
 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}
 


@@ -1148,7 +1151,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,