X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/review_prng.git/blobdiff_plain/bba3979e3f3ee00ce44b16d13b4e61e434310b61..af5ccdc8b87c569ce32f355e5c631e0c2c0574ed:/review_prng.tex

diff --git a/review_prng.tex b/review_prng.tex
index a5d1388..1ddc487 100644
--- a/review_prng.tex
+++ b/review_prng.tex
@@ -3,7 +3,7 @@
 \usepackage[standard]{ntheorem}
 \usepackage[english]{babel}
 
-
+\usepackage{stmaryrd}
 \usepackage{amsmath}
 \usepackage{color}
 \usepackage{dsfont}
@@ -80,7 +80,7 @@ these units have not the same processing frequency.
 \end{itemize} 
 
 These considerations lead to the following definition of an iterative
-system.
+system~\cite{GuyeuxThese10}.
 
 \begin{definition}
 Iterative systems on a set $\mathcal{X}$ are defined by
@@ -93,136 +93,124 @@ $$\left\{
 where $f^n:\mathcal{X}^{n+1}\rightarrow \mathcal{X}$.
 \end{definition}
 
+Some particular cases of these iterative systems are well documented,
+namely the serial, parallel, or chaotic modes.
+In the serial mode, each component is updated one by one, whereas the
+parallel mode consists in updating all the components at each iteration,
+leading to an usual discrete dynamical system.
+These modes are compliant with the definition above, 
+as the parallel mode consists in considering that the sequence
+$f^n$ defined above is constant equal to a given $f: \mathcal{X} 
+\longrightarrow \mathcal{X}$,
+whereas the serial mode can be rewritten as parallel iterations of
+$$ G=F_\mathsf{N} \circ \ldots \circ F_2 \circ F_1 $$
+where, $\forall i \in \llbracket 1, \mathsf{N} \rrbracket $:
+$$\begin{array}{rccc}
+F_i: & \mathcal{X} & \longrightarrow & \mathcal{X}\\
+        & (x_1, \hdots, x_\mathsf{N}) & \longmapsto & \left(x_1, \hdots, x_{i-1},f_i\left(x_1, \hdots, x_\mathsf{N}\right), x_{i+1}, \hdots, x_\mathsf{N}\right).
+\end{array}$$
+
+
+
+Finally, iterative systems in chaotic mode, simply called chaotic iterations,
+are defined as follows~\cite{Robert}.
+ 
 
+\begin{definition}
+Let $f: \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$ and 
+$S \subset \mathcal{P} \left(\llbracket1,\mathsf{N}\rrbracket\right)^\mathds{N}$. 
+\emph{Chaotic iterations} $(f, (x^0, S))$ are defined by:
+$$\left\{
+\begin{array}{l}
+x^0 \in \mathds{B}^\mathsf{N} \\
+\forall n \in \mathds{N}^*, \forall i \in \llbracket 1; \mathsf{N} \rrbracket,  x^{n}_i = \left\{
+\begin{array}{ll}
+x^{n-1}_{i} & \textrm{ if } i \notin S^n\\
+f(x^{n-1})_{i} & \textrm{ if } i \in S^n
+\end{array}
+\right.
+\end{array}
+\right.$$
+\end{definition}
 
+\emph{A priori}, there is no relation between these chaotic iterations
+and the mathematical theory of chaos recalled in the previous section.
+On our side, we have regarded whether these chaotic iterations can 
+behave chaotically, as it is defined for instance by Devaney, and if so, 
+in which applicative context this behavior can be profitable.
+This questioning has led to a first necessary condition of non convergence~\cite{GuyeuxThese10}.
+
+\begin{proposition}
+Let $f : \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$ and 
+$S \in \llbracket 1, \mathsf{N} \rrbracket^{\mathds{N}}$. 
+If the chaotic iterations $\left(f,(x^0,S)\right)$ are not convergent, then:
+\begin{itemize}
+\item either $f$ is not a contraction, meaning that there is no Boolean matrix
+    $M$ of size $\mathsf{N}$ satisfying $\forall x,y\in \mathds{B}^\mathsf{N}$,
+    $d(f(x),f(y)) \leqslant M d(x,y)$, where $d$ is here the ``vectorial distance''
+    defined by $d(x,y) = \left(\begin{array}{c} \delta(x_1,y_1)\\ \vdots \\ \delta(x_\mathsf{N}, 
+    y_\mathsf{N}) \end{array}\right)$, with $\delta$ the discrete metric defined by $\delta(x,y) = \left\{\begin{matrix} 1 &\mbox{if}\ x\neq y , \\ 0 &\mbox{if}\ x = y \end{matrix}\right.$, and $\leqslant$ is the inequality term by term~\cite{Robert}.
+\item or $S$ is not pseudo-periodic: it is not constituted by an infinite succession of finite sequences, each having any element of $\llbracket
+    1, \mathsf{N} \rrbracket$ at least once.
+\end{itemize}
+\end{proposition}
+
+The second alternative of the proposition above concerns the strategy,
+which should be provided by the outside world. Indeed, in our opinion, 
+chaotic iterations can receive a PRNG $S$ as input, and due to 
+properties of disorder of $f$, generate a new pseudorandom sequence
+that presents better statistical properties than $S$. Having this 
+approach in mind, we thus have searched vectorial Boolean iteration
+functions that are not contractions. The vectorial negation function
+$f_0:\mathds{B}^\mathsf{N} \longrightarrow \mathds{N}^\mathsf{N},$
+$(x_1, \hdots, x_\mathsf{N}) \longmapsto (\overline{x_1}, \hdots, 
+\overline{x_\mathsf{N}}) $ is such a function, which served has a
+model in our further studies ($\overline{x}$ stands for the negation
+of the Boolean $x$).
+
+The quantity of disorder generated by such chaotic iterations, when
+satisfying the proposition above, has then been measured. To do so, 
+chaotic iterations have first been rewritten as simple discrete 
+dynamical systems, as follows.
+
+
+\subsection{Chaotic Iterations as Dynamical Systems}
+
+The problems raised by such a formalization can be summarized as 
+follows. 
+Chaotic iterations are defined in the discrete mathematics framework,
+considering $x^0 \in \mathds{B}^\mathds{N}$ and $S \in \mathcal{S} = \llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$, and iterations having the
+form 
+$$x_i^{n+1} = \left\{ \begin{array}{ll} x^{n}_{i} & \textrm{ si } i \neq S^n\\ f(x^{n})_{i} & \textrm{ si } i = S^n \end{array} \right.$$ 
+where $f: \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$.
+However, the mathematical theory of chaos takes place into a 
+topological space $(\mathcal{X},\tau)$. It studies the iterations
+$x^0 \in \mathcal{X}$, $\forall n \in \mathds{N}, x^{n+1} = f(x^n)$,
+where $f : \mathcal{X} \to \mathcal{X}$ is continuous for the
+topology $\tau$.
+
+To realize the junction between these two frameworks, the following
+material has been introduced~\cite{GuyeuxThese10,bgw09:ip}:
+\begin{itemize}
+\item the shift function: $\sigma : \mathcal{S} \longrightarrow \mathcal{S}, (S^n)_{n \in \mathds{N}} \mapsto (S^{n+1})_{n \in \mathds{N}}$.
+\item the initial function, defined by $i : \mathcal{S} \longrightarrow \llbracket 1 ; \mathsf{N} \rrbracket, (S^n)_{n \in \mathds{N}} \mapsto S^0$
+\item and $F_f : \llbracket 1 ; \mathsf{N} \rrbracket \times \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N},$ $$(k,E) \longmapsto  \left( E_j.\delta(k,j) + f(E)_k.\overline{\delta (k,j)} \right)_{j \in \llbracket 1 ; \mathsf{N} \rrbracket}$$
+\end{itemize}
+where $\delta$ is the discrete metric.
 
 
-%%  \end{block}
-%%\uncover<2->{
-%%DiffÃ©rents modes d'itÃ©rations: sÃ©ries, parallÃ¨les, chaotiques, asynchrones...
-%%}
-%%}
-
-
-
-
-
-
-
-
-
-
-%\subsection*{Cas des ItÃ©rations chaotiques}
-%\frame{
-%  \frametitle{Les Â« itÃ©rations chaotiques Â»}
-%    \begin{block}{DÃ©finition (ItÃ©rations chaotiques)}
-% Soient $f: \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$ et $S \subset \mathcal{P} \left(\llbracket1,\mathsf{N}\rrbracket\right)^\mathds{N}$. Les \emph{itÃ©rations chaotiques} sont:
-%$$\left\{
-%\begin{array}{l}
-%x^0 \in \mathds{B}^\mathsf{N} \\
-%\forall n \in \mathds{N}^*, \forall i \in \llbracket 1; \mathsf{N} \rrbracket,  x^{n}_i = \left\{
-%\begin{array}{ll}
-%x^{n-1}_{i} & \textrm{ si } i \notin S^n\\
-%f(x^{n-1})_{i} & \textrm{ si } i \in S^n
-%\end{array}
-%\right.
-%\end{array}
-%\right.$$
-%\end{block}
-%%\uncover<2->{
-%%ItÃ©rations chaotiques et thÃ©orie du chaos: a priori, rien Ã  voir.
-%%}
-%%\uncover<3->{Y a-t-il un lien ?}\uncover<4->{ Pour quoi faire ?}
-%}
-
-
-
-
-
-%\frame{
-%  \frametitle{Non-convergence des IC}
-%   \begin{alertblock}{ThÃ©orÃ¨me (Condition nÃ©cessaire de non-convergence)}
-%    % Soit $f : \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$ et $S \in \mathcal{S}$. 
-%    Si les itÃ©rations chaotiques $\left(f,(x^0,S)\right)$ sont non convergentes, alors:
-%\begin{itemize}
-%\item soit $f$ n'est pas contractante,
-%\item soit $S$ n'est pas pseudo-pÃ©riodique (complÃ¨te).
-%\end{itemize}
-%   \end{alertblock}
-%   \uncover<2->{
-%   Quelle quantitÃ© de dÃ©sordre ?
-%   }
-%}
-
-
-
-
-
-
-
-
-
-
-%\frame{
-%\frametitle{PrÃ©sentation du problÃ¨me}
-
-%\begin{tabular}{c||c}
-%MATHS DISCRÃTES & TOPOLOGIE MATHÃMATIQUE \tabularnewline
-%\hline
-%\multirow{2}{5cm}{\centering $f: \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$} & $(\mathcal{X},\tau)$ espace topologique\\
-%& $f : \mathcal{X} \to \mathcal{X}$ continue pour $\tau$\\
-%\hline
-%$S \in \mathcal{S} = \llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$ & \multirow{2}{5cm}{\centering $x^0 \in \mathcal{X}$} \\
-%$x^0 \in \mathds{B}^\mathds{N}$ & \\ 
-%\hline
-%$x_i^{n+1} = \left\{ \begin{array}{ll} x^{n}_{i} & \textrm{ si } i \neq S^n\\ f(x^{n})_{i} & \textrm{ si } i = S^n \end{array} \right.$ & $\forall n \in \mathds{N}, x^{n+1} = f(x^n)$ \\ 
-%\end{tabular}
-
-%}
-
-
-
-
-
-
-%\frame{
-%\frametitle{DÃ©finitions et notations}
-%\begin{block}{Introduisons quelques fonctions...}
-%\begin{itemize}
-%\item dÃ©calage: $\sigma : \mathcal{S} \longrightarrow \mathcal{S}, (S^n)_{n \in \mathds{N}} \mapsto (S^{n+1})_{n \in \mathds{N}}$.
-%\item initiale: $i : \mathcal{S} \longrightarrow \llbracket 1 ; \mathsf{N} \rrbracket, (S^n)_{n \in \mathds{N}} \mapsto S^0$
-%\item $F_f : \llbracket 1 ; \mathsf{N} \rrbracket \times \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N},$ $$(k,E) \longmapsto  \left( E_j.\delta(k,j) + f(E)_k.\overline{\delta (k,j)} \right)_{j \in \llbracket 1 ; \mathsf{N} \rrbracket}$$
-%\end{itemize}
-%oÃ¹ $\delta(x,y) = \left\{\begin{array}{ll}
-%0 & \textrm{ si } x=y, \\
-%1 & \textrm{ sinon.}
-% \end{array}\right.
-%$
-%\end{block}
-%}
-
-
-
-
-%\frame{
-%\frametitle{ModÃ©lisation des IC}
-%\begin{alertblock}{ModÃ©lisation des IC en topologie}
-%Soit $\mathcal{X} = \llbracket 1 ; \mathsf{N} \rrbracket^\mathds{N} \times \mathds{B}^\mathsf{N},$ et $G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right).$ 
-
 
-%On modÃ©lise les itÃ©rations chaotiques $\left(f, (S,x^0)\right)$ par le systÃ¨me dynamique discret:
-%$$\left\{
-%\begin{array}{l}
-%X^0 = (S,x^0) \in \mathcal{X}, \\
-%\forall k \in \mathds{N}, X^{k+1} = G_f(X^k).
-%\end{array}
-%\right.$$
-%\end{alertblock}
 
-% \uncover<2>{
-% On peut donc Ã©tudier leur dÃ©sordre topologique.
-% }
-%}
+Let $\mathcal{X} = \llbracket 1 ; \mathsf{N} \rrbracket^\mathds{N} \times \mathds{B}^\mathsf{N},$ and $G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right).$ 
+Chaotic iterations $\left(f, (S,x^0)\right)$ can be modeled by the 
+discrete dynamical system:
+$$\left\{
+\begin{array}{l}
+X^0 = (S,x^0) \in \mathcal{X}, \\
+\forall k \in \mathds{N}, X^{k+1} = G_f(X^k).
+\end{array}
+\right.$$
+Their topological disorder can then be studied.
 
 
 
