From: couchot <jf.couchot@gmail.com>
Date: Tue, 10 Mar 2015 08:03:38 +0000 (+0100)
Subject: ajoutde prgn.tex
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/fe2fb6840b6891f539276e8215b1b8d762a90fd0?ds=inline

ajoutde prgn.tex
---

diff --git a/prng.tex b/prng.tex
new file mode 100644
index 0000000..2ceecc7
--- /dev/null
+++ b/prng.tex
@@ -0,0 +1,52 @@
+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 length 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 
+provided it is allowed to traverse it, \textit{i.e.}, 
+when $\textit{Random}(1)$ is not null. 
+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   
+the probability to execute the function $F_f$ is equal to 0.5 since
+the output of $\textit{Random(1)}$ is uniform in $\{0,1\}$.  
+
+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.