stoping

[rairo15.git] / intro.tex

diff --git a/intro.tex b/intro.tex
index f4ed222b2987afd4bf3b30cbfb51e0bd5d82198a..569c493a000df8ddd51dabd0513a99206741b6b2 100644 (file)
--- a/intro.tex
+++ b/intro.tex
@@ -4,20 +4,20 @@ chosen due to their unpredictable character and their sensitiveness to initial c
 In most cases, these generators simply consist in iterating a chaotic function like 
 the logistic map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots
 It thus remains to find optimal parameters in such functions so that attractors are
 In most cases, these generators simply consist in iterating a chaotic function like 
 the logistic map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots
 It thus remains to find optimal parameters in such functions so that attractors are

-avoided, guaranteeing by doing so that generated numbers follow a uniform distribution.
+avoided, hoping by doing so that the generated numbers follow a uniform distribution.

 In order to check the quality of the produced outputs, it is usual to test the 
 PRNGs   (Pseudo-Random  Number   Generators) with statistical batteries like
 In order to check the quality of the produced outputs, it is usual to test the 
 PRNGs   (Pseudo-Random  Number   Generators) with statistical batteries like

-the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite{LEcuyerS07}.
+the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite{LEcuyerS07} ones.

 
 

-In its general understanding, the chaos notion is often reduced to the strong
+In its general understanding, chaos notion is often reduced to the strong

 sensitiveness to the initial conditions (the well known ``butterfly effect''):
 a continuous function $k$ defined on a metrical space is said 
 sensitiveness to the initial conditions (the well known ``butterfly effect''):
 a continuous function $k$ defined on a metrical space is said 

-\emph{strongly sensitive to the initial conditions} if for all point 
-$x$ and all positive value $\epsilon$, it is possible to find another 
-point $y$, as close as possible to $x$, and an integer $t$ such that the distance
+\emph{strongly sensitive to the initial conditions} if for each point 
+$x$ and each positive value $\epsilon$, it is possible to find another 
+point $y$ as close as possible to $x$, and an integer $t$ such that the distance

 between the $t$-th iterates of $x$ and $y$, denoted by $k^t(x)$ and $k^t(y)$,
 are larger than $\epsilon$. However, in his definition of chaos, Devaney~\cite{Devaney} 
 between the $t$-th iterates of $x$ and $y$, denoted by $k^t(x)$ and $k^t(y)$,
 are larger than $\epsilon$. However, in his definition of chaos, Devaney~\cite{Devaney} 

-impose to the chaotic function two other properties called
+imposes to the chaotic function two other properties called

 \emph{transitivity} and \emph{regularity}. Functions evoked above have
 been studied according to these properties, and they have been proven as chaotic on $\R$.
 But nothing guarantees that such properties are preserved when iterating the functions
 \emph{transitivity} and \emph{regularity}. Functions evoked above have
 been studied according to these properties, and they have been proven as chaotic on $\R$.
 But nothing guarantees that such properties are preserved when iterating the functions


@@ -38,7 +38,7 @@ asynchronous iterations are strongly connected. We then have proven that it is n
 and sufficient that the Markov matrix associated to this graph is doubly stochastic,
 in order to have a uniform distribution of the outputs. We have finally established 
 sufficient conditions to guarantee the first property of connectivity. Among the 
 and sufficient that the Markov matrix associated to this graph is doubly stochastic,
 in order to have a uniform distribution of the outputs. We have finally established 
 sufficient conditions to guarantee the first property of connectivity. Among the 

-generated functions, we thus considered for further investigations only the one that
+generated functions, we thus have considered for further investigations only the one that

 satisfy the second property too. In~\cite{chgw14oip}, we have proposed an algorithmic 
 method allowing to directly obtain a strongly connected iteration graph having a doubly
 stochastic Markov matrix. The research work presented here generalizes this latter article
 satisfy the second property too. In~\cite{chgw14oip}, we have proposed an algorithmic 
 method allowing to directly obtain a strongly connected iteration graph having a doubly
 stochastic Markov matrix. The research work presented here generalizes this latter article


@@ -215,6 +215,16 @@ theoretical properties but with a reduced mixing time.
 % sur une batterie de tests.
 
 
 % sur une batterie de tests.
 
 

+The remainder of this article is organized as follows. The next section is devoted to 
+preliminaries, basic notations, and terminologies regarding asynchronous iterations.
+Then, in Section~\ref{sec:proofOfChaos}, Devaney's definition of chaos is recalled
+while the proofs of chaos of our most general PRNGs is provided. Section~\ref{sec:SCCfunc} shows how to generate functions and a number of iterations such that the iteration graph is strongly connected, making the
+PRNG chaotic. The next section focuses on examples of such graphs obtained by modifying the 
+hypercube, while Section~\ref{sec:prng} establishes the link between the theoretical study and
+pseudorandom number generation. 
+This research work ends by a conclusion section, where the contribution is summarized and
+intended future work is outlined.
+

 % Le reste de ce document est organisé comme suit. 
 % La section~\ref{section:chaos} présente ce qu'est un système dynamique discret booléen itérant une fonction $f$.
 % La chaoticité de la fonction engendrée $G_f$ est caractérisée en 
 % Le reste de ce document est organisé comme suit. 
 % La section~\ref{section:chaos} présente ce qu'est un système dynamique discret booléen itérant une fonction $f$.
 % La chaoticité de la fonction engendrée $G_f$ est caractérisée en