X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/c9d6a79d174af327059607a3e0a1f23ab7921a49..79f46c777f6ef3202c2fb25194822518cad3e32c:/generating.tex diff --git a/generating.tex b/generating.tex index 0837fda..377c811 100644 --- a/generating.tex +++ b/generating.tex @@ -3,9 +3,7 @@ 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. - - +if and only if its Markov matrix is a doubly stochastic one. In~\cite[Section 4]{DBLP:conf/secrypt/CouchotHGWB14}, we have presented a general scheme which generates function with strongly connected iteration graph $\Gamma(f)$ and @@ -19,7 +17,7 @@ is removed, an edge $(x,x)$ is added. 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$ +$000,100,101,001,011,111,$ $110,010,000$ has been removed. \end{xpl} @@ -31,7 +29,7 @@ has the awaited property with regard to the connectivity. \begin{thrm} The iteration graph $\Gamma(f)$ issued from the ${\mathsf{N}}$-cube where an Hamiltonian -cycle is removed is strongly connected. +cycle is removed, is strongly connected. \end{thrm} Moreover, if all the transitions have the same probability ($\frac{1}{n}$), @@ -64,13 +62,13 @@ Thus, there exists $b$ such that there is an arc between any $x$ and $y$. This section ends with the idea of removing a Hamiltonian cycle in the $\mathsf{N}$-cube. In such a context, the Hamiltonian cycle is equivalent to a Gray code. -Many approaches have been proposed a way to build such codes, for instance +Many approaches have been proposed as a way to build such codes, for instance the Reflected Binary Code. In this one and for a $\mathsf{N}$-length cycle, one of the bits is exactly switched $2^{\mathsf{N}-1}$ times whereas the others bits are modified at most $\left\lfloor \dfrac{2^{\mathsf{N-1}}}{\mathsf{N}-1} \right\rfloor$ times. It is clear that the function that is built from such a code would -not provide a uniform output. +not provide an uniform output. The next section presents how to build balanced Hamiltonian cycles in the $\mathsf{N}$-cube with the objective to embed them into the