hamilton

diff --git a/biblio.bib b/biblio.bib
index c368f01d19f4d119c1629a0ae80743a1288e67b2..0857ae7143cd6268062bed9e3ad191405a91ae87 100644 (file)
--- a/biblio.bib
+++ b/biblio.bib
@@ -1029,3 +1029,54 @@ year = 2013,
   ee = {http://arxiv.org/abs/1112.5239}
 }
 
+
+
+@article{DBLP:journals/combinatorics/BhatS96,
+  author    = {Girish S. Bhat and
+               Carla D. Savage},
+  title     = {Balanced Gray Codes},
+  journal   = {Electr. J. Comb.},
+  volume    = {3},
+  number    = {1},
+  year      = {1996},
+  url       = {http://www.combinatorics.org/Volume_3/Abstracts/v3i1r25.html},
+  timestamp = {Tue, 05 Oct 2004 14:51:02 +0200},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/combinatorics/BhatS96},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+
+@Article{Bykov2016,
+author="Bykov, I. S.",
+title="On locally balanced gray codes",
+journal="Journal of Applied and Industrial Mathematics",
+year="2016",
+volume="10",
+number="1",
+pages="78--85",
+abstract="We consider locally balanced Gray codes.We say that a Gray code is locally balanced if every ``short'' subword in its transition sequence contains all letters of the alphabet |1, 2,..., n{\textasciitilde}. The minimal length of these subwords is the window width of the code. We show that for each n ≥ 3 there exists a Gray code with window width at most n + 3⌊log n⌋.",
+issn="1990-4797",
+doi="10.1134/S1990478916010099",
+url="http://dx.doi.org/10.1134/S1990478916010099"
+}
+
+
+@article{Robinson:1981:CS,
+ author = {Robinson, John P. and Cohn, Martin},
+ title = {Counting Sequences},
+ journal = {IEEE Trans. Comput.},
+ issue_date = {January 1981},
+ volume = {30},
+ number = {1},
+ month = jan,
+ year = {1981},
+ issn = {0018-9340},
+ pages = {17--23},
+ numpages = {7},
+ url = {http://dl.acm.org/citation.cfm?id=1963620.1963622},
+ acmid = {1963622},
+ publisher = {IEEE Computer Society},
+ address = {Washington, DC, USA},
+ keywords = {circuit testing, counters, gray codes, hamming distance, transition counts, uniform distance},
+} 
+

diff --git a/evalPRNG/compareFonctionMixingTime.py b/evalPRNG/compareFonctionMixingTime.py
index 5ff825101bfabcb31a906e0b13be7ec5ca5aebd3..d5dc782bf8902ca73672cea587519d072c643ed3 100644 (file)
--- a/evalPRNG/compareFonctionMixingTime.py
+++ b/evalPRNG/compareFonctionMixingTime.py
@@ -102,12 +102,12 @@ def MarkovMatrixSaut(fbin,n,p2n,lp2nm1):
 lf= []
 #lf +=[ [13, 10, 9, 14, 3, 11, 1, 12, 15, 4, 7, 5, 2, 6, 0, 8]] #4
 #lf += [[29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]] #5
-lf +=  [[55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49, 15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]] #6
+#lf +=  [[55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, 49, 15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, 40, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32]] #6
 #lf+= [[47, 58, 57, 44, 51, 42, 41, 60, 63, 22, 37, 53, 19, 54, 48, 32, 45, 14, 13, 46, 11, 43, 33, 8, 7, 36, 39, 4, 34, 50, 1, 40, 29, 62, 61, 30, 59, 27, 17, 56, 55, 20, 23, 52, 18, 2, 49, 24, 31, 10, 9, 28, 3, 26, 25, 12, 15, 38, 21, 5, 35, 6, 0, 16]]
 
 #lf += [[111, 94, 93, 116, 122, 90, 125, 88, 115, 126, 119, 84, 123, 98, 81, 120, 109, 106, 105, 110, 99, 107, 104, 72, 71, 118, 117, 96, 103, 102, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24, 85, 22, 69, 20, 19, 114, 17, 112, 77, 76, 13, 108, 74, 10, 9, 73, 67, 66, 101, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, 56, 48, 53, 38, 37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42, 46, 45, 41, 35, 34, 39, 52, 43, 50, 32, 36, 29, 28, 61, 92, 26, 18, 89, 25, 87, 30, 23, 4, 27, 2, 16, 80, 31, 78, 15, 14, 3, 11, 8, 12, 5, 70, 21, 68, 7, 6, 65, 1]] #7
 
-#lf += [[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180, 227, 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, 229, 166, 165, 244, 163, 242, 241, 192, 215, 220, 205, 216, 218, 222, 221, 208, 213, 210, 212, 214, 219, 211, 217, 209, 239, 202, 207, 140, 139, 234, 193, 204, 135, 196, 199, 132, 194, 130, 225, 200, 159, 62, 185, 252, 59, 250, 169, 56, 191, 246, 245, 52, 243, 50, 176, 48, 173, 238, 189, 44, 235, 42, 137, 184, 231, 38, 37, 228, 35, 226, 177, 224, 151, 156, 141, 152, 154, 158, 157, 144, 149, 146, 148, 150, 155, 147, 153, 145, 175, 206, 143, 136, 11, 142, 129, 8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122, 126, 125, 112, 117, 114, 116, 100, 123, 98, 97, 113, 79, 106, 111, 110, 99, 74, 121, 120, 71, 118, 103, 101, 115, 66, 65, 104, 127, 90, 89, 94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72, 107, 78, 105, 64, 69, 102, 68, 70, 75, 67, 73, 96, 55, 58, 45, 188, 51, 186, 61, 40, 119, 182, 181, 53, 179, 54, 33, 49, 15, 174, 47, 60, 171, 46, 57, 32, 167, 6, 36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, 138, 41, 12, 39, 134, 133, 5, 131, 34, 9, 128]]#8 pas totally
+lf += [[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180, 227, 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, 229, 166, 165, 244, 163, 242, 241, 192, 215, 220, 205, 216, 218, 222, 221, 208, 213, 210, 212, 214, 219, 211, 217, 209, 239, 202, 207, 140, 139, 234, 193, 204, 135, 196, 199, 132, 194, 130, 225, 200, 159, 62, 185, 252, 59, 250, 169, 56, 191, 246, 245, 52, 243, 50, 176, 48, 173, 238, 189, 44, 235, 42, 137, 184, 231, 38, 37, 228, 35, 226, 177, 224, 151, 156, 141, 152, 154, 158, 157, 144, 149, 146, 148, 150, 155, 147, 153, 145, 175, 206, 143, 136, 11, 142, 129, 8, 7, 198, 197, 4, 195, 2, 161, 160, 255, 124, 109, 108, 122, 126, 125, 112, 117, 114, 116, 100, 123, 98, 97, 113, 79, 106, 111, 110, 99, 74, 121, 120, 71, 118, 103, 101, 115, 66, 65, 104, 127, 90, 89, 94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72, 107, 78, 105, 64, 69, 102, 68, 70, 75, 67, 73, 96, 55, 58, 45, 188, 51, 186, 61, 40, 119, 182, 181, 53, 179, 54, 33, 49, 15, 174, 47, 60, 171, 46, 57, 32, 167, 6, 36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, 138, 41, 12, 39, 134, 133, 5, 131, 34, 9, 128]]#8 pas totally
 
 lf +=[[223, 250, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180, 227, 178, 240, 248, 237, 236, 173, 172, 171, 238, 201, 168, 229, 166, 228, 244, 235, 242, 241, 192, 215, 220, 205, 216, 218, 222, 153, 152, 151, 210, 212, 214, 219, 146, 217, 209, 239, 142, 141, 206, 195, 234, 193, 136, 231, 196, 199, 197, 194, 226, 225, 200, 63, 188, 253, 252, 59, 190, 189, 176, 191, 246, 245, 164, 243, 162, 161, 177, 143, 170, 45, 44, 43, 138, 185, 184, 135, 38, 167, 165, 179, 34, 129, 224, 31, 154, 221, 158, 147, 26, 25, 156, 159, 22, 213, 149, 211, 150, 144, 208, 207, 14, 13, 204, 203, 202, 169, 8, 133, 198, 132, 4, 139, 131, 1, 160, 255, 124, 109, 108, 122, 126, 125, 112, 117, 114, 116, 100, 123, 98, 97, 113, 79, 106, 111, 110, 99, 74, 121, 120, 71, 118, 103, 101, 115, 66, 65, 104, 127, 90, 89, 94, 83, 91, 81, 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72, 107, 78, 105, 64, 69, 102, 68, 70, 75, 67, 73, 96, 55, 58, 57, 62, 51, 186, 41, 40, 119, 182, 181, 53, 35, 54, 48, 56, 175, 174, 61, 60, 11, 46, 9, 32, 37, 6, 36, 52, 163, 50, 49, 0, 23, 28, 157, 24, 155, 30, 29, 16, 21, 18, 20, 148, 27, 19, 145, 17, 47, 10, 15, 140, 3, 42, 137, 12, 39, 134, 7, 5, 2, 130, 33, 128]] #8 totally
 

diff --git a/generating.tex b/generating.tex
index 5b0d3931f3e51269806ef6df83a11a0731408304..354058afe5fb3822e93a5189de9419e44deaf094 100644 (file)
--- a/generating.tex
+++ b/generating.tex
@@ -62,5 +62,6 @@ 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
+The next section presents how to build hamiltonian cycles in the 
+$\mathsf{N}$-cube with the objective to embed them into the 
+pseudorandom number generator.

diff --git a/hamilton.tex b/hamilton.tex
index 8f022c611ee37cac96201447b9f6678d1f6c3c85..694bbcf82c301ab14b9a96a88f0552fdf2affb7f 100644 (file)
--- a/hamilton.tex
+++ b/hamilton.tex
@@ -1,7 +1,7 @@
 Many approaches have been developed to solve the problem of building
-a Gray code in a $\mathsf{N}$ cube~\cite{}, according to properties 
+a Gray code in a $\mathsf{N}$ cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, according to properties 
 the produced code has to verify.
-For instance,~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} focus on
+For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on
 balanced Gray codes. In the transition sequence of these codes, 
 the number of transitions of each element must differ
 at most by 2.
@@ -27,9 +27,130 @@ However, none of the two algorithms is compatible with the second one:
 balanced Gray codes that are generated by state of the art works~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} are not locally balanced. Conversely,
 locally balanced Gray codes yielded by Igor Bykov approach~\cite{Bykov2016}
 are not globally balanced.
