Ajout diapos présentation PRNG

[16dcc.git] / generating.tex

diff --git a/generating.tex b/generating.tex
index 5b0d3931f3e51269806ef6df83a11a0731408304..377c8110b7dd0edaa6628468b9bb42018b5debf2 100644 (file)
--- a/generating.tex
+++ b/generating.tex
@@ -3,16 +3,13 @@ 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 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},
 In~\cite[Section 4]{DBLP:conf/secrypt/CouchotHGWB14},

-we have presented an efficient
-approach which generates 
+we have presented a general scheme which generates 

 function with strongly connected iteration graph $\Gamma(f)$ and
 with doubly stochastic Markov probability matrix.
 
 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 
+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. 
 
 remove one Hamiltonian cycle in this one. When an edge $(x,y)$ 
 is removed, an edge $(x,x)$ is added. 
 


@@ -20,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 
 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}
 
 has been removed.
 \end{xpl}
 


@@ -32,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 
 \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}$),
 \end{thrm}
 
 Moreover, if all the transitions have the same probability ($\frac{1}{n}$),


@@ -46,21 +43,40 @@ cycle is removed, is doubly stochastic.
 Let us consider now a ${\mathsf{N}}$-cube where an Hamiltonian 
 cycle is removed.
 Let $f$ be the corresponding function.
 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 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 furtheremore have the following strongest 
+The answer is indeed positive. We furthermore have the following strongest 

 result.
 \begin{thrm}
 result.
 \begin{thrm}

-There exist $b \in \Nats$ such that $\Gamma_{\{b\}}(f)$ is complete.
+There exists $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.
 \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.

-There exists thus $b$ such there is an arc between any $x$ and $y$.
+Thus, there exists $b$ such that there is an arc between any $x$ and $y$.

 \end{proof}
 
 \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
+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 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 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 
+pseudorandom number generator.
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: "main"
+%%% ispell-dictionary: "american"
+%%% mode: flyspell
+%%% End: