]> AND Private Git Repository - review_prng.git/commitdiff
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
fdlsihf
authorguyeux <guyeux@gmail.com>
Fri, 1 Jun 2012 11:28:08 +0000 (13:28 +0200)
committerguyeux <guyeux@gmail.com>
Fri, 1 Jun 2012 11:28:08 +0000 (13:28 +0200)
review_prng.tex

index 158f90bc4a2bde6c225bab432ee921f0f3feffc2..1ddc487ed270a04fff935bfacf15d8dab75f8893 100644 (file)
@@ -80,7 +80,7 @@ these units have not the same processing frequency.
 \end{itemize} 
 
 These considerations lead to the following definition of an iterative
 \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
 
 \begin{definition}
 Iterative systems on a set $\mathcal{X}$ are defined by
@@ -98,23 +98,28 @@ 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.
 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 compiliant with the definition above, 
-
-On appelle \emph{itérations parallèles} \index{itérations!parallèles} de $f$ sur 
-$\mathcal{X}$ toute itération synchrone $\Sigma = (\mathcal{X}, \mathcal{F})$ 
-telle que la suite $\mathcal{F}$ est constante égale à $f: \X \to \X$.
-On parle encore d'itérations parallèles $\left(\mathcal{X},f\right)$.
+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,
 
 
 
 Finally, iterative systems in chaotic mode, simply called chaotic iterations,
- are defined as follows.
+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}$. 
  
 
 \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} are defined by:
+\emph{Chaotic iterations} $(f, (x^0, S))$ are defined by:
 $$\left\{
 \begin{array}{l}
 x^0 \in \mathds{B}^\mathsf{N} \\
 $$\left\{
 \begin{array}{l}
 x^0 \in \mathds{B}^\mathsf{N} \\
@@ -133,87 +138,79 @@ 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.
 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 questionning has led to a first necessary condition of non convergence.
+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}
 
 \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,
-\item or $S$ is not pseudo-periodic.
+\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}
 
 \end{itemize}
 \end{proposition}
 
-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 rewriten as simple discrete dynamical systems, as follows.
-
-
-
-
-
-
-%\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}
-%}
-
-
-
+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.
 
 
-%\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.