-This section thus show how the non deterministic approach 
+This section thus shows how the non deterministic approach 
 presented in~\cite{ZanSup04} has been automatized to provide balanced 
 Hamiltonian paths such that, for each subpart, 
-the number of swiches of each element is as constant as possible.
+the number of switches of each element is as uniform as possible.
 
+\subsection{Analysis of the Robinson-Cohn extension algorithm}
+As far as we know three works, 
+namely~\cite{Robinson:1981:CS},~\cite{DBLP:journals/combinatorics/BhatS96}, 
+and~\cite{ZanSup04} have adressed the probem of providing an approach
+to produce balanced gray code.
+The authors of~\cite{Robinson:1981:CS} introduced an inductive approach
+aiming at producing balanced Gray codes, provided the user gives 
+a special subsequence of the transition sequence at each induction step.
+This work have been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96}
+where the authors have explicitely shown how to construct such a subsequence.
+Finally the authors of~\cite{ZanSup04} have presented 
+the \emph{Robinson-Cohn extension} 
+algorithm. There rigourous presentation of this one 
+have mainly allowed them to prove two properties.
+The former states that if 
+$\mathsf{N}$ is a 2-power, a balanced Gray code is always totally balanced.
+The latter states that for every $\mathsf{N}$ there 
+exists a Gray code such that all transition count numbers are 
+are 2-powers whose exponents are either equal
+or differ from each other by 1.
+However, the authors do not prove that the approach allows to build 
+(totally balanced) Gray code. 
+What follows shows that this fact is established and first recalls the approach.
 
+
+Let be given a $\mathsf{N}-2$-bit Gray code whose transition sequence is
+$S_{\mathsf{N}-2}$. What follows is the 
+ \emph{Robinson-Cohn extension} method~\cite{ZanSup04}
+which produces a $n$-bits Gray code.
+
+\begin{enumerate}
+\item \label{item:nondet}Let $l$ be an even positive integer. Find 
+$u_1, u_2, \dots , u_{l-2}, v$ (maybe empty) subsequences of $S_{\mathsf{N}-2}$ 
+such that $S_{\mathsf{N}-2}$ is the concatenation of 
+$$
+s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, . . . , s_{i_l-1}, u_{l-2}, s_{i_l}, v
+$$
+where $i_1 = 1$, $i_2 = 2$, and $u_0 = \emptyset$ (the empty sequence).
+\item Replace in $S_{\mathsf{N}-2}$ the sequences $u_0, u_1, u_2, \ldots, u_{l-2}$ 
+  by 
+  $\mathsf{N} - 1,  u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$
+  respectively, where $u'(u,x,y)$ is the sequence $u,x,u^R,y,u$ such that 
+  $u^R$ is $u$ in reversed order. 
+  The obtained sequence is further denoted as $U$.
+\item Construct the sequences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$, and let $W'$ be $W$ where the first 
+two elements have been exchanged.
+\item The transition sequence $S_{\mathsf{N}}$ is thus the concatenation $U^R, V, W'$.
+\end{enumerate} 
+
+It has been proven in~\cite{ZanSup04} that 
+$S_{\mathsf{N}}$ is transition sequence of a cyclic $\mathsf{N}$-bits Gray code 
+if $S_{\mathsf{N}-2}$ is. 
+However, the step~(\ref{item:nondet}) is not a constructive 
+step that precises how to select the subsequences which ensures that 
+yielded Gray code is balanced.
+Next section shows how to choose the sequence $l$ to have the balancy property.
+
+\subsection{Balanced Codes}
+Let us first recall how to formalize the balancy property of a Gray code.
+Let  $L = w_1, w_2, \dots, w_{2^\mathsf{N}}$ be the sequence 
+of a $\mathsf{N}$-bits cyclic Gray code. 
+The  transition sequence 
+$S = s_1, s_2, \dots, s_{2^n}$, $s_i$, $1 \le i \le 2^\mathsf{N}$,
+indicates which bit position changes between 
+codewords at index $i$ and $i+1$ modulo $2^\mathsf{N}$. 
+The \emph{transition count} function  
+$\textit{TC}_{\mathsf{N}} : \{1,\dots, \mathsf{N}\} \rightarrow \{0, \ldots, 2^{\mathsf{N}}\}$ 
+gives the number of times $i$ occurs in $S$,
+\textit{i.e.}, the number of times 
+the bit $i$ has been switched in $L$.   
+
+The Gray code is \emph{totally balanced} if $\textit{TC}_{\mathsf{N}}$ 
+is constant (and equal to $\frac{2^{\mathsf{N}}}{\mathsf{N}}$).
+It is \emph{balanced} if for any two bit indices $i$ and $j$, 
+$|\textit{TC}_{\mathsf{N}}(i) - \textit{TC}_{\mathsf{N}}(j)| \le  2$.
+
+
+   
+\begin{xpl}
+Let $L^*=000,100,101,001,011,111,110,010$ be the Gray code that corresponds to 
+the Hamiltonian cycle that has been removed in $f^*$.
+Its transition sequence is $S=3,1,3,2,3,1,3,2$ and its transition count function is 
+$\textit{TC}_3(1)= \textit{TC}_3(2)=2$ and  $\textit{TC}_3(3)=4$. Such a Gray code is balanced. 
+
+Let now  
+$L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011, 0001, 0101,$
+$0100, 1100, 1101, 1001, 1011, 1010, 1000$
+be a cyclic Gray code. Since $S=2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4$ $\textit{TC}_4$ is equal to 4 everywhere, this code
+is thus totally balanced.
+
+On the contrary, for the standard $4$-bits Gray code  
+$L^{\textit{st}}=0000,0001,0011,0010,0110,0111,0101,0100,1100,$
+$1101,1111,1110,1010,1011,1001,1000$,
+we have $\textit{TC}_4(1)=8$ $\textit{TC}_4(2)=4$ $\textit{TC}_4(3)=\textit{TC}_4(4)=2$ and
+the code is neither balanced nor totally balanced.
+\end{xpl}
+
+
+\begin{thrm}\label{prop:balanced}
+Let $\mathsf{N}$ in $\Nats$, and $a_{\mathsf{N}}$ be defined by
+$a_{\mathsf{N}}= 2 \lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \rfloor$. 
+Then, there exists a sequence $l$ in 
+step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm
+such that all the transition counts $\textit{TC}_{\mathsf{N}}(i)$ 
+are $a_{\mathsf{N}}$ or $a_{\mathsf{N}}+2$ 
+for any $i$, $1 \le i \le \mathsf{N}$.
+
+
+
+
+\end{thrm}
+
+
+
+
+\begin{proof}
+
+
+
+\end{proof}
+
+\subsection{Toward a local uniform distribution of switches}

