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 a general scheme which generates 
function with strongly connected iteration graph $\Gamma(f)$ and
with doubly stochastic Markov probability matrix.

Basically, let us 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{thrm}
The iteration graph $\Gamma(f)$ issued from
the ${\mathsf{N}}$-cube where an Hamiltonian 
cycle is removed is strongly connected.
\end{thrm}

Moreover, if all the transitions have the same probability ($\frac{1}{n}$),
we have proven the following results:
\begin{thrm}
The Markov Matrix $M$ resulting from the ${\mathsf{N}}$-cube in
which an Hamiltonian 
cycle is removed, is doubly stochastic.
\end{thrm}

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:
\emph{can we always find $b$ such that $\Gamma_{\{b\}}(f)$ is strongly connected?}

The answer is indeed positive. We furthermore have the following strongest 
result.
\begin{thrm}
There exist $b \in \Nats$ such that $\Gamma_{\{b\}}(f)$ is complete.
\end{thrm}
\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.
Thus, there exists $b$ such that there is an arc between any $x$ and $y$.
\end{proof}

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 
the Reflected Binary Code. In this one, one of the bits is switched 
exactly $2^{\mathsf{N}-}$ \ANNOT{formule incomplète : $2^{\mathsf{N}-1}$ ??} for a $\mathsf{N}$-length cycle. 

%%%%%%%%%%%%%%%%%%%%%

The function that is built 
from the \ANNOT{Phrase non terminée}

The next section presents how to build balanced Hamiltonian cycles in the 
$\mathsf{N}$-cube with the objective to embed them into the 
pseudorandom number generator.

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "main"
%%% ispell-dictionary: "american"
%%% mode: flyspell
%%% End:
