From: Jean-François Couchot <couchot@couchot.iut-bm.univ-fcomte.fr>
Date: Fri, 13 Mar 2015 09:04:49 +0000 (+0100)
Subject: generating : synthese secrypt + mons
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/006d3c5dcaf6d769591b2496d592e87066b0ec42

generating : synthese secrypt + mons
---

diff --git a/generating.tex b/generating.tex
new file mode 100644
index 0000000..7e41a7d
--- /dev/null
+++ b/generating.tex
@@ -0,0 +1,66 @@
+First of all, let $f: \Bool^{{\mathsf{N}}} \rightarrow \Bool^{{\mathsf{N}}}$.
+It has been shown~\cite[Theorem 4]{bcgr11:ip} that 
+if its iteration graph $\Gamma(f)$ 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.
+
+
+In~\cite[Section 4]{DBLP:conf/secrypt/CouchotHGWB14},
+we have presented an efficient
+approach which generates 
+function with strongly connected iteration graph $\Gamma(f)$ and
+with doubly stochastic Markov probability matrix.
+
+Basically, let consider the ${\mathsf{N}}$-cube. Let us next 
+remove one Hamiltonian cycle in this one. When an edge $(x,y)$ 
+is removed, an edge $(x,x)$ is added. 
+
+\begin{xpl}
+For instance, the iteration graph $\Gamma(f^*)$ 
+(given in Figure~\ref{fig:iteration:f*}) 
+is the $3$-cube in which the Hamiltonian cycle 
+$000,100,101,001,011,111,110,010,000$ 
+has been removed.
+\end{xpl}
+
+We first have proven the following result, which 
+states that the ${\mathsf{N}}$-cube without one
+Hamiltonian cycle 
+has the awaited property with regard to the connectivity.
+
+\begin{Theo}
+The iteration graph $\Gamma(f)$ issued from
+the ${\mathsf{N}}$-cube where an Hamiltonian 
+cycle is removed is strongly connected.
+\end{Theo}
+
+Moreover, if all the transitions have the same probability ($\frac{1}{n}$),
+we have proven the following results:
+\begin{Theo}
+The Markov Matrix $M$ resulting from the ${\mathsf{N}}$-cube in
+which an Hamiltonian 
+cycle is removed, is doubly stochastic.
+\end{Theo}
+
+Let us consider now a ${\mathsf{N}}$-cube where an Hamiltonian 
+cycle is removed.
+Let $f$ be the corresponding function.
+The question which remains to solve is
+can we always find $b$ such that $\Gamma_{\{b\}}(f)$ is strongly connected.
+
+The answer is indeed positive. We furtheremore have the following strongest 
+result.
+\begin{Theo}
+There exist $b \in \Nats$ such that $\Gamma_{\{b\}}(f)$ is complete.
+\end{Theo}
+\begin{proof}
+There is an arc $(x,y)$ in the 
+graph $\Gamma_{\{b\}}(f)$ if and only if $M^b_{xy}$ is positive
+where $M$ is the Markov matrix of $\Gamma(f)$.
+It has been shown in~\cite[Lemma 3]{bcgr11:ip}  that $M$ is regular.
+There exists thus $b$ such there is an arc between any $x$ and $y$.
+\end{proof}
+
+Details on the construction of hamiltonian paths in the 
+$\mathsf{N}$-cube may be found in~\cite[Section 4]{DBLP:conf/secrypt/CouchotHGWB14}.
\ No newline at end of file