diff --git a/main.aux b/main.aux
index 9cfaa3d00646f6c701127c6b9302db459ad4c9f5..6f139013412f5a308b95fe8583437a513839220f 100644 (file)
--- a/main.aux
+++ b/main.aux
@@ -18,7 +18,7 @@
 \citation{chgw14oip}
 \citation{chgw14oip}
 \citation{DBLP:conf/secrypt/CouchotHGWB14}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{2}{\uppercase {Preliminaries}}}{3}}
+\@writefile{toc}{\contentsline {section}{\tocsection {}{2}{Preliminaries}}{3}}
 \newlabel{sec:preliminaries}{{2}{3}}
 \newlabel{eq:asyn}{{1}{3}}
 \citation{bcgr11:ip}
@@ -51,33 +51,55 @@
 \@writefile{toc}{\contentsline {section}{\tocsection {}{4}{Functions with Strongly Connected $\Gamma _{\{b\}}(f)$}}{10}}
 \newlabel{sec:SCCfunc}{{4}{10}}
 \citation{bcgr11:ip}
-\citation{DBLP:conf/secrypt/CouchotHGWB14}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{5}{Stopping Time}}{11}}
-\newlabel{sec:hypercube}{{5}{11}}
+\citation{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}
+\citation{DBLP:journals/combinatorics/BhatS96,ZanSup04}
+\citation{Bykov2016}
+\citation{ZanSup04,DBLP:journals/combinatorics/BhatS96}
+\citation{Bykov2016}
+\citation{ZanSup04}
+\@writefile{toc}{\contentsline {section}{\tocsection {}{5}{(Locally) Balanced Hamiltonian Cycle}}{11}}
+\newlabel{sec:hamilton}{{5}{11}}
+\citation{Robinson:1981:CS}
+\citation{DBLP:journals/combinatorics/BhatS96}
+\citation{ZanSup04}
+\citation{Robinson:1981:CS}
+\citation{DBLP:journals/combinatorics/BhatS96}
+\citation{ZanSup04}
+\citation{ZanSup04}
+\citation{ZanSup04}
+\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{5.1}{Analysis of the Robinson-Cohn extension algorithm}}{12}}
+\newlabel{item:nondet}{{1}{12}}
+\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{5.2}{Balanced Codes}}{13}}
+\newlabel{prop:balanced}{{5.1}{13}}
+\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{5.3}{Toward a local uniform distribution of switches}}{13}}
+\@writefile{toc}{\contentsline {section}{\tocsection {}{6}{Stopping Time}}{13}}
+\newlabel{sec:hypercube}{{6}{13}}
 \citation{LevinPeresWilmer2006}
