syntaxe

diff --git a/main.tex b/main.tex
index efbc870021ddc089d08b8ccc98249b1e2a51c8c7..e10eba456a5520422f238028edb80ec5b5d1c85f 100644 (file)
--- 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). 
 
 % 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{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{...}
 
 
 \section{Conclusion}
 %\input{conclusion}
 
 %\acknowledgements{...}
 

-
+\bibliographystyle{alpha}

 \bibliography{biblio}
 
 \end{document}
 \bibliography{biblio}
 
 \end{document}

diff --git a/preliminaries.tex b/preliminaries.tex
index 628cd446996d1436e2bfb6923e5fc3f3c9ffe6b6..de77e127eb5f560c4805cfc970b5cf3769c6c250 100644 (file)
--- a/preliminaries.tex
+++ b/preliminaries.tex
@@ -53,12 +53,12 @@ Figure~\ref{fig:iteration:f*}.
 
 
 Let thus be given such kind of map.
 
 
 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 
 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.
 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}$$
 
 $\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}.$$
 $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.}
 
 
 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 ?}
 
 
 \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
 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).$$
 
 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.