X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/17bd6f6df9a94a46128919486c226ae8b1124740..44232560a3cd3ab96e3c35d7e4445f5185fb52d3:/preliminaries.tex?ds=sidebyside diff --git a/preliminaries.tex b/preliminaries.tex index 628cd44..1200bc5 100644 --- a/preliminaries.tex +++ b/preliminaries.tex @@ -3,36 +3,49 @@ $\Bool=\{0,1\}$ with the classical operators of conjunction '.', of disjunction '+', of negation '$\overline{~}$', and of disjunctive union $\oplus$. -Let $n$ be a positive integer. A {\emph{Boolean map} $f$ is -a function from $\Bool^n$ +Let us first introduce basic notations. +Let $\mathsf{N}$ be a positive integer. The set $\{1, 2, \hdots , \mathsf{N}\}$ +of integers belonging between $1$ and $\mathsf{N}$ +is further denoted as $\llbracket 1, \mathsf{N} \rrbracket$. +A {\emph{Boolean map} $f$ is +a function from $\Bool^{\mathsf{N}}$ to itself such that -$x=(x_1,\dots,x_n)$ maps to $f(x)=(f_1(x),\dots,f_n(x))$. +$x=(x_1,\dots,x_{\mathsf{N}})$ maps to $f(x)=(f_1(x),\dots,f_{\mathsf{N}}(x))$. +In what follows, for any finite set $X$, $|X|$ denotes its cardinality and +$\lfloor y \rfloor$ is +the largest integer lower than $y$. + Functions are iterated as follows. At the $t^{th}$ iteration, only the $s_{t}-$th component is said to be -``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;n \rrbracket$ called ``strategy''. +``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;{\mathsf{N}} \rrbracket$ called ``strategy''. Formally, -let $F_f: \llbracket1;n\rrbracket\times \Bool^{n}$ to $\Bool^n$ be defined by +let $F_f: \Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket$ to $\Bool^{\mathsf{N}}$ be defined by \[ -F_f(i,x)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_n). +F_f(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_{\mathsf{N}}). \] -Then, let $x^0\in\Bool^n$ be an initial configuration +Then, let $x^0\in\Bool^{\mathsf{N}}$ be an initial configuration and $s\in -\llbracket1;n\rrbracket^\Nats$ be a strategy, +\llbracket1;{\mathsf{N}}\rrbracket^\Nats$ be a strategy, the dynamics are described by the recurrence \begin{equation}\label{eq:asyn} -x^{t+1}=F_f(s_t,x^t). +x^{t+1}=F_f(x^t,s_t). \end{equation} + + + Let be given a Boolean map $f$. Its associated {\emph{iteration graph}} $\Gamma(f)$ is the directed graph such that the set of vertices is -$\Bool^n$, and for all $x\in\Bool^n$ and $i\in \llbracket1;n\rrbracket$, -the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(i,x)$. +$\Bool^{\mathsf{N}}$, and for all $x\in\Bool^{\mathsf{N}}$ and $i\in \llbracket1;{\mathsf{N}}\rrbracket$, +the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(x,i)$. +Each arc $(x,F_f(x,i))$ is labelled with $i$. + \begin{xpl} -Let us consider for instance $n=3$. +Let us consider for instance ${\mathsf{N}}=3$. Let $f^*: \Bool^3 \rightarrow \Bool^3$ be defined by $f^*(x_1,x_2,x_3) = @@ -40,186 +53,49 @@ $f^*(x_1,x_2,x_3) = \overline{x_1}\overline{x_3} + x_1x_2)$. The iteration graph $\Gamma(f^*)$ of this function is given in Figure~\ref{fig:iteration:f*}. +\end{xpl} -\vspace{-1em} \begin{figure}[ht] \begin{center} \includegraphics[scale=0.5]{images/iter_f0c} \end{center} -\vspace{-0.5em} \caption{Iteration Graph $\Gamma(f^*)$ of the function $f^*$}\label{fig:iteration:f*} \end{figure} -\end{xpl} - - -Let thus be given such kind of map. -This article focusses on studying its iterations according to -the equation~(\ref{eq:asyn}) with a given strategy. -First of all, this can be interpreted as walking into its iteration graph -where the choice of the edge to follow is decided by the strategy. -Notice that the iteration graph is always a subgraph of -$n$-cube augemented with all the self-loop, \textit{i.e.}, all the -edges $(v,v)$ for any $v \in \Bool^n$. -Next, if we add probabilities on the transition graph, iterations can be -interpreted as Markov chains. -\begin{xpl} -Let us consider for instance -the graph $\Gamma(f)$ defined -in \textsc{Figure~\ref{fig:iteration:f*}.} and -the probability function $p$ defined on the set of edges as follows: -$$ -p(e) \left\{ -\begin{array}{ll} -= \frac{2}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\ -= \frac{1}{6} \textrm{ otherwise.} -\end{array} -\right. -$$ -The matrix $P$ of the Markov chain associated to the function $f^*$ and to its probability function $p$ is -\[ -P=\dfrac{1}{6} \left( -\begin{array}{llllllll} -4&1&1&0&0&0&0&0 \\ -1&4&0&0&0&1&0&0 \\ -0&0&4&1&0&0&1&0 \\ -0&1&1&4&0&0&0&0 \\ -1&0&0&0&4&0&1&0 \\ -0&0&0&0&1&4&0&1 \\ -0&0&0&0&1&0&4&1 \\ -0&0&0&1&0&1&0&4 -\end{array} -\right) -\] -\end{xpl} - - - -More generally, let $\pi$, $\mu$ be two distribution on $\Bool^n$. The total -variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is -defined by -$$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$ It is known that -$$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$ Moreover, if -$\nu$ is a distribution on $\Bool^n$, one has -$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$ - -Let $P$ be the matrix of a markov chain on $\Bool^n$. $P(x,\cdot)$ is the -distribution induced by the $x$-th row of $P$. If the markov chain induced by -$P$ has a stationary distribution $\pi$, then we define -$$d(t)=\max_{x\in\Bool^n}\tv{P^t(x,\cdot)-\pi}.$$ -It is known that $d(t+1)\leq d(t)$. \JFC{référence ? Cela a-t-il -un intérêt dans la preuve ensuite.} - - - -%and -% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ -% One can prove that \JFc{Ou cela a-t-il été fait?} -% $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$ - - - -Let $(X_t)_{t\in \mathbb{N}}$ be a sequence of $\Bool^n$ valued random -variables. A $\mathbb{N}$-valued random variable $\tau$ is a {\it stopping - time} for the sequence $(X_i)$ if for each $t$ there exists $B_t\subseteq -\Omega^{t+1}$ such that $\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$. -In other words, the event $\{\tau = t \}$ only depends on the values of -$(X_0,X_1,\ldots,X_t)$, not on $X_k$ with $k > t$. - - -\JFC{Je ne comprends pas la definition de randomized stopping time, Peut-on enrichir ?} - -Let $(X_t)_{t\in \mathbb{N}}$ be a markov chain and $f(X_{t-1},Z_t)$ a -random mapping representation of the markov chain. A {\it randomized - stopping time} for the markov chain is a stopping time for -$(Z_t)_{t\in\mathbb{N}}$. If the markov chain is irreductible and has $\pi$ -as stationary distribution, then a {\it stationary time} $\tau$ is a -randomized stopping time (possibily depending on the starting position $x$), -such that the distribution of $X_\tau$ is $\pi$: -$$\P_x(X_\tau=y)=\pi(y).$$ - - -\JFC{Ou ceci a-t-il ete prouvé} -\begin{Theo} -If $\tau$ is a strong stationary time, then $d(t)\leq \max_{x\in\Bool^n} -\P_x(\tau > t)$. -\end{Theo} - -% % Let us first recall the \emph{Total Variation} distance $\tv{\pi-\mu}$, -% % which is defined for two distributions $\pi$ and $\mu$ on the same set -% % $\Bool^n$ by: -% % $$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$ -% % It is known that -% % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$ - -% % Let then $M(x,\cdot)$ be the -% % distribution induced by the $x$-th row of $M$. If the Markov chain -% % induced by -% % $M$ has a stationary distribution $\pi$, then we define -% % $$d(t)=\max_{x\in\Bool^n}\tv{M^t(x,\cdot)-\pi}.$$ -% Intuitively $d(t)$ is the largest deviation between -% the distribution $\pi$ and $M^t(x,\cdot)$, which -% is the result of iterating $t$ times the function. -% Finally, let $\varepsilon$ be a positive number, the \emph{mixing time} -% with respect to $\varepsilon$ is given by -% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ -% It defines the smallest iteration number -% that is sufficient to obtain a deviation lesser than $\varepsilon$. -% Notice that the upper and lower bounds of mixing times cannot -% directly be computed with eigenvalues formulae as expressed -% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work -% only consider reversible Markov matrices whereas we do no restrict our -% matrices to such a form. - - - -Let us finally present the pseudorandom number generator $\chi_{\textit{15Rairo}}$ -which is based on random walks in $\Gamma(f)$. -More precisely, let be given a Boolean map $f:\Bool^n \rightarrow \Bool^n$, -a PRNG \textit{Random}, -an integer $b$ that corresponds an iteration number (\textit{i.e.}, the lenght of the walk), and +Let us finally recall the pseudorandom number generator $\chi_{\textit{14Secrypt}}$ +\cite{DBLP:conf/secrypt/CouchotHGWB14} +formalized in Algorithm~\ref{CI Algorithm}. +It is based on random walks in $\Gamma(f)$. +More precisely, let be given a Boolean map $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$, +an input PRNG \textit{Random}, +an integer $b$ that corresponds to a number of iterations, and an initial configuration $x^0$. Starting from $x^0$, the algorithm repeats $b$ times a random choice of which edge to follow and traverses this edge. The final configuration is thus outputted. -This PRNG is formalized in Algorithm~\ref{CI Algorithm}. - \begin{algorithm}[ht] -%\begin{scriptsize} -\KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($n$ bits)} -\KwOut{a configuration $x$ ($n$ bits)} +\begin{scriptsize} +%\JFC{Mettre ceci dans une boite flottante} +\KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ (${\mathsf{N}}$ bits)} +\KwOut{a configuration $x$ (${\mathsf{N}}$ bits)} $x\leftarrow x^0$\; \For{$i=0,\dots,b-1$} { -\If{$\textit{Random}(1) \neq 0$}{ -$s\leftarrow{\textit{Random}(n)}$\; -$x\leftarrow{F_f(s,x)}$\; -} +$s\leftarrow{\textit{Random}({\mathsf{N}})}$\; +$x\leftarrow{F_f(x,s)}$\; } return $x$\; -%\end{scriptsize} -\caption{Pseudo Code of the $\chi_{\textit{15Rairo}}$ PRNG} +\end{scriptsize} +\caption{Pseudo Code of the $\chi_{\textit{14Secrypt}}$ PRNG} \label{CI Algorithm} \end{algorithm} -This PRNG is a particularized version of Algorithm given in~\cite{DBLP:conf/secrypt/CouchotHGWB14}. -As this latter, the length of the random -walk of our algorithm is always constant (and is equal to $b$). -However, in the current version, we add the constraint that +With all this material, we can study the chaos properties of these +function. +This is the aims of the next section. -Let $f: \Bool^{n} \rightarrow \Bool^{n}$. -It has been shown~\cite[Th. 4, p. 135]{BCGR11}} that -if its iteration graph is strongly connected, then -the output of $\chi_{\textit{14Secrypt}}$ follows -a law that tends to the uniform distribution -if and only if its Markov matrix is a doubly stochastic matrix. - -Let us now present a method to -generate functions -with Doubly Stochastic matrix and Strongly Connected iteration graph, -denoted as DSSC matrix.