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.