From: couchot Date: Wed, 18 Feb 2015 11:54:55 +0000 (+0100) Subject: syntaxe X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/bc87eea8f89e38db87cb1d4705c6cfbfa993e27c syntaxe --- diff --git a/main.tex b/main.tex index efbc870..e10eba4 100644 --- a/main.tex +++ b/main.tex @@ -132,22 +132,22 @@ may be updated at each iteration. At the theoretical level, we show that % Donner la borne du stopping time quand on marche dedans (nouveau). % Énoncer le problème de la taille de cette borne (elle est certes finie, mais grande). - +\section{Proofs of Chaos in this context} \section{Quality study of the strategy} %6) Se pose alors la question de comment générer une stratégie de "bonne qualité". Par exemple, combien de générateurs aléatoires embarquer ? (nouveau) -\section{Expérimentations} -% +\section{Application to Pseudorandom Number Generation} +\input{prng} \section{Conclusion} %\input{conclusion} %\acknowledgements{...} - +\bibliographystyle{alpha} \bibliography{biblio} \end{document} diff --git a/preliminaries.tex b/preliminaries.tex index 628cd44..de77e12 100644 --- a/preliminaries.tex +++ b/preliminaries.tex @@ -53,12 +53,12 @@ Figure~\ref{fig:iteration:f*}. Let thus be given such kind of map. -This article focusses on studying its iterations according to +This article focuses 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 +$n$-cube augmented 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. @@ -103,11 +103,11 @@ $$\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 +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 +It is known that $d(t+1)\leq d(t)$. \JFC{references ? Cela a-t-il un intérêt dans la preuve ensuite.} @@ -129,12 +129,12 @@ $(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$ +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 irreducible and has $\pi$ as stationary distribution, then a {\it stationary time} $\tau$ is a -randomized stopping time (possibily depending on the starting position $x$), +randomized stopping time (possibly depending on the starting position $x$), such that the distribution of $X_\tau$ is $\pi$: $$\P_x(X_\tau=y)=\pi(y).$$ @@ -173,53 +173,4 @@ If $\tau$ is a strong stationary time, then $d(t)\leq \max_{x\in\Bool^n} -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 -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)} -$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)}$\; -} -} -return $x$\; -%\end{scriptsize} -\caption{Pseudo Code of the $\chi_{\textit{15Rairo}}$ 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 - - -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.