-\newlabel{eq:Markov:rairo}{{3}{13}}
-\newlabel{lm:h}{{5.2}{13}}
+\newlabel{eq:Markov:rairo}{{3}{15}}
+\newlabel{lm:h}{{6.2}{15}}
 \citation{proba}
-\newlabel{prop:stop}{{5.4}{14}}
-\newlabel{prop:lambda}{{5.5}{14}}
-\newlabel{lm:stopprime}{{5.6}{15}}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{6}{Experiments}}{15}}
-\newlabel{sec:prng}{{6}{15}}
-\@writefile{loa}{\contentsline {algocf}{\numberline {2}{\ignorespaces Pseudo Code of the $\chi _{\textit  {15Rairo}}$ PRNG\relax }}{16}}
-\newlabel{CI Algorithm:2}{{2}{16}}
-\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Functions with DSCC Matrix and smallest MT\relax }}{17}}
-\newlabel{table:nc}{{1}{17}}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{7}{Conclusion}}{17}}
+\newlabel{prop:stop}{{6.4}{16}}
+\newlabel{prop:lambda}{{6.5}{16}}
+\newlabel{lm:stopprime}{{6.6}{17}}
+\@writefile{toc}{\contentsline {section}{\tocsection {}{7}{Experiments}}{17}}
+\newlabel{sec:prng}{{7}{17}}
+\@writefile{loa}{\contentsline {algocf}{\numberline {2}{\ignorespaces Pseudo Code of the $\chi _{\textit  {15Rairo}}$ PRNG\relax }}{18}}
+\newlabel{CI Algorithm:2}{{2}{18}}
+\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Functions with DSCC Matrix and smallest MT\relax }}{19}}
+\newlabel{table:nc}{{1}{19}}
+\@writefile{toc}{\contentsline {section}{\tocsection {}{8}{Conclusion}}{19}}
 \bibstyle{alpha}
 \bibdata{biblio}
 \bibcite{Banks92}{BBCS92}
 \bibcite{bcgr11:ip}{BCGR11}
 \bibcite{Nist10}{BR10}
+\bibcite{DBLP:journals/combinatorics/BhatS96}{BS96}
+\bibcite{Bykov2016}{Byk16}
 \bibcite{chgw14oip}{CHG{$^{+}$}14a}
+\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces NIST SP 800-22 test results ($\mathbb  {P}_T$)\relax }}{20}}
+\newlabel{The passing rate}{{2}{20}}
+\@writefile{toc}{\contentsline {section}{\tocsection {}{}{References}}{20}}
 \bibcite{DBLP:conf/secrypt/CouchotHGWB14}{CHG{$^{+}$}14b}
-\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces NIST SP 800-22 test results ($\mathbb  {P}_T$)\relax }}{18}}
-\newlabel{The passing rate}{{2}{18}}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{}{References}}{18}}
 \bibcite{5376454}{CMZ09}
 \bibcite{Devaney}{Dev89}
 \bibcite{guyeuxTaiwan10}{GWB10}
@@ -85,8 +107,10 @@
 \bibcite{LEcuyerS07}{LS07}
 \bibcite{Marsaglia1996}{Mar96}
 \bibcite{proba}{MU05}
+\bibcite{Robinson:1981:CS}{RC81}
 \bibcite{915385}{SK01}
 \bibcite{915396}{SPK01}
+\bibcite{ZanSup04}{SZ04}
 \bibcite{wbg10ip}{WBGF10}
 \newlabel{tocindent-1}{0pt}
 \newlabel{tocindent0}{13.28564pt}

diff --git a/main.bbl b/main.bbl
index 6cb5b6baee66203370d89aaaa19e7522ba4d2e4d..e2aaabba32291caae31481dda76ac24d6ada7a5c 100644 (file)
--- a/main.bbl
+++ b/main.bbl
@@ -19,6 +19,17 @@ E.~Barker and A.~Roginsky.
 \newblock Draft {N}{I}{S}{T} special publication 800-131 recommendation for the
   transitioning of cryptographic algorithms and key sizes, 2010.
 
+\bibitem[BS96]{DBLP:journals/combinatorics/BhatS96}
+Girish~S. Bhat and Carla~D. Savage.
+\newblock Balanced gray codes.
+\newblock {\em Electr. J. Comb.}, 3(1), 1996.
+
+\bibitem[Byk16]{Bykov2016}
+I.~S. Bykov.
+\newblock On locally balanced gray codes.
+\newblock {\em Journal of Applied and Industrial Mathematics}, 10(1):78--85,
+  2016.
+
 \bibitem[CHG{\etalchar{+}}14a]{chgw14oip}
 Jean-Fran\c{c}ois Couchot, Pierre-Cyrille H\'eam, Christophe Guyeux, Qianxue
   Wang, and Jacques Bahi.
@@ -76,6 +87,11 @@ M.~Mitzenmacher and Eli Upfal.
 \newblock {\em Probability and Computing}.
 \newblock Cambridge University Press, 2005.
 
+\bibitem[RC81]{Robinson:1981:CS}
+John~P. Robinson and Martin Cohn.
+\newblock Counting sequences.
+\newblock {\em IEEE Trans. Comput.}, 30(1):17--23, January 1981.
+
 \bibitem[SK01]{915385}
 T.~Stojanovski and L.~Kocarev.
 \newblock Chaos-based random number generators-part i: analysis [cryptography].
@@ -88,6 +104,12 @@ T.~Stojanovski, J.~Pihl, and L.~Kocarev.
 \newblock {\em Circuits and Systems I: Fundamental Theory and Applications,
   IEEE Transactions on}, 48(3):382--385, Mar 2001.
 
+\bibitem[SZ04]{ZanSup04}
+IN~Suparta and AJ~van Zanten.
+\newblock Totally balanced and exponentially balanced gray codes.
+\newblock {\em Discrete Analysis and Operation Research (Russia)},
+  11(4):81--98, 2004.
+
 \bibitem[WBGF10]{wbg10ip}
 Qianxue Wang, Jacques Bahi, Christophe Guyeux, and Xiaole Fang.
 \newblock Randomness quality of {CI} chaotic generators. application to

diff --git a/main.blg b/main.blg
index 86a026ae31d0801d4c0d9cb21ccb015b30e0f1b3..b2d76191b07b9db23757cf048f8cca48cfe96e4c 100644 (file)
--- a/main.blg
+++ b/main.blg
@@ -1,46 +1,48 @@
-This is BibTeX, Version 0.99d (TeX Live 2013/Debian)
+This is BibTeX, Version 0.99d (TeX Live 2015/dev/Debian)
 Capacity: max_strings=35307, hash_size=35307, hash_prime=30011
 The top-level auxiliary file: main.aux
 The style file: alpha.bst
 Database file #1: biblio.bib
-You've used 15 entries,
+Warning--I didn't find a database entry for ""
+You've used 19 entries,
             2543 wiz_defined-function locations,
-            664 strings with 7466 characters,
-and the built_in function-call counts, 7127 in all, are:
-= -- 715
-> -- 366
-< -- 11
-+ -- 132
-- -- 129
-* -- 524
-:= -- 1142
-add.period$ -- 50
-call.type$ -- 15
-change.case$ -- 102
-chr.to.int$ -- 14
-cite$ -- 15
-duplicate$ -- 282
-empty$ -- 499
-format.name$ -- 144
-if$ -- 1499
+            695 strings with 8037 characters,
+and the built_in function-call counts, 8579 in all, are:
+= -- 865
+> -- 431
+< -- 12
++ -- 152
+- -- 149
+* -- 635
+:= -- 1386
+add.period$ -- 62
+call.type$ -- 19
+change.case$ -- 125
+chr.to.int$ -- 18
+cite$ -- 19
+duplicate$ -- 338
+empty$ -- 604
+format.name$ -- 169
+if$ -- 1790
 int.to.chr$ -- 2
 int.to.str$ -- 0
-missing$ -- 17
-newline$ -- 80
-num.names$ -- 47
-pop$ -- 107
+missing$ -- 21
+newline$ -- 100
+num.names$ -- 59
+pop$ -- 119
 preamble$ -- 1
-purify$ -- 119
+purify$ -- 146
 quote$ -- 0
-skip$ -- 248
+skip$ -- 299
 stack$ -- 0
-substring$ -- 382
-swap$ -- 76
-text.length$ -- 11
-text.prefix$ -- 2
+substring$ -- 463
+swap$ -- 80
+text.length$ -- 12
+text.prefix$ -- 3
 top$ -- 0
-type$ -- 108
+type$ -- 140
 warning$ -- 0
-while$ -- 64
-width$ -- 17
-write$ -- 207
+while$ -- 80
+width$ -- 21
+write$ -- 259
+(There was 1 warning)

diff --git a/main.log b/main.log
index 9a092cc8c0fefb6743474ca0a00755b0df551da8..749adc158e82154a132d3a564b662c0175fa12a6 100644 (file)
--- a/main.log
+++ b/main.log
@@ -1,4 +1,4 @@
-This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2015/dev/Debian) (preloaded format=pdflatex 2015.11.13)  1 APR 2016 11:05
+This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2015/dev/Debian) (preloaded format=pdflatex 2015.11.13)  7 APR 2016 10:48
 entering extended mode
  restricted \write18 enabled.
  %&-line parsing enabled.
@@ -1301,8 +1301,32 @@ Underfull \hbox (badness 10000) in paragraph at lines 472--477
 ; :::; a[]; :::; a[];$
  []
 
-[9 <./graphe1.pdf> <./graphe2.pdf>]) (./generating.tex [10]) (./stopping.tex
-[11] [12] [13] [14]) (./prng.tex [15]
+[9 <./graphe1.pdf> <./graphe2.pdf>]) (./generating.tex [10]) (./hamilton.tex
+[11] [12]
+Overfull \hbox (104.68428pt too wide) in paragraph at lines 119--124
+[]\T1/cmr/m/it/10 Let now $\OML/cmm/m/it/10 L[] \OT1/cmr/m/n/10 = 0000\OML/cmm/
+m/it/10 ; \OT1/cmr/m/n/10 0010\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 0110\OML/cmm/m
+/it/10 ; \OT1/cmr/m/n/10 1110\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 1111\OML/cmm/m/
+it/10 ; \OT1/cmr/m/n/10 0111\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 0011\OML/cmm/m/i
+t/10 ; \OT1/cmr/m/n/10 0001\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 0101\OML/cmm/m/it
+/10 ;$ $\OT1/cmr/m/n/10 0100\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 1100\OML/cmm/m/i
+t/10 ; \OT1/cmr/m/n/10 1101\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 1001\OML/cmm/m/it
+/10 ; \OT1/cmr/m/n/10 1011\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 1010\OML/cmm/m/it/
+10 ; \OT1/cmr/m/n/10 1000$
+ []
+
+
+Overfull \hbox (116.14502pt too wide) in paragraph at lines 125--130
+[]\T1/cmr/m/it/10 On the con-trary, for the stan-dard $\OT1/cmr/m/n/10 4$\T1/cm
+r/m/it/10 -bits Gray code $\OML/cmm/m/it/10 L[] \OT1/cmr/m/n/10 = 0000\OML/cmm/
+m/it/10 ; \OT1/cmr/m/n/10 0001\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 0011\OML/cmm/m
+/it/10 ; \OT1/cmr/m/n/10 0010\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 0110\OML/cmm/m/
+it/10 ; \OT1/cmr/m/n/10 0111\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 0101\OML/cmm/m/i
+t/10 ; \OT1/cmr/m/n/10 0100\OML/cmm/m/it/10 ; \OT1/cmr/m/n/10 1100\OML/cmm/m/it
+/10 ;$
+ []
+
+) (./stopping.tex [13] [14] [15] [16]) (./prng.tex [17]
 
 LaTeX Warning: Command \textcircled invalid in math mode on input line 64.
 
@@ -1347,7 +1371,7 @@ LaTeX Warning: Command \textcircled invalid in math mode on input line 172.
 
 LaTeX Warning: Command \textcircled invalid in math mode on input line 172.
 
-[16]
+[18]
 
 LaTeX Warning: Command \textcircled invalid in math mode on input line 231.
 
@@ -1386,21 +1410,21 @@ Overfull \hbox (4.26556pt too wide) in paragraph at lines 229--250
 ) (./conclusion.tex
 Missing character: There is no p in font dsrom8!
 Missing character: There is no p in font dsrom8!
- [17]) (./main.bbl [18]
-Underfull \hbox (badness 10000) in paragraph at lines 70--73
+ [19]) (./main.bbl [20]
+Underfull \hbox (badness 10000) in paragraph at lines 81--84
 []\T1/cmr/m/n/8 G. Marsaglia. Diehard: a bat-tery of tests of ran-dom-ness.
  []
 
-) [19] (./main.aux) )
+) [21] (./main.aux) )
 (\end occurred inside a group at level 1)
 
 ### simple group (level 1) entered at line 10 ({)
 ### bottom level 
 Here is how much of TeX's memory you used:
- 22182 strings out of 494950
- 431307 string characters out of 6179039
+ 22192 strings out of 494950
+ 431459 string characters out of 6179039
  561594 words of memory out of 5000000
- 24709 multiletter control sequences out of 15000+600000
+ 24716 multiletter control sequences out of 15000+600000
  28957 words of font info for 91 fonts, out of 8000000 for 9000
  197 hyphenation exceptions out of 8191
  54i,17n,75p,539b,695s stack positions out of 5000i,500n,10000p,200000b,80000s
@@ -1445,10 +1469,10 @@ pe1/public/amsfonts/symbols/msbm10.pfb></usr/share/texlive/texmf-dist/fonts/typ
 e1/public/amsfonts/symbols/msbm7.pfb></usr/share/texlive/texmf-dist/fonts/type1
 /public/stmaryrd/stmary10.pfb></usr/share/texlive/texmf-dist/fonts/type1/public
 /stmaryrd/stmary7.pfb>
-Output written on main.pdf (19 pages, 467540 bytes).
+Output written on main.pdf (21 pages, 479708 bytes).
 PDF statistics:
- 813 PDF objects out of 1000 (max. 8388607)
- 210 compressed objects within 3 object streams
+ 826 PDF objects out of 1000 (max. 8388607)
+ 214 compressed objects within 3 object streams
  0 named destinations out of 1000 (max. 500000)
  28 words of extra memory for PDF output out of 10000 (max. 10000000)
 

diff --git a/main.pdf b/main.pdf
index aff26ba1086fc244627aa1800a2e351a485a652e..6d1894cf239a55c201358ab35db3ecad06a00764 100644 (file)
Binary files a/main.pdf and b/main.pdf differ

diff --git a/main.tex b/main.tex
index 465fbf5a2d179b15236d958a0c98136a958c0de4..773caeeb7574ea491fb682c2008c4dd7ddb6df1f 100644 (file)
--- a/main.tex
+++ b/main.tex
@@ -108,7 +108,7 @@ the classical statistical tests.
 \section{Introduction}
 \input{intro}
 
- \section{\uppercase{Preliminaries}}\label{sec:preliminaries}
+\section{Preliminaries}\label{sec:preliminaries}
 \input{preliminaries}
 
 \section{Proof Of Chaos}\label{sec:proofOfChaos}
@@ -117,6 +117,10 @@ the classical statistical tests.
 \section{Functions with Strongly Connected $\Gamma_{\{b\}}(f)$}\label{sec:SCCfunc}
 \input{generating}
 
+\section{(Locally) Balanced Hamiltonian Cycle}\label{sec:hamilton}
+\input{hamilton}
+
+
 \section{Stopping Time}\label{sec:hypercube}
 \input{stopping}