OPTmonth = {},
}
-@inproceedings{chgw14oip,
-inhal = {no},
-domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO, INFO:INFO_SE},
-equipe = {ie},
-classement = {COM},
-author = {Couchot, Jean-Fran\c{c}ois and H\'eam, Pierre-Cyrille and Guyeux, Christophe and Wang, Qianxue and Bahi, Jacques},
-title = {Pseudorandom Number Generators with Balanced Gray Codes},
-booktitle = {Secrypt 2014, 11th Int. Conf. on Security and Cryptography},
-pages = {469--475},
-address = {Vienna, Austria},
-month = aug,
-date = {28-30 aout},
-year = 2014,
-note = {Position short paper},
-
-}
@Misc{GridComp,
OPTkey = {},
pages = "267--272",
URL = "http://dx.doi.org/10.1016/j.ipl.2008.10.015",
}
+
@inproceedings{DBLP:conf/secrypt/CouchotHGWB14,
author = {Jean{-}Fran{\c{c}}ois Couchot and
Pierre{-}Cyrille H{\'{e}}am and
and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected.
\end{proof}
-The next section shows how to generate functions and a iteration number $b$
+The next section recalls a general scheme to produce
+functions and a iteration number $b$
such that $\Gamma_{\{b\}}$ is strongly connected.
acc = acc + 2**(n-i-1)
return acc
-"""
+
def MarkovMatrixUnPas(fbin,n,p2n,lp2nm1):
MM = np.zeros(p2n*p2n).reshape((p2n,p2n))
# diagonal
ipb =[_ for _ in ib]
ipb[j] = image[j]
MM[i, dec(ipb,n)] +=float(1)/(2*n)
+ print MM
return MM
-"""
+"""
def MarkovMatrixUnPas(fbin,n,p2n,lp2nm1):
MM = np.zeros(p2n*p2n).reshape((p2n,p2n))
# diagonal
return MM
-
-
+"""
+"""
# f is the binary function
# b is the number to iterate
xp[st] = image[st]
#print "xp ",xp
return xp
-
+"""
## n'est pas un circuit hmiltonien
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],[29, 22, 21, 30, 19, 27, 24, 28, 7, 20, 5, 4, 23, 26, 25, 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 1, 6, 11, 18, 0,16]] # essai des 2 elements à 5
-
-
+#lf+=[[29, 22, 21, 24, 31, 30, 27, 26, 7, 23, 5, 28, 3, 19, 25, 17, 13, 12, 9, 8, 15, 2, 1, 10, 6, 14, 4, 20, 11, 18, 0, 16]]
+#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],[29, 22, 21, 30, 19, 27, 24, 28, 7, 20, 5, 4, 23, 26, 25, 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 1, 6, 11, 18, 0,16]] # essai des 2 elements a 5
+lf +=[
+ [29, 22, 21, 30, 19, 27, 24, 28, 7, 20, 5, 4, 23, 26, 25, 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 1, 6, 11, 18, 0, 16],#sylvain 1
+ [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],#sylvain 2
+ [29, 22, 21, 24, 31, 30, 27, 26, 7, 23, 5, 28, 3, 19, 25, 17, 13, 12, 9, 8, 15, 2, 1, 10, 6, 14, 4, 20, 11, 18, 0, 16], #mini avec 7
+ [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
+
-#f += [[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 += [[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
for f in lf:
- dev = 1E-8
+ dev = 1E-12
n,cpt1,cpt2 = traite_f(f)
print f, n,cpt1,cpt2
print 8*n*n + 4*n*log(n+1)#,8*n*n + (n+2)*(log(n)+2)
acc = acc + 2**(n-i-1)
return acc
-
+"""
def MarkovMatrixUnPas(fbin,n,p2n,lp2nm1):
print p2n
MM = np.zeros((p2n,p2n))
MM[i, dec(ipb,n)] +=float(1)/(2**n)
return MM
-"""
+
#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, 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
+#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
+lf +=[
+ [29, 22, 21, 30, 19, 27, 24, 28, 7, 20, 5, 4, 23, 26, 25, 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 1, 6, 11, 18, 0, 16],#sylvain 1
+ [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],#sylvain 2
+ [29, 22, 21, 24, 31, 30, 27, 26, 7, 23, 5, 28, 3, 19, 25, 17, 13, 12, 9, 8, 15, 2, 1, 10, 6, 14, 4, 20, 11, 18, 0, 16], #mini avec 7
+ [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
# 14 = (1,1,1,0) = f(0,0,0,0)
-This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2015/dev/Debian) (preloaded format=pdflatex 2015.4.24) 1 SEP 2015 14:12
+This is pdfTeX, Version 3.14159265-2.6-1.40.16 (TeX Live 2015/Debian) (preloaded format=pdflatex 2016.5.31) 20 JUN 2016 22:12
entering extended mode
restricted \write18 enabled.
%&-line parsing enabled.
-**president.tex
+**main.tex
! Emergency stop.
-<*> president.tex
-
+<*> main.tex
+
End of file on the terminal!
Here is how much of TeX's memory you used:
- 3 strings out of 494991
- 118 string characters out of 6180055
- 46069 words of memory out of 5000000
- 3329 multiletter control sequences out of 15000+600000
+ 3 strings out of 494924
+ 106 string characters out of 6179708
+ 45807 words of memory out of 5000000
+ 3399 multiletter control sequences out of 15000+600000
3640 words of font info for 14 fonts, out of 8000000 for 9000
14 hyphenation exceptions out of 8191
0i,0n,0p,1b,6s stack positions out of 5000i,500n,10000p,200000b,80000s
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.
-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.
There exists thus $b$ such there is an arc between any $x$ and $y$.
\end{proof}
-The next section presents how to build hamiltonian cycles in the
+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}-}$ for a $\mathsf{N}$-length cycle.
+
+%%%%%%%%%%%%%%%%%%%%%
+
+The function that is built
+from the
+
+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.
The current context is to provide a function
$f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing a Hamiltonian
cycle in the $\mathsf{N}$ cube. Such a function is going to be iterated
-$b$ time to produce a pseudo random number, \textit{i.e.} a vertex in the
+$b$ times to produce a pseudo random number,
+\textit{i.e.} a vertex in the
$\mathsf{N}$ cube.
Obviously, the number of iterations $b$ has to be sufficiently large
to provide a uniform output distribution.
-To reduced the number of iterations, the provided Gray code
+To reduce the number of iterations, the provided Gray code
should ideally possess the both balanced and locally balanced properties.
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,
\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
+and~\cite{ZanSup04} have addressed the problem 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.
+where the authors have explicitly 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
+algorithm. There rigorous 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.
$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
+s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, \dots , 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}$
+\item\label{item:u'}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
+\item\label{item:VW} 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}
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.
+Next section shows how to choose the sequence $l$ to have the balance property.
\subsection{Balanced Codes}
-Let us first recall how to formalize the balancy property of a Gray code.
+Let us first recall how to formalize the balance 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
\begin{thrm}\label{prop:balanced}
-Let $\mathsf{N}$ in $\Nats$, and $a_{\mathsf{N}}$ be defined by
+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$.
There exists then a sequence $l$ in
step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm
-The proof is done by induction on $\mathsf{N}$. Let us imadialty verify
+The proof is done by induction on $\mathsf{N}$. Let us immediately verify
that it is established for both odd and even smallest values, \textit{i.e.}
$3$ and $4$.
For the initial case where $\mathsf{N}=3$, \textit{i.e.} $\mathsf{N-2}=1$ we successively have: $S_1=1,1$, $l=2$, $u_0 = \emptyset$, and $v=\emptyset$.
For the inductive case, let us first define some variables.
Let $c_{\mathsf{N}}$ (resp. $d_{\mathsf{N}}$) be the number of elements
-whose transistion count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
+whose transition count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
These two variables are defined by the system
$$
\qquad
\left\{
\begin{array}{lcl}
-d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -n.a_{\mathsf{N}}}{2} \\
+d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -\mathsf{N}.a_{\mathsf{N}}}{2} \\
c_{\mathsf{N}} &= &\mathsf{N} - d_{\mathsf{N}}
\end{array}
\right.
$$
-Since $a_{\mathsf{N}$ is even, $d_{\mathsf{N}}$ is defined.
-Moreover, both $c_{\mathsf{N}}$ and $d_{\mathsf{N}}$ are obviously positves.
+Since $a_{\mathsf{N}}$ is even, $d_{\mathsf{N}}$ is an integer.
+Let us first proove that both $c_{\mathsf{N}}$ and $d_{\mathsf{N}}$ are positive
+integers.
+Let $q_{\mathsf{N}}$ and $r_{\mathsf{N}}$, respectively, be
+the quotient and the remainder in the Euclidean disvision
+of $2^{\mathsf{N}}$ by $2\mathsf{N}$, \textit{i.e.}
+$2^{\mathsf{N}} = q_{\mathsf{N}}.2\mathsf{N} + r_{\mathsf{N}}$, with $0 \le r_{\mathsf{N}} <2\mathsf{N}$.
+First of all, the integer $r$ is even since $r_{\mathsf{N}} = 2^{\mathsf{N}} - q_{\mathsf{N}}.2\mathsf{N}= 2(2^{\mathsf{N}-1} - q_{\mathsf{N}}.\mathsf{N})$.
+Next, $a_{\mathsf{N}}$ is $\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}$. Consequently
+$d_{\mathsf{N}}$ is $r_{\mathsf{N}}/2$ and is thus a positive integer s.t.
+$0 \le d_{\mathsf{N}} <\mathsf{N}$.
+The proof for $c_{\mathsf{N}}$ is obvious.
+For any $i$, $1 \le i \le \mathsf{N}$, let $zi_{\mathsf{N}}$ (resp. $ti_{\mathsf{N}}$ and $bi_{\mathsf{N}}$)
+be the occurence number of element $i$ in the sequence $u_0, \dots, u_{l-2}$
+(resp. in the sequences $s_{i_1}, \dots , s_{i_l}$ and $v$)
+in step (\ref{item:nondet}) of the algorithm.
+
+Due to the definition of $u'$ in step~(\ref{item:u'}),
+$3.zi_{\mathsf{N}} + ti_{\mathsf{N}}$ is the
+ number of element $i$ in the sequence $U$.
+It is clear that the number of element $i$ in the sequence $V$ is
+$2bi_{\mathsf{N}}$ due to step (\ref{item:VW}).
+We thus have the following system:
+$$
+\left\{
+\begin{array}{lcl}
+3.zi_{\mathsf{N}} + ti_{\mathsf{N}} + 2.bi_{\mathsf{N}} + \textit{TC}_{\mathsf{N}-2}(i) &= &\textit{TC}_{\mathsf{N}}(i) \\
+zi_{\mathsf{N}} + ti_{\mathsf{N}} + bi_{\mathsf{N}} & =& \textit{TC}_{\mathsf{N}-2}(i)
+\end{array}
+\right.
+\qquad
+\Leftrightarrow
+$$
+
+\begin{equation}
+\left\{
+\begin{array}{lcl}
+zi_{\mathsf{N}} &= &
+\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) - bi_{\mathsf{N}}}{2}\\
+ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}-bi_{\mathsf{N}}
+\end{array}
+\right.
+\label{eq:sys:zt1}
+\end{equation}
+
+In this set of 2 equations with 3 unknown variables, let $b_i$ be set with 0.
+In this case, since $\textit{TC}_{\mathsf{N}}$ is even (equal to $a_{\mathsf{N}}$
+or to $a_{\mathsf{N}}+2$), the variable $zi_{\mathsf{N}}$ is thus an integer.
+Let us now prove that the resulting system has always positive integer
+solutions $z_i$, $t_i$, $0 \le z_i, t_i \le \textit{TC}_{\mathsf{N}-2}(i)$
+and s.t. their sum is equal to $\textit{TC}_{\mathsf{N}-2}(i)$.
+This latter consraint is obviously established if the system has a solution.
+We thus have the following system.
+
+
+
+\begin{equation}
+\left\{
+\begin{array}{lcl}
+zi_{\mathsf{N}} &= &
+\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) }{2}\\
+ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}
+\end{array}
+\right.
+\label{eq:sys:zt2}
+\end{equation}
+
+The definition of $\textit{TC}_{\mathsf{N}}(i)$ depends on the value of $\mathsf{N}$.
+When $3 \le N \le 7$, values are defined as follows:
+\begin{eqnarray*}
+\textit{TC}_{3} & = & [2,2,4] \\
+\textit{TC}_{5} & = & [6,6,8,6,6] \\
+\textit{TC}_{7} & = & [18,18,20,18,18,18,18] \\
+\\
+\textit{TC}_{4} & = & [4,4,4,4] \\
+\textit{TC}_{6} & = & [10,10,10,10,12,12] \\
+\end{eqnarray*}
+It is not hard to verify that all these instanciations verify the aformentioned contraints.
+
+When $N \ge 8$, $\textit{TC}_{\mathsf{N}}(i)$ is defined as follows:
+\begin{equation}
+\textit{TC}_{\mathsf{N}}(i) = \left\{
+\begin{array}{l}
+a_{\mathsf{N}} \textrm{ if } 1 \le i \le c_{\mathsf{N}} \\
+a_{\mathsf{N}}+2 \textrm{ if } c_{\mathsf{N}} +1 \le i \le c_{\mathsf{N}} + d_{\mathsf{N}}
+\end{array}
+\right.
+\label{eq:TCN:def}
+\end{equation}
+
+
+We thus have
+$$
+\begin{array}{rcl}
+\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)
+&\ge&
+a_{\mathsf{N}} - 2(a_{\mathsf{N}-2}+2) \\
+&\ge&
+\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}
+-2 \left( \frac{2^{\mathsf{N-2}}-r_{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
+&\ge&
+\frac{2^{\mathsf{N}}-2N}{\mathsf{N}}
+-2 \left( \frac{2^{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
+&\ge&
+\dfrac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\
+\end{array}
+$$
+
+A simple variation study of the function $t:\R \rightarrow \R$ such that
+$x \mapsto t(x) = (x -2).2^{x}-2x.2^{x-2}-6x(x-2)$ shows that
+its derivative is strictly postive if $x \ge 6$ and $t(8)=224$.
+The integer $\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)$ is thus positive
+for any $\mathsf{N} \ge 8$ and the proof is established.
+
+
+% \begin{table}[ht]
+% $$
+% \begin{array}{|l|l|l|l|l|l|}
+% \hline
+% \mathsf{N} & 3 & 4 & 5 & 6 & 7\\
+% \hline
+% a_{\mathsf{N}} & 2 & 4 & 6 & 10 & 18\\
+% \hline
+% \end{array}
+% $$
+% \label{tab:an}
+% \caption{First values of $a_{\mathsf{N}}$}
+% \end{table}
+
+For each element $i$, we are then left to choose $zi_{\mathsf{N}}$ positions
+among $\textit{TC}_{\mathsf{N}}(i)$, which leads to
+${\textit{TC}_{\mathsf{N}}(i) \choose zi_{\mathsf{N}} }$ possibilities.
+Notice that all such choices lead to a hamiltonian path.
+
-\subsection{Toward a local uniform distribution of switches}
-The exploitation of chaotic systems to generate pseudorandom sequences is
-an hot topic~\cite{915396,915385,5376454}. Such systems are fundamentally
-chosen due to their unpredictable character and their sensitiveness to initial conditions.
-In most cases, these generators simply consist in iterating a chaotic function like
-the logistic map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots
-It thus remains to find optimal parameters in such functions so that attractors are
-avoided, hoping by doing so that the generated numbers follow a uniform distribution.
-In order to check the quality of the produced outputs, it is usual to test the
-PRNGs (Pseudo-Random Number Generators) with statistical batteries like
-the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite{LEcuyerS07} ones.
+The exploitation of chaotic systems to generate pseudorandom sequences
+is an hot topic~\cite{915396,915385,5376454}. Such systems are
+fundamentally chosen due to their unpredictable character and their
+sensitiveness to initial conditions. In most cases, these generators
+simply consist in iterating a chaotic function like the logistic
+map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots It
+thus remains to find optimal parameters in such functions so that
+attractors are avoided, hoping by doing so that the generated numbers
+follow a uniform distribution. In order to check the quality of the
+produced outputs, it is usual to test the PRNGs (Pseudo-Random Number
+Generators) with statistical batteries like the so-called
+DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or
+TestU01~\cite{LEcuyerS07} ones.
-In its general understanding, chaos notion is often reduced to the strong
-sensitiveness to the initial conditions (the well known ``butterfly effect''):
-a continuous function $k$ defined on a metrical space is said
-\emph{strongly sensitive to the initial conditions} if for each point
-$x$ and each positive value $\epsilon$, it is possible to find another
-point $y$ as close as possible to $x$, and an integer $t$ such that the distance
-between the $t$-th iterates of $x$ and $y$, denoted by $k^t(x)$ and $k^t(y)$,
-are larger than $\epsilon$. However, in his definition of chaos, Devaney~\cite{Devaney}
-imposes to the chaotic function two other properties called
-\emph{transitivity} and \emph{regularity}. Functions evoked above have
-been studied according to these properties, and they have been proven as chaotic on $\R$.
-But nothing guarantees that such properties are preserved when iterating the functions
-on floating point numbers, which is the domain of interpretation of real numbers $\R$ on
-machines.
+In its general understanding, chaos notion is often reduced to the
+strong sensitiveness to the initial conditions (the well known
+``butterfly effect''): a continuous function $k$ defined on a metrical
+space is said \emph{strongly sensitive to the initial conditions} if
+for each point $x$ and each positive value $\epsilon$, it is possible
+to find another point $y$ as close as possible to $x$, and an integer
+$t$ such that the distance between the $t$-th iterates of $x$ and $y$,
+denoted by $k^t(x)$ and $k^t(y)$, are larger than $\epsilon$. However,
+in his definition of chaos, Devaney~\cite{Devaney} imposes to the
+chaotic function two other properties called \emph{transitivity} and
+\emph{regularity}. Functions evoked above have been studied according
+to these properties, and they have been proven as chaotic on $\R$.
+But nothing guarantees that such properties are preserved when
+iterating the functions on floating point numbers, which is the domain
+of interpretation of real numbers $\R$ on machines.
-To avoid this lack of chaos, we have previously presented some PRNGs that iterate
-continuous functions $G_f$ on a discrete domain $\{ 1, \ldots, n \}^{\Nats}
- \times \{0,1\}^n$, where $f$ is a Boolean function (\textit{i.e.}, $f :
- \{0,1\}^n \rightarrow \{0,1\}^n$). These generators are
-$\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11:ip},
-$\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip} and
-$\chi_{\textit{14Secrypt}}$ \cite{chgw14oip} where \textit{CI} means
-\emph{Chaotic Iterations}.
-We have firstly proven in~\cite{bcgr11:ip} that, to establish the chaotic nature
-of algorithm $\textit{CIPRNG}_f^1$, it is necessary and sufficient that the
-asynchronous iterations are strongly connected. We then have proven that it is necessary
-and sufficient that the Markov matrix associated to this graph is doubly stochastic,
-in order to have a uniform distribution of the outputs. We have finally established
-sufficient conditions to guarantee the first property of connectivity. Among the
-generated functions, we thus have considered for further investigations only the ones that
-satisfy the second property too. In~\cite{chgw14oip}, we have proposed an algorithmic
-method allowing to directly obtain a strongly connected iteration graph having a doubly
-stochastic Markov matrix.
+To avoid this lack of chaos, we have previously presented some PRNGs
+that iterate continuous functions $G_f$ on a discrete domain $\{ 1,
+\ldots, n \}^{\Nats} \times \{0,1\}^n$, where $f$ is a Boolean
+function (\textit{i.e.}, $f : \{0,1\}^{\mathsf{N}}
+\rightarrow \{0,1\}^{\mathsf{N}}$).
+These generators are $\textit{CIPRNG}_f^1(u)$
+\cite{guyeuxTaiwan10,bcgr11:ip}, $\textit{CIPRNG}_f^2(u,v)$
+\cite{wbg10ip} and $\chi_{\textit{14Secrypt}}$
+\cite{DBLP:conf/secrypt/CouchotHGWB14} where \textit{CI} means
+\emph{Chaotic Iterations}. We have firstly proven in~\cite{bcgr11:ip}
+that, to establish the chaotic nature of algorithm
+$\textit{CIPRNG}_f^1$, it is necessary and sufficient that the
+asynchronous iterations are strongly connected. We then have proven
+that it is necessary and sufficient that the Markov matrix associated
+to this graph is doubly stochastic, in order to have a uniform
+distribution of the outputs. We have finally established sufficient
+conditions to guarantee the first property of connectivity. Among the
+generated functions, we thus have considered for further
+investigations only the ones that satisfy the second property
+too.
+However, it cannot be directly deduced that
+$\chi_{\textit{14Secrypt}}$ is chaotic since we do not output all the
+successive values of iterating $G_f$. This algorithm only displays a
+subsequence $x^{b.n}$ of a whole chaotic sequence $x^{n}$ and it is
+indeed not correct that the chaos property is preserved for any
+subsequence of a chaotic sequence. This article presents conditions
+to preserve this property.
-However, it cannot be directly deduced
-that $\chi_{\textit{14Secrypt}}$ is chaotic
-since we do not output all the successive
-values of iterating $F_f$.
-This algorithm only displays a
-subsequence $x^{b.n}$ of a whole chaotic sequence $x^{n}$ and
-it is indeed definitively false that the chaos property is
-preserved for any subsequence of a chaotic sequence.
-This article presents conditions to preserve this property.
-An approach to generate a large class of chaotic functions has
-been presented in~\cite{chgw14oip}.
-It is basically fourfold:
-first build a $\mathsf{N}$-cube, next remove an Hamiltonian cycle, further add self-loop
-on each vertex and finally, translate this into a Boolean map.
-We are then left to check whether this approach proposes maps with the required conditions
-for the chaos.
-The answer is indeed positive. The pseudorandom number generation can thus be seen as a
-random walk in a $\mathsf{N}$-cube without a Hamiltonian cycle.
+Finding a Boolean function which provides a strongly connected
+iteration graph having a doubly stochastic Markov matrix is however
+not an easy task.
+We have firstly proposed in~\cite{bcgr11:ip} a generate-and-test based
+approach that solves this issue. However, this one was not efficient enough.
+Thus, a second scheme has been further presented
+in~\cite{DBLP:conf/secrypt/CouchotHGWB14} by remarking that
+a $\mathsf{N}$-cube where an Hamiltonian cycle (or equivalently a Gray code)
+has been removed is strongly connected and has
+a doubly stochastic Markov matrix.
-In the PRNG context, there remains to find which subsequence
-is theoretically and practically
-sufficient to extract.
-A uniform distribution is indeed awaited and this
-cannot be obtained in a walk in the hypercube
-with paths of short length $b$.
-However, the higher
-is $b$ the slower is the
-algorithm to generate pseudorandom
-numbers.
-The time until the
-corresponding Markov chain is close
-to the uniform distribution is a metric
-that should be theoretically and practically studied.
-Finally, the ability of the approach to face classical
-tests suite has to be evaluated.
+However, the removed Hamiltonian cycle
+has a great influence in the quality of the output.
+For instance, if this one one is not balanced (\textit{i.e.},
+the number of changes in different bits are completely different),
+some bits would be hard to switch.
+This article shows an effective algorithm that efficiently
+implements the previous scheme and provides thus functions issued
+from removing in the $\mathsf{N}$-cube a \emph{balanced} Hamiltonian cycle.
+The length $b$ of the walk to reach a
+distribution close to the uniform one would be dramatically long.
+This article theoretically and practically
+studies the length $b$ until the corresponding Markov
+chain is close to the uniform distribution.
+Finally, the ability of the approach to face classical tests
+suite is evaluated.
-%A upper bound of this time quadratic in the number of
-%generated bits.
-The remainder of this article is organized as follows. The next section is devoted to
-preliminaries, basic notations, and terminologies regarding Boolean map iterations.
-Then, in Section~\ref{sec:proofOfChaos}, Devaney's definition of chaos is recalled
-while the proofs of chaos of our most general PRNGs is provided.
-This is the first major contribution.
-Section~\ref{sec:SCCfunc} shows how to generate functions with required properties
-making the PRNG chaotic.
-The next section (Sect.~\ref{sec:hypercube}) defines the theoretical framework
-to study the stopping-time, \textit{i.e.}, time until reaching
-a uniform distribution.
-This is the second major contribution.
-The Section~\ref{sec:prng} gives practical results on evaluating the PRNG against the NIST suite.
-This research work ends by a conclusion section, where the contribution is summarized and
-intended future work is outlined.
+
+The remainder of this article is organized as follows. The next
+section is devoted to preliminaries, basic notations, and
+terminologies regarding Boolean map iterations. Then, in
+Section~\ref{sec:proofOfChaos}, Devaney's definition of chaos is
+recalled while the proofs of chaos of our most general PRNGs is
+provided. This is the first major contribution.
+Section~\ref{sec:SCCfunc} recalls a general scheme
+to obtain functions with awaited behavior. Main theorems are recalled
+to make the document self-content.
+The next section (Sect.~\ref{sec:hamilton}) presents an algorithm that
+implements this scheme and proves it always produces a solution.
+This is the second major contribution
+The later section
+(Sect.~\ref{sec:hypercube}) defines the theoretical framework to study
+the mixing-time, \textit{i.e.}, time until reaching a uniform
+distribution. It proves that this one is at worth quadratic in the number
+of elements. Experiments show that the bound is practically largely much
+lower. This is the third major contribution. The
+Section~\ref{sec:prng} gives practical results on evaluating the PRNG
+against the NIST suite. This research work ends by a conclusion
+section, where the contribution is summarized and intended future work
+is outlined.
+++ /dev/null
-\relax
-\citation{915396,915385,5376454}
-\citation{915396,915385}
-\citation{5376454}
-\citation{Marsaglia1996}
-\citation{Nist10}
-\citation{LEcuyerS07}
-\citation{Devaney}
-\select@language{english}
-\@writefile{toc}{\select@language{english}}
-\@writefile{lof}{\select@language{english}}
-\@writefile{lot}{\select@language{english}}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{1}{Introduction}}{1}}
-\citation{guyeuxTaiwan10,bcgr11:ip}
-\citation{wbg10ip}
-\citation{chgw14oip}
-\citation{bcgr11:ip}
-\citation{chgw14oip}
-\citation{chgw14oip}
-\citation{DBLP:conf/secrypt/CouchotHGWB14}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{2}{Preliminaries}}{3}}
-\newlabel{sec:preliminaries}{{2}{3}}
-\newlabel{eq:asyn}{{1}{3}}
-\citation{bcgr11:ip}
-\citation{bcgr11:ip}
-\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Iteration Graph $\Gamma (f^*)$ of the function $f^*$\relax }}{4}}
-\providecommand*\caption@xref[2]{\@setref\relax\@undefined{#1}}
-\newlabel{fig:iteration:f*}{{1}{4}}
-\@writefile{loa}{\contentsline {algocf}{\numberline {1}{\ignorespaces Pseudo Code of the $\chi _{\textit {14Secrypt}}$ PRNG\relax }}{4}}
-\newlabel{CI Algorithm}{{1}{4}}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{3}{Proof Of Chaos}}{4}}
-\newlabel{sec:proofOfChaos}{{3}{4}}
-\citation{Devaney}
-\citation{Banks92}
-\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{3.1}{Devaney's Chaotic Dynamical Systems}}{5}}
-\newlabel{subsec:Devaney}{{3.1}{5}}
-\newlabel{sensitivity}{{3.5}{5}}
-\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{3.2}{A Metric Space for PRNG Iterations}}{5}}
-\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{3.3}{A metric on $\mathcal {X}_{\mathsf {N},\mathcal {P}}$}}{6}}
-\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{3.4}{$\Gamma _{\mathcal {P}}(f)$ as an extension of $\Gamma (f)$}}{8}}
-\newlabel{graphe1}{{2a}{9}}
-\newlabel{sub@graphe1}{{a}{9}}
-\newlabel{graphe2}{{2b}{9}}
-\newlabel{sub@graphe2}{{b}{9}}
-\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Iterating $f_0:(x_1,x_2) \DOTSB \mapstochar \rightarrow (\overline {x_1}, \overline {x_2})$\relax }}{9}}
-\newlabel{fig:itg}{{2}{9}}
-\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{3.5}{Proofs of chaos}}{9}}
-\newlabel{prop:trans}{{3.8}{9}}
-\citation{bcgr11:ip}
-\citation{DBLP:conf/secrypt/CouchotHGWB14}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{4}{Functions with Strongly Connected $\Gamma _{\{b\}}(f)$}}{10}}
-\newlabel{sec:SCCfunc}{{4}{10}}
-\citation{bcgr11:ip}
-\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}}
-\citation{LevinPeresWilmer2006}
-\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{5.3}{Toward a local uniform distribution of switches}}{14}}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{6}{Stopping Time}}{14}}
-\newlabel{sec:hypercube}{{6}{14}}
-\newlabel{thm-sst}{{6.1}{15}}
-\newlabel{eq:Markov:rairo}{{3}{15}}
-\newlabel{lm:h}{{6.2}{16}}
-\newlabel{prop:stop}{{6.4}{16}}
-\newlabel{prop:lambda}{{6.5}{16}}
-\citation{proba}
-\newlabel{lm:stopprime}{{6.6}{17}}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{7}{Experiments}}{18}}
-\newlabel{sec:prng}{{7}{18}}
-\@writefile{loa}{\contentsline {algocf}{\numberline {2}{\ignorespaces Pseudo Code of the $\chi _{\textit {15Rairo}}$ PRNG\relax }}{18}}
-\newlabel{CI Algorithm:2}{{2}{18}}
-\@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}
-\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Functions with DSCC Matrix and smallest MT\relax }}{20}}
-\newlabel{table:nc}{{1}{20}}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{}{References}}{20}}
-\bibcite{Bykov2016}{Byk16}
-\bibcite{chgw14oip}{CHG{$^{+}$}14a}
-\bibcite{DBLP:conf/secrypt/CouchotHGWB14}{CHG{$^{+}$}14b}
-\bibcite{5376454}{CMZ09}
-\bibcite{Devaney}{Dev89}
-\bibcite{guyeuxTaiwan10}{GWB10}
-\bibcite{LevinPeresWilmer2006}{LPW06}
-\bibcite{LEcuyerS07}{LS07}
-\bibcite{Marsaglia1996}{Mar96}
-\bibcite{proba}{MU05}
-\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces NIST SP 800-22 test results ($\mathbb {P}_T$)\relax }}{21}}
-\newlabel{The passing rate}{{2}{21}}
-\bibcite{Robinson:1981:CS}{RC81}
-\bibcite{915385}{SK01}
-\bibcite{915396}{SPK01}
-\bibcite{ZanSup04}{SZ04}
-\bibcite{wbg10ip}{WBGF10}
-\newlabel{tocindent-1}{0pt}
-\newlabel{tocindent0}{12.77466pt}
-\newlabel{tocindent1}{17.77344pt}
-\newlabel{tocindent2}{25.54932pt}
-\newlabel{tocindent3}{0pt}
\newcommand{\etalchar}[1]{$^{#1}$}
-\begin{thebibliography}{CHG{\etalchar{+}}14b}
+\begin{thebibliography}{WBGF10}
\bibitem[BBCS92]{Banks92}
J.~Banks, J.~Brooks, G.~Cairns, and P.~Stacey.
\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.
-\newblock Pseudorandom number generators with balanced gray codes.
-\newblock In {\em Secrypt 2014, 11th Int. Conf. on Security and Cryptography},
- pages 469--475, Vienna, Austria, August 2014.
-\newblock Position short paper.
-
-\bibitem[CHG{\etalchar{+}}14b]{DBLP:conf/secrypt/CouchotHGWB14}
+\bibitem[CHG{\etalchar{+}}14]{DBLP:conf/secrypt/CouchotHGWB14}
Jean{-}Fran{\c{c}}ois Couchot, Pierre{-}Cyrille H{\'{e}}am, Christophe Guyeux,
Qianxue Wang, and Jacques~M. Bahi.
\newblock Pseudorandom number generators with balanced gray codes.
+++ /dev/null
-This is BibTeX, Version 0.99d (TeX Live 2013/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 19 entries,
- 2543 wiz_defined-function locations,
- 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$ -- 21
-newline$ -- 100
-num.names$ -- 59
-pop$ -- 119
-preamble$ -- 1
-purify$ -- 146
-quote$ -- 0
-skip$ -- 299
-stack$ -- 0
-substring$ -- 463
-swap$ -- 80
-text.length$ -- 12
-text.prefix$ -- 3
-top$ -- 0
-type$ -- 140
-warning$ -- 0
-while$ -- 80
-width$ -- 21
-write$ -- 259
+++ /dev/null
-This is pdfTeX, Version 3.1415926-2.5-1.40.14 (TeX Live 2013/Debian) (format=pdflatex 2014.6.13) 22 JUN 2016 14:44
-entering extended mode
- restricted \write18 enabled.
- %&-line parsing enabled.
-**main.tex
-(./main.tex
-LaTeX2e <2011/06/27>
-Babel <3.9h> and hyphenation patterns for 78 languages loaded.
-(./ita.cls
-Document Class: ita 1999/03/01 v1.1 EDP-Sciences
-(/usr/share/texlive/texmf-dist/tex/latex/amscls/amsart.cls
-Document Class: amsart 2009/07/02 v2.20.1
-\linespacing=\dimen102
-\normalparindent=\dimen103
-\normaltopskip=\skip41
-(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsmath.sty
-Package: amsmath 2013/01/14 v2.14 AMS math features
-\@mathmargin=\skip42
-
-For additional information on amsmath, use the `?' option.
-(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amstext.sty
-Package: amstext 2000/06/29 v2.01
-
-(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsgen.sty
-File: amsgen.sty 1999/11/30 v2.0
-\@emptytoks=\toks14
-\ex@=\dimen104
-))
-(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsbsy.sty
-Package: amsbsy 1999/11/29 v1.2d
-\pmbraise@=\dimen105
-)
-(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsopn.sty
-Package: amsopn 1999/12/14 v2.01 operator names
-)
-\inf@bad=\count79
-LaTeX Info: Redefining \frac on input line 210.
-\uproot@=\count80
-\leftroot@=\count81
-LaTeX Info: Redefining \overline on input line 306.
-\classnum@=\count82
-\DOTSCASE@=\count83
-LaTeX Info: Redefining \ldots on input line 378.
-LaTeX Info: Redefining \dots on input line 381.
-LaTeX Info: Redefining \cdots on input line 466.
-\Mathstrutbox@=\box26
-\strutbox@=\box27
-\big@size=\dimen106
-LaTeX Font Info: Redeclaring font encoding OML on input line 566.
-LaTeX Font Info: Redeclaring font encoding OMS on input line 567.
-\macc@depth=\count84
-\c@MaxMatrixCols=\count85
-\dotsspace@=\muskip10
-\c@parentequation=\count86
-\dspbrk@lvl=\count87
-\tag@help=\toks15
-\row@=\count88
-\column@=\count89
-\maxfields@=\count90
-\andhelp@=\toks16
-\eqnshift@=\dimen107
-\alignsep@=\dimen108
-\tagshift@=\dimen109
-\tagwidth@=\dimen110
-\totwidth@=\dimen111
-\lineht@=\dimen112
-\@envbody=\toks17
-\multlinegap=\skip43
-\multlinetaggap=\skip44
-\mathdisplay@stack=\toks18
-LaTeX Info: Redefining \[ on input line 2665.
-LaTeX Info: Redefining \] on input line 2666.
-)
-LaTeX Font Info: Try loading font information for U+msa on input line 388.
-
-(/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsa.fd
-File: umsa.fd 2013/01/14 v3.01 AMS symbols A
-)
-(/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amsfonts.sty
-Package: amsfonts 2013/01/14 v3.01 Basic AMSFonts support
-\symAMSa=\mathgroup4
-\symAMSb=\mathgroup5
-LaTeX Font Info: Overwriting math alphabet `\mathfrak' in version `bold'
-(Font) U/euf/m/n --> U/euf/b/n on input line 106.
-)
-\copyins=\insert233
-\abstractbox=\box28
-\listisep=\skip45
-\c@part=\count91
-\c@section=\count92
-\c@subsection=\count93
-\c@subsubsection=\count94
-\c@paragraph=\count95
-\c@subparagraph=\count96
-\c@figure=\count97
-\c@table=\count98
-\abovecaptionskip=\skip46
-\belowcaptionskip=\skip47
-\captionindent=\dimen113
-\thm@style=\toks19
-\thm@bodyfont=\toks20
-\thm@headfont=\toks21
-\thm@notefont=\toks22
-\thm@headpunct=\toks23
-\thm@preskip=\skip48
-\thm@postskip=\skip49
-\thm@headsep=\skip50
-\dth@everypar=\toks24
-)
-(/usr/share/texlive/texmf-dist/tex/latex/cite/cite.sty
-LaTeX Info: Redefining \cite on input line 302.
-LaTeX Info: Redefining \nocite on input line 373.
-Package: cite 2010/09/10 v 5.3
-)
-\@b@rnngttl=\box29
-\@b@rnngthr=\box30
-\@c@thr@=\count99
-\@y=\count100
-\@x=\count101
-\@b@kwrds=\box31
-\resumebox=\box32
-\abstractbox=\box33
-\@c@ddrss@=\count102
-\@b@ddrss@=\box34
-\@c@thnks@=\count103
-\@b@thnks@=\box35
-\c@thrm=\count104
-)
-(/usr/share/texlive/texmf-dist/tex/latex/graphics/graphicx.sty
-Package: graphicx 1999/02/16 v1.0f Enhanced LaTeX Graphics (DPC,SPQR)
-
-(/usr/share/texlive/texmf-dist/tex/latex/graphics/keyval.sty
-Package: keyval 1999/03/16 v1.13 key=value parser (DPC)
-\KV@toks@=\toks25
-)
-(/usr/share/texlive/texmf-dist/tex/latex/graphics/graphics.sty
-Package: graphics 2009/02/05 v1.0o Standard LaTeX Graphics (DPC,SPQR)
-
-(/usr/share/texlive/texmf-dist/tex/latex/graphics/trig.sty
-Package: trig 1999/03/16 v1.09 sin cos tan (DPC)
-)
-(/usr/share/texlive/texmf-dist/tex/latex/latexconfig/graphics.cfg
-File: graphics.cfg 2010/04/23 v1.9 graphics configuration of TeX Live
-)
-Package graphics Info: Driver file: pdftex.def on input line 91.
-
-(/usr/share/texlive/texmf-dist/tex/latex/pdftex-def/pdftex.def
-File: pdftex.def 2011/05/27 v0.06d Graphics/color for pdfTeX
-
-(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/infwarerr.sty
-Package: infwarerr 2010/04/08 v1.3 Providing info/warning/error messages (HO)
-)
-(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/ltxcmds.sty
-Package: ltxcmds 2011/11/09 v1.22 LaTeX kernel commands for general use (HO)
-)
-\Gread@gobject=\count105
-))
-\Gin@req@height=\dimen114
-\Gin@req@width=\dimen115
-)
-(/usr/share/texlive/texmf-dist/tex/latex/caption/caption.sty
-Package: caption 2013/05/02 v3.3-89 Customizing captions (AR)
-
-(/usr/share/texlive/texmf-dist/tex/latex/caption/caption3.sty
-Package: caption3 2013/05/02 v1.6-88 caption3 kernel (AR)
-Package caption3 Info: TeX engine: e-TeX on input line 57.
-\captionmargin=\dimen116
-\captionmargin@=\dimen117
-\captionwidth=\dimen118
-\caption@tempdima=\dimen119
-\caption@indent=\dimen120
-\caption@parindent=\dimen121
-\caption@hangindent=\dimen122
-)
-Package caption Info: AMS or SMF document class.
-\c@ContinuedFloat=\count106
-)
-(/usr/share/texlive/texmf-dist/tex/latex/caption/subcaption.sty
-Package: subcaption 2013/02/03 v1.1-62 Sub-captions (AR)
-\c@subfigure=\count107
-\c@subtable=\count108
-)
-(/usr/share/texlive/texmf-dist/tex/latex/doublestroke/dsfont.sty
-Package: dsfont 1995/08/01 v0.1 Double stroke roman fonts
-)
-(/usr/share/texlive/texmf-dist/tex/latex/stmaryrd/stmaryrd.sty
-Package: stmaryrd 1994/03/03 St Mary's Road symbol package
-\symstmry=\mathgroup6
-LaTeX Font Info: Overwriting symbol font `stmry' in version `bold'
-(Font) U/stmry/m/n --> U/stmry/b/n on input line 89.
-)
-(/usr/share/texlive/texmf-dist/tex/latex/base/ifthen.sty
-Package: ifthen 2001/05/26 v1.1c Standard LaTeX ifthen package (DPC)
-)
-(/usr/share/texlive/texmf-dist/tex/latex/graphics/color.sty
-Package: color 2005/11/14 v1.0j Standard LaTeX Color (DPC)
-
-(/usr/share/texlive/texmf-dist/tex/latex/latexconfig/color.cfg
-File: color.cfg 2007/01/18 v1.5 color configuration of teTeX/TeXLive
-)
-Package color Info: Driver file: pdftex.def on input line 130.
-)
-(/usr/share/texlive/texmf-dist/tex/latex/algorithm2e/algorithm2e.sty
-Package: algorithm2e 2013/01/06 v5.00 algorithms environments
-\c@AlgoLine=\count109
-
-(/usr/share/texlive/texmf-dist/tex/latex/tools/xspace.sty
-Package: xspace 2009/10/20 v1.13 Space after command names (DPC,MH)
-)
-(/usr/share/texlive/texmf-dist/tex/latex/relsize/relsize.sty
-Package: relsize 2013/03/29 ver 4.1
-LaTeX Info: Redefining \larger on input line 150.
-LaTeX Info: Redefining \smaller on input line 151.
-)
-********************************************************
-Package `algorithm2e' Release 5.0 -- january 06 2013 --
-- algorithm2e-announce@lirmm.fr mailing list for announcement about releases
-- algorithm2e-discussion@lirmm.fr mailing list for discussion about package
-subscribe by emailing sympa@lirmm.fr with 'subscribe <list> <firstname name>'
-- Author: Christophe Fiorio (cfiorio@um2.fr)
-********************************************************
-\skiptotal=\skip51
-\skiplinenumber=\skip52
-\skiprule=\skip53
-\skiphlne=\skip54
-\skiptext=\skip55
-\skiplength=\skip56
-\algomargin=\skip57
-\skipalgocfslide=\skip58
-\algowidth=\dimen123
-\inoutsize=\dimen124
-\inoutindent=\dimen125
-\interspacetitleruled=\dimen126
-\interspacealgoruled=\dimen127
-\interspacetitleboxruled=\dimen128
-\algocf@inoutbox=\box36
-\algocf@inputbox=\box37
-\AlCapSkip=\skip59
-\AlCapHSkip=\skip60
-\algoskipindent=\skip61
-\algocf@nlbox=\box38
-\algocf@hangingbox=\box39
-\algocf@untilbox=\box40
-\algocf@skipuntil=\skip62
-\algocf@capbox=\box41
-\algoheightruledefault=\skip63
-\algoheightrule=\skip64
-\algotitleheightruledefault=\skip65
-\algotitleheightrule=\skip66
-\c@algocfline=\count110
-\c@algocfproc=\count111
-\c@algocf=\count112
-\algocf@algoframe=\box42
-\algocf@algobox=\box43
-) (/usr/share/texlive/texmf-dist/tex/latex/oberdiek/epstopdf.sty
-Package: epstopdf 2010/02/09 v2.5 Conversion with epstopdf on the fly (HO)
-
-(/usr/share/texlive/texmf-dist/tex/latex/oberdiek/epstopdf-base.sty
-Package: epstopdf-base 2010/02/09 v2.5 Base part for package epstopdf
-
-(/usr/share/texlive/texmf-dist/tex/latex/oberdiek/grfext.sty
-Package: grfext 2010/08/19 v1.1 Manage graphics extensions (HO)
-
-(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/kvdefinekeys.sty
-Package: kvdefinekeys 2011/04/07 v1.3 Define keys (HO)
-))
-(/usr/share/texlive/texmf-dist/tex/latex/oberdiek/kvoptions.sty
-Package: kvoptions 2011/06/30 v3.11 Key value format for package options (HO)
-
-(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/kvsetkeys.sty
-Package: kvsetkeys 2012/04/25 v1.16 Key value parser (HO)
-
-(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/etexcmds.sty
-Package: etexcmds 2011/02/16 v1.5 Avoid name clashes with e-TeX commands (HO)
-
-(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/ifluatex.sty
-Package: ifluatex 2010/03/01 v1.3 Provides the ifluatex switch (HO)
-Package ifluatex Info: LuaTeX not detected.
-)
-Package etexcmds Info: Could not find \expanded.
-(etexcmds) That can mean that you are not using pdfTeX 1.50 or
-(etexcmds) that some package has redefined \expanded.
-(etexcmds) In the latter case, load this package earlier.
-)))
-(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/pdftexcmds.sty
-Package: pdftexcmds 2011/11/29 v0.20 Utility functions of pdfTeX for LuaTeX (HO
-)
-
-(/usr/share/texlive/texmf-dist/tex/generic/oberdiek/ifpdf.sty
-Package: ifpdf 2011/01/30 v2.3 Provides the ifpdf switch (HO)
-Package ifpdf Info: pdfTeX in PDF mode is detected.
-)
-Package pdftexcmds Info: LuaTeX not detected.
-Package pdftexcmds Info: \pdf@primitive is available.
-Package pdftexcmds Info: \pdf@ifprimitive is available.
-Package pdftexcmds Info: \pdfdraftmode found.
-)
-Package grfext Info: Graphics extension search list:
-(grfext) [.png,.pdf,.jpg,.mps,.jpeg,.jbig2,.jb2,.PNG,.PDF,.JPG,.JPE
-G,.JBIG2,.JB2,.eps]
-(grfext) \AppendGraphicsExtensions on input line 452.
-
-(/usr/share/texlive/texmf-dist/tex/latex/latexconfig/epstopdf-sys.cfg
-File: epstopdf-sys.cfg 2010/07/13 v1.3 Configuration of (r)epstopdf for TeX Liv
-e
-)))
-(/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty
-Package: inputenc 2008/03/30 v1.1d Input encoding file
-\inpenc@prehook=\toks26
-\inpenc@posthook=\toks27
-
-(/usr/share/texlive/texmf-dist/tex/latex/base/utf8.def
-File: utf8.def 2008/04/05 v1.1m UTF-8 support for inputenc
-Now handling font encoding OML ...
-... no UTF-8 mapping file for font encoding OML
-Now handling font encoding T1 ...
-... processing UTF-8 mapping file for font encoding T1
-
-(/usr/share/texlive/texmf-dist/tex/latex/base/t1enc.dfu
-File: t1enc.dfu 2008/04/05 v1.1m UTF-8 support for inputenc
- defining Unicode char U+00A1 (decimal 161)
- defining Unicode char U+00A3 (decimal 163)
- defining Unicode char U+00AB (decimal 171)
- defining Unicode char U+00BB (decimal 187)
- defining Unicode char U+00BF (decimal 191)
- defining Unicode char U+00C0 (decimal 192)
- defining Unicode char U+00C1 (decimal 193)
- defining Unicode char U+00C2 (decimal 194)
- defining Unicode char U+00C3 (decimal 195)
- defining Unicode char U+00C4 (decimal 196)
- defining Unicode char U+00C5 (decimal 197)
- defining Unicode char U+00C6 (decimal 198)
- defining Unicode char U+00C7 (decimal 199)
- defining Unicode char U+00C8 (decimal 200)
- defining Unicode char U+00C9 (decimal 201)
- defining Unicode char U+00CA (decimal 202)
- defining Unicode char U+00CB (decimal 203)
- defining Unicode char U+00CC (decimal 204)
- defining Unicode char U+00CD (decimal 205)
- defining Unicode char U+00CE (decimal 206)
- defining Unicode char U+00CF (decimal 207)
- defining Unicode char U+00D0 (decimal 208)
- defining Unicode char U+00D1 (decimal 209)
- defining Unicode char U+00D2 (decimal 210)
- defining Unicode char U+00D3 (decimal 211)
- defining Unicode char U+00D4 (decimal 212)
- defining Unicode char U+00D5 (decimal 213)
- defining Unicode char U+00D6 (decimal 214)
- defining Unicode char U+00D8 (decimal 216)
- defining Unicode char U+00D9 (decimal 217)
- defining Unicode char U+00DA (decimal 218)
- defining Unicode char U+00DB (decimal 219)
- defining Unicode char U+00DC (decimal 220)
- defining Unicode char U+00DD (decimal 221)
- defining Unicode char U+00DE (decimal 222)
- defining Unicode char U+00DF (decimal 223)
- defining Unicode char U+00E0 (decimal 224)
- defining Unicode char U+00E1 (decimal 225)
- defining Unicode char U+00E2 (decimal 226)
- defining Unicode char U+00E3 (decimal 227)
- defining Unicode char U+00E4 (decimal 228)
- defining Unicode char U+00E5 (decimal 229)
- defining Unicode char U+00E6 (decimal 230)
- defining Unicode char U+00E7 (decimal 231)
- defining Unicode char U+00E8 (decimal 232)
- defining Unicode char U+00E9 (decimal 233)
- defining Unicode char U+00EA (decimal 234)
- defining Unicode char U+00EB (decimal 235)
- defining Unicode char U+00EC (decimal 236)
- defining Unicode char U+00ED (decimal 237)
- defining Unicode char U+00EE (decimal 238)
- defining Unicode char U+00EF (decimal 239)
- defining Unicode char U+00F0 (decimal 240)
- defining Unicode char U+00F1 (decimal 241)
- defining Unicode char U+00F2 (decimal 242)
- defining Unicode char U+00F3 (decimal 243)
- defining Unicode char U+00F4 (decimal 244)
- defining Unicode char U+00F5 (decimal 245)
- defining Unicode char U+00F6 (decimal 246)
- defining Unicode char U+00F8 (decimal 248)
- defining Unicode char U+00F9 (decimal 249)
- defining Unicode char U+00FA (decimal 250)
- defining Unicode char U+00FB (decimal 251)
- defining Unicode char U+00FC (decimal 252)
- defining Unicode char U+00FD (decimal 253)
- defining Unicode char U+00FE (decimal 254)
- defining Unicode char U+00FF (decimal 255)
- defining Unicode char U+0102 (decimal 258)
- defining Unicode char U+0103 (decimal 259)
- defining Unicode char U+0104 (decimal 260)
- defining Unicode char U+0105 (decimal 261)
- defining Unicode char U+0106 (decimal 262)
- defining Unicode char U+0107 (decimal 263)
- defining Unicode char U+010C (decimal 268)
- defining Unicode char U+010D (decimal 269)
- defining Unicode char U+010E (decimal 270)
- defining Unicode char U+010F (decimal 271)
- defining Unicode char U+0110 (decimal 272)
- defining Unicode char U+0111 (decimal 273)
- defining Unicode char U+0118 (decimal 280)
- defining Unicode char U+0119 (decimal 281)
- defining Unicode char U+011A (decimal 282)
- defining Unicode char U+011B (decimal 283)
- defining Unicode char U+011E (decimal 286)
- defining Unicode char U+011F (decimal 287)
- defining Unicode char U+0130 (decimal 304)
- defining Unicode char U+0131 (decimal 305)
- defining Unicode char U+0132 (decimal 306)
- defining Unicode char U+0133 (decimal 307)
- defining Unicode char U+0139 (decimal 313)
- defining Unicode char U+013A (decimal 314)
- defining Unicode char U+013D (decimal 317)
- defining Unicode char U+013E (decimal 318)
- defining Unicode char U+0141 (decimal 321)
- defining Unicode char U+0142 (decimal 322)
- defining Unicode char U+0143 (decimal 323)
- defining Unicode char U+0144 (decimal 324)
- defining Unicode char U+0147 (decimal 327)
- defining Unicode char U+0148 (decimal 328)
- defining Unicode char U+014A (decimal 330)
- defining Unicode char U+014B (decimal 331)
- defining Unicode char U+0150 (decimal 336)
- defining Unicode char U+0151 (decimal 337)
- defining Unicode char U+0152 (decimal 338)
- defining Unicode char U+0153 (decimal 339)
- defining Unicode char U+0154 (decimal 340)
- defining Unicode char U+0155 (decimal 341)
- defining Unicode char U+0158 (decimal 344)
- defining Unicode char U+0159 (decimal 345)
- defining Unicode char U+015A (decimal 346)
- defining Unicode char U+015B (decimal 347)
- defining Unicode char U+015E (decimal 350)
- defining Unicode char U+015F (decimal 351)
- defining Unicode char U+0160 (decimal 352)
- defining Unicode char U+0161 (decimal 353)
- defining Unicode char U+0162 (decimal 354)
- defining Unicode char U+0163 (decimal 355)
- defining Unicode char U+0164 (decimal 356)
- defining Unicode char U+0165 (decimal 357)
- defining Unicode char U+016E (decimal 366)
- defining Unicode char U+016F (decimal 367)
- defining Unicode char U+0170 (decimal 368)
- defining Unicode char U+0171 (decimal 369)
- defining Unicode char U+0178 (decimal 376)
- defining Unicode char U+0179 (decimal 377)
- defining Unicode char U+017A (decimal 378)
- defining Unicode char U+017B (decimal 379)
- defining Unicode char U+017C (decimal 380)
- defining Unicode char U+017D (decimal 381)
- defining Unicode char U+017E (decimal 382)
- defining Unicode char U+200C (decimal 8204)
- defining Unicode char U+2013 (decimal 8211)
- defining Unicode char U+2014 (decimal 8212)
- defining Unicode char U+2018 (decimal 8216)
- defining Unicode char U+2019 (decimal 8217)
- defining Unicode char U+201A (decimal 8218)
- defining Unicode char U+201C (decimal 8220)
- defining Unicode char U+201D (decimal 8221)
- defining Unicode char U+201E (decimal 8222)
- defining Unicode char U+2030 (decimal 8240)
- defining Unicode char U+2031 (decimal 8241)
- defining Unicode char U+2039 (decimal 8249)
- defining Unicode char U+203A (decimal 8250)
- defining Unicode char U+2423 (decimal 9251)
-)
-Now handling font encoding OT1 ...
-... processing UTF-8 mapping file for font encoding OT1
-
-(/usr/share/texlive/texmf-dist/tex/latex/base/ot1enc.dfu
-File: ot1enc.dfu 2008/04/05 v1.1m UTF-8 support for inputenc
- defining Unicode char U+00A1 (decimal 161)
- defining Unicode char U+00A3 (decimal 163)
- defining Unicode char U+00B8 (decimal 184)
- defining Unicode char U+00BF (decimal 191)
- defining Unicode char U+00C5 (decimal 197)
- defining Unicode char U+00C6 (decimal 198)
- defining Unicode char U+00D8 (decimal 216)
- defining Unicode char U+00DF (decimal 223)
- defining Unicode char U+00E6 (decimal 230)
- defining Unicode char U+00EC (decimal 236)
- defining Unicode char U+00ED (decimal 237)
- defining Unicode char U+00EE (decimal 238)
- defining Unicode char U+00EF (decimal 239)
- defining Unicode char U+00F8 (decimal 248)
- defining Unicode char U+0131 (decimal 305)
- defining Unicode char U+0141 (decimal 321)
- defining Unicode char U+0142 (decimal 322)
- defining Unicode char U+0152 (decimal 338)
- defining Unicode char U+0153 (decimal 339)
- defining Unicode char U+2013 (decimal 8211)
- defining Unicode char U+2014 (decimal 8212)
- defining Unicode char U+2018 (decimal 8216)
- defining Unicode char U+2019 (decimal 8217)
- defining Unicode char U+201C (decimal 8220)
- defining Unicode char U+201D (decimal 8221)
-)
-Now handling font encoding OMS ...
-... processing UTF-8 mapping file for font encoding OMS
-
-(/usr/share/texlive/texmf-dist/tex/latex/base/omsenc.dfu
-File: omsenc.dfu 2008/04/05 v1.1m UTF-8 support for inputenc
- defining Unicode char U+00A7 (decimal 167)
- defining Unicode char U+00B6 (decimal 182)
- defining Unicode char U+00B7 (decimal 183)
- defining Unicode char U+2020 (decimal 8224)
- defining Unicode char U+2021 (decimal 8225)
- defining Unicode char U+2022 (decimal 8226)
-)
-Now handling font encoding OMX ...
-... no UTF-8 mapping file for font encoding OMX
-Now handling font encoding U ...
-... no UTF-8 mapping file for font encoding U
- defining Unicode char U+00A9 (decimal 169)
- defining Unicode char U+00AA (decimal 170)
- defining Unicode char U+00AE (decimal 174)
- defining Unicode char U+00BA (decimal 186)
- defining Unicode char U+02C6 (decimal 710)
- defining Unicode char U+02DC (decimal 732)
- defining Unicode char U+200C (decimal 8204)
- defining Unicode char U+2026 (decimal 8230)
- defining Unicode char U+2122 (decimal 8482)
- defining Unicode char U+2423 (decimal 9251)
-))
-(/usr/share/texlive/texmf-dist/tex/latex/base/fontenc.sty
-Package: fontenc 2005/09/27 v1.99g Standard LaTeX package
-
-(/usr/share/texlive/texmf-dist/tex/latex/base/t1enc.def
-File: t1enc.def 2005/09/27 v1.99g Standard LaTeX file
-LaTeX Font Info: Redeclaring font encoding T1 on input line 43.
-))
-(/usr/share/texlive/texmf-dist/tex/generic/babel/babel.sty
-Package: babel 2013/12/03 3.9h The Babel package
-
-(/usr/share/texlive/texmf-dist/tex/generic/babel-english/english.ldf
-Language: english 2012/08/20 v3.3p English support from the babel system
-
-(/usr/share/texlive/texmf-dist/tex/generic/babel/babel.def
-File: babel.def 2013/12/03 3.9h Babel common definitions
-\babel@savecnt=\count113
-\U@D=\dimen129
-)
-\l@canadian = a dialect from \language\l@american
-\l@australian = a dialect from \language\l@british
-\l@newzealand = a dialect from \language\l@british
-))
-(/usr/share/texlive/texmf-dist/tex/latex/amsfonts/amssymb.sty
-Package: amssymb 2013/01/14 v3.01 AMS font symbols
-LaTeX Font Info: Redeclaring math symbol \boxdot on input line 44.
-)
-(/usr/share/texlive/texmf-dist/tex/latex/base/latexsym.sty
-Package: latexsym 1998/08/17 v2.2e Standard LaTeX package (lasy symbols)
-\symlasy=\mathgroup7
-LaTeX Font Info: Overwriting symbol font `lasy' in version `bold'
-(Font) U/lasy/m/n --> U/lasy/b/n on input line 47.
-)
-(/usr/share/texlive/texmf-dist/tex/latex/amsfonts/eufrak.sty
-
-Package eufrak Warning: The eufrak package is redundant if the amsfonts package
- is used on input line 36.
-
-) (/usr/share/texlive/texmf-dist/tex/latex/amsfonts/euscript.sty
-Package: euscript 2009/06/22 v3.00 Euler Script fonts
-LaTeX Font Info: Overwriting math alphabet `\EuScript' in version `bold'
-(Font) U/eus/m/n --> U/eus/b/n on input line 33.
-)
-(/usr/share/texlive/texmf-dist/tex/latex/pstricks/pstricks.sty
-Package: pstricks 2013/12/12 v0.60 LaTeX wrapper for `PSTricks' (RN,HV)
-
-(/usr/share/texlive/texmf-dist/tex/generic/pstricks/pstricks.tex
-(/usr/share/texlive/texmf-dist/tex/generic/xkeyval/pst-xkey.tex
-File: pst-xkey.tex 2005/11/25 v1.6 PSTricks specialization of xkeyval (HA)
-
-(/usr/share/texlive/texmf-dist/tex/latex/xkeyval/xkeyval.sty
-Package: xkeyval 2012/10/14 v2.6b package option processing (HA)
-
-(/usr/share/texlive/texmf-dist/tex/generic/xkeyval/xkeyval.tex
-\XKV@toks=\toks28
-\XKV@tempa@toks=\toks29
-\XKV@depth=\count114
-File: xkeyval.tex 2012/10/14 v2.6b key=value parser (HA)
-)))
-(/usr/share/texlive/texmf-dist/tex/generic/pstricks/pst-fp.tex
-`pst-fp' v0.05, 2010/01/17 (hv)
-\pstFP@xs=\count115
-\pstFP@xia=\count116
-\pstFP@xib=\count117
-\pstFP@xfa=\count118
-\pstFP@xfb=\count119
-\pstFP@rega=\count120
-\pstFP@regb=\count121
-\pstFP@regs=\count122
-\pstFP@times=\count123
-)
-(/usr/share/texmf/tex/generic/pgf/utilities/pgfutil-common.tex
-\pgfutil@everybye=\toks30
-)
-(/usr/share/texmf/tex/generic/pgf/utilities/pgfkeys.code.tex
-\pgfkeys@pathtoks=\toks31
-\pgfkeys@temptoks=\toks32
-
-(/usr/share/texmf/tex/generic/pgf/utilities/pgfkeysfiltered.code.tex
-\pgfkeys@tmptoks=\toks33
-))
-(/usr/share/texmf/tex/generic/pgf/utilities/pgffor.code.tex
-\pgffor@iter=\dimen130
-\pgffor@skip=\dimen131
-\pgffor@stack=\toks34
-\pgffor@toks=\toks35
-)
-\psLoopIndex=\count124
-
-`PSTricks' v2.51 <2014/02/03> (tvz)
-\pst@dima=\dimen132
-\pst@dimb=\dimen133
-\pst@dimc=\dimen134
-\pst@dimd=\dimen135
-\pst@dimg=\dimen136
-\pst@dimh=\dimen137
-\pst@dimm=\dimen138
-\pst@dimn=\dimen139
-\pst@dimo=\dimen140
-\pst@dimp=\dimen141
-\pst@hbox=\box44
-\pst@ibox=\box45
-\pst@boxg=\box46
-\pst@cnta=\count125
-\pst@cntb=\count126
-\pst@cntc=\count127
-\pst@cntd=\count128
-\pst@cntg=\count129
-\pst@cnth=\count130
-\pst@cntm=\count131
-\pst@cntn=\count132
-\pst@cnto=\count133
-\pst@cntp=\count134
-\@zero=\count135
-\pst@toks=\toks36
-(/usr/share/texlive/texmf-dist/tex/generic/pstricks/pstricks.con)
-\psunit=\dimen142
-\psxunit=\dimen143
-\psyunit=\dimen144
-\pst@C@@rType=\count136
-\pslinewidth=\dimen145
-\psk@startLW=\dimen146
-\psk@endLW=\dimen147
-\pst@customdefs=\toks37
-\pslinearc=\dimen148
-\pst@symbolStep=\dimen149
-\pst@symbolWidth=\dimen150
-\pst@symbolLinewidth=\dimen151
-\everypsbox=\toks38
-\psframesep=\dimen152
-\pslabelsep=\dimen153
-\sh@wgridXunit=\dimen154
-\sh@wgridYunit=\dimen155
-\pst@shift=\dimen156
-)
-File: pstricks.tex 2014/02/03 v2.51 `PSTricks' (tvz,hv)
-
-(/usr/share/texlive/texmf-dist/tex/generic/pstricks/pst-fp.tex)
-File: pst-fp.tex 2014/02/03 v2.51 `PST-fp' (hv)
-
-(/usr/share/texmf/tex/latex/xcolor/xcolor.sty
-Package: xcolor 2007/01/21 v2.11 LaTeX color extensions (UK)
-
-(/usr/share/texlive/texmf-dist/tex/latex/latexconfig/color.cfg
-File: color.cfg 2007/01/18 v1.5 color configuration of teTeX/TeXLive
-)
-Package xcolor Info: Driver file: pdftex.def on input line 225.
-LaTeX Info: Redefining \color on input line 702.
-Package xcolor Info: Model `cmy' substituted by `cmy0' on input line 1337.
-Package xcolor Info: Model `hsb' substituted by `rgb' on input line 1341.
-Package xcolor Info: Model `RGB' extended on input line 1353.
-Package xcolor Info: Model `HTML' substituted by `rgb' on input line 1355.
-Package xcolor Info: Model `Hsb' substituted by `hsb' on input line 1356.
-Package xcolor Info: Model `tHsb' substituted by `hsb' on input line 1357.
-Package xcolor Info: Model `HSB' substituted by `hsb' on input line 1358.
-Package xcolor Info: Model `Gray' substituted by `gray' on input line 1359.
-Package xcolor Info: Model `wave' substituted by `hsb' on input line 1360.
-))
-(/usr/share/texlive/texmf-dist/tex/latex/pst-node/pst-node.sty
-Package: pst-node 2012/09/18 v1.01 LaTeX wrapper for `pst-node' (HV)
-Package: pst-node 2010/04/22 package wrapper for pst-node.tex
-
-(/usr/share/texlive/texmf-dist/tex/generic/pst-node/pst-node.tex
- v1.32, 2014/02/03
-\psrow=\count137
-\pscol=\count138
-\psmatrixcnt=\count139
-\psrowsep=\skip67
-\pscolsep=\skip68
-\pst@args=\count140
-\num@pts=\count141
-\pst@argcnt=\count142
-)
-File: pst-node.tex 2014/02/03 1.32 `pst-node' (tvz,hv)
-)
-(/usr/share/texlive/texmf-dist/tex/latex/pst-coil/pst-coil.sty
-Package: pst-coil 2010/02/01 package wrapper for pst-coil.tex (hv)
-
-(/usr/share/texlive/texmf-dist/tex/generic/pst-coil/pst-coil.tex
- v1.32, 2014/02/03
-(/usr/share/texlive/texmf-dist/tex/generic/pst-node/pst-node.tex))
-File: pst-coil.tex 2011/09/17 v1.06 `PST-coil' (tvz,hv)
-)
-(/usr/share/texlive/texmf-dist/tex/latex/url/url.sty
-\Urlmuskip=\muskip11
-Package: url 2013/09/16 ver 3.4 Verb mode for urls, etc.
-)
-(/usr/share/texmf/tex/latex/pgf/frontendlayer/tikz.sty
-(/usr/share/texmf/tex/latex/pgf/basiclayer/pgf.sty
-(/usr/share/texmf/tex/latex/pgf/utilities/pgfrcs.sty
-(/usr/share/texmf/tex/generic/pgf/utilities/pgfutil-common.tex
-\pgfutil@everybye=\toks39
-)
-(/usr/share/texmf/tex/generic/pgf/utilities/pgfutil-latex.def
-\pgfutil@abb=\box47
-
-(/usr/share/texlive/texmf-dist/tex/latex/ms/everyshi.sty
-Package: everyshi 2001/05/15 v3.00 EveryShipout Package (MS)
-))
-(/usr/share/texmf/tex/generic/pgf/utilities/pgfrcs.code.tex
-Package: pgfrcs 2010/10/25 v2.10 (rcs-revision 1.24)
-))
-Package: pgf 2008/01/15 v2.10 (rcs-revision 1.12)
-
-(/usr/share/texmf/tex/latex/pgf/basiclayer/pgfcore.sty
-(/usr/share/texmf/tex/latex/pgf/systemlayer/pgfsys.sty
-(/usr/share/texmf/tex/generic/pgf/systemlayer/pgfsys.code.tex
-Package: pgfsys 2010/06/30 v2.10 (rcs-revision 1.37)
-
-(/usr/share/texmf/tex/generic/pgf/utilities/pgfkeys.code.tex)
-\pgf@x=\dimen157
-\pgf@y=\dimen158
-\pgf@xa=\dimen159
-\pgf@ya=\dimen160
-\pgf@xb=\dimen161
-\pgf@yb=\dimen162
-\pgf@xc=\dimen163
-\pgf@yc=\dimen164
-\w@pgf@writea=\write3
-\r@pgf@reada=\read1
-\c@pgf@counta=\count143
-\c@pgf@countb=\count144
-\c@pgf@countc=\count145
-\c@pgf@countd=\count146
-
-(/usr/share/texmf/tex/generic/pgf/systemlayer/pgf.cfg
-File: pgf.cfg 2008/05/14 (rcs-revision 1.7)
-)
-Package pgfsys Info: Driver file for pgf: pgfsys-pdftex.def on input line 900.
-
-(/usr/share/texmf/tex/generic/pgf/systemlayer/pgfsys-pdftex.def
-File: pgfsys-pdftex.def 2009/05/22 (rcs-revision 1.26)
-
-(/usr/share/texmf/tex/generic/pgf/systemlayer/pgfsys-common-pdf.def
-File: pgfsys-common-pdf.def 2008/05/19 (rcs-revision 1.10)
-)))
-(/usr/share/texmf/tex/generic/pgf/systemlayer/pgfsyssoftpath.code.tex
-File: pgfsyssoftpath.code.tex 2008/07/18 (rcs-revision 1.7)
-\pgfsyssoftpath@smallbuffer@items=\count147
-\pgfsyssoftpath@bigbuffer@items=\count148
-)
-(/usr/share/texmf/tex/generic/pgf/systemlayer/pgfsysprotocol.code.tex
-File: pgfsysprotocol.code.tex 2006/10/16 (rcs-revision 1.4)
-))
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcore.code.tex
-Package: pgfcore 2010/04/11 v2.10 (rcs-revision 1.7)
-
-(/usr/share/texmf/tex/generic/pgf/math/pgfmath.code.tex
-(/usr/share/texmf/tex/generic/pgf/math/pgfmathcalc.code.tex
-(/usr/share/texmf/tex/generic/pgf/math/pgfmathutil.code.tex)
-(/usr/share/texmf/tex/generic/pgf/math/pgfmathparser.code.tex
-\pgfmath@dimen=\dimen165
-\pgfmath@count=\count149
-\pgfmath@box=\box48
-\pgfmath@toks=\toks40
-\pgfmath@stack@operand=\toks41
-\pgfmath@stack@operation=\toks42
-)
-(/usr/share/texmf/tex/generic/pgf/math/pgfmathfunctions.code.tex
-(/usr/share/texmf/tex/generic/pgf/math/pgfmathfunctions.basic.code.tex)
-(/usr/share/texmf/tex/generic/pgf/math/pgfmathfunctions.trigonometric.code.tex)
-(/usr/share/texmf/tex/generic/pgf/math/pgfmathfunctions.random.code.tex)
-(/usr/share/texmf/tex/generic/pgf/math/pgfmathfunctions.comparison.code.tex)
-(/usr/share/texmf/tex/generic/pgf/math/pgfmathfunctions.base.code.tex)
-(/usr/share/texmf/tex/generic/pgf/math/pgfmathfunctions.round.code.tex)
-(/usr/share/texmf/tex/generic/pgf/math/pgfmathfunctions.misc.code.tex)))
-(/usr/share/texmf/tex/generic/pgf/math/pgfmathfloat.code.tex
-\c@pgfmathroundto@lastzeros=\count150
-))
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcorepoints.code.tex
-File: pgfcorepoints.code.tex 2010/04/09 (rcs-revision 1.20)
-\pgf@picminx=\dimen166
-\pgf@picmaxx=\dimen167
-\pgf@picminy=\dimen168
-\pgf@picmaxy=\dimen169
-\pgf@pathminx=\dimen170
-\pgf@pathmaxx=\dimen171
-\pgf@pathminy=\dimen172
-\pgf@pathmaxy=\dimen173
-\pgf@xx=\dimen174
-\pgf@xy=\dimen175
-\pgf@yx=\dimen176
-\pgf@yy=\dimen177
-\pgf@zx=\dimen178
-\pgf@zy=\dimen179
-)
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcorepathconstruct.code.tex
-File: pgfcorepathconstruct.code.tex 2010/08/03 (rcs-revision 1.24)
-\pgf@path@lastx=\dimen180
-\pgf@path@lasty=\dimen181
-)
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcorepathusage.code.tex
-File: pgfcorepathusage.code.tex 2008/04/22 (rcs-revision 1.12)
-\pgf@shorten@end@additional=\dimen182
-\pgf@shorten@start@additional=\dimen183
-)
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcorescopes.code.tex
-File: pgfcorescopes.code.tex 2010/09/08 (rcs-revision 1.34)
-\pgfpic=\box49
-\pgf@hbox=\box50
-\pgf@layerbox@main=\box51
-\pgf@picture@serial@count=\count151
-)
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcoregraphicstate.code.tex
-File: pgfcoregraphicstate.code.tex 2008/04/22 (rcs-revision 1.9)
-\pgflinewidth=\dimen184
-)
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcoretransformations.code.tex
-File: pgfcoretransformations.code.tex 2009/06/10 (rcs-revision 1.11)
-\pgf@pt@x=\dimen185
-\pgf@pt@y=\dimen186
-\pgf@pt@temp=\dimen187
-)
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcorequick.code.tex
-File: pgfcorequick.code.tex 2008/10/09 (rcs-revision 1.3)
-)
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcoreobjects.code.tex
-File: pgfcoreobjects.code.tex 2006/10/11 (rcs-revision 1.2)
-)
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcorepathprocessing.code.tex
-File: pgfcorepathprocessing.code.tex 2008/10/09 (rcs-revision 1.8)
-)
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcorearrows.code.tex
-File: pgfcorearrows.code.tex 2008/04/23 (rcs-revision 1.11)
-)
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcoreshade.code.tex
-File: pgfcoreshade.code.tex 2008/11/23 (rcs-revision 1.13)
-\pgf@max=\dimen188
-\pgf@sys@shading@range@num=\count152
-)
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcoreimage.code.tex
-File: pgfcoreimage.code.tex 2010/03/25 (rcs-revision 1.16)
-
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcoreexternal.code.tex
-File: pgfcoreexternal.code.tex 2010/09/01 (rcs-revision 1.17)
-\pgfexternal@startupbox=\box52
-))
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcorelayers.code.tex
-File: pgfcorelayers.code.tex 2010/08/27 (rcs-revision 1.2)
-)
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcoretransparency.code.tex
-File: pgfcoretransparency.code.tex 2008/01/17 (rcs-revision 1.2)
-)
-(/usr/share/texmf/tex/generic/pgf/basiclayer/pgfcorepatterns.code.tex
-File: pgfcorepatterns.code.tex 2009/07/02 (rcs-revision 1.3)
-)))
-(/usr/share/texmf/tex/generic/pgf/modules/pgfmoduleshapes.code.tex
-File: pgfmoduleshapes.code.tex 2010/09/09 (rcs-revision 1.13)
-\pgfnodeparttextbox=\box53
-)
-(/usr/share/texmf/tex/generic/pgf/modules/pgfmoduleplot.code.tex
-File: pgfmoduleplot.code.tex 2010/10/22 (rcs-revision 1.8)
-)
-(/usr/share/texmf/tex/latex/pgf/compatibility/pgfcomp-version-0-65.sty
-Package: pgfcomp-version-0-65 2007/07/03 v2.10 (rcs-revision 1.7)
-\pgf@nodesepstart=\dimen189
-\pgf@nodesepend=\dimen190
-)
-(/usr/share/texmf/tex/latex/pgf/compatibility/pgfcomp-version-1-18.sty
-Package: pgfcomp-version-1-18 2007/07/23 v2.10 (rcs-revision 1.1)
-))
-(/usr/share/texmf/tex/latex/pgf/utilities/pgffor.sty
-(/usr/share/texmf/tex/latex/pgf/utilities/pgfkeys.sty
-(/usr/share/texmf/tex/generic/pgf/utilities/pgfkeys.code.tex))
-(/usr/share/texmf/tex/generic/pgf/utilities/pgffor.code.tex
-Package: pgffor 2010/03/23 v2.10 (rcs-revision 1.18)
-\pgffor@iter=\dimen191
-\pgffor@skip=\dimen192
-\pgffor@stack=\toks43
-\pgffor@toks=\toks44
-))
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/tikz.code.tex
-Package: tikz 2010/10/13 v2.10 (rcs-revision 1.76)
-
-(/usr/share/texmf/tex/generic/pgf/libraries/pgflibraryplothandlers.code.tex
-File: pgflibraryplothandlers.code.tex 2010/05/31 v2.10 (rcs-revision 1.15)
-\pgf@plot@mark@count=\count153
-\pgfplotmarksize=\dimen193
-)
-\tikz@lastx=\dimen194
-\tikz@lasty=\dimen195
-\tikz@lastxsaved=\dimen196
-\tikz@lastysaved=\dimen197
-\tikzleveldistance=\dimen198
-\tikzsiblingdistance=\dimen199
-\tikz@figbox=\box54
-\tikz@tempbox=\box55
-\tikztreelevel=\count154
-\tikznumberofchildren=\count155
-\tikznumberofcurrentchild=\count156
-\tikz@fig@count=\count157
-
-(/usr/share/texmf/tex/generic/pgf/modules/pgfmodulematrix.code.tex
-File: pgfmodulematrix.code.tex 2010/08/24 (rcs-revision 1.4)
-\pgfmatrixcurrentrow=\count158
-\pgfmatrixcurrentcolumn=\count159
-\pgf@matrix@numberofcolumns=\count160
-)
-\tikz@expandcount=\count161
-
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibrarytopat
-hs.code.tex
-File: tikzlibrarytopaths.code.tex 2008/06/17 v2.10 (rcs-revision 1.2)
-)))
-(/usr/share/texmf/tex/latex/pgf/compatibility/pgflibrarysnakes.sty
-
-Package pgf Warning: This package is obsolete. Use \usetikzlibrary {snakes} ins
-tead on input line 11.
-
-(/usr/share/texmf/tex/generic/pgf/libraries/pgflibrarysnakes.code.tex
-File: pgflibrarysnakes.code.tex 2008/01/19 v2.10 (rcs-revision 1.24)
-
-
-Package pgf Warning: Snakes have been superseded by decorations. Use the decora
-tion libraries instead of the snakes library on input line 13.
-
-
-(/usr/share/texmf/tex/generic/pgf/libraries/decorations/pgflibrarydecorations.p
-athmorphing.code.tex
-(/usr/share/texmf/tex/generic/pgf/modules/pgfmoduledecorations.code.tex
-\pgfdecoratedcompleteddistance=\dimen200
-\pgfdecoratedremainingdistance=\dimen201
-\pgfdecoratedinputsegmentcompleteddistance=\dimen202
-\pgfdecoratedinputsegmentremainingdistance=\dimen203
-\pgf@decorate@distancetomove=\dimen204
-\pgf@decorate@repeatstate=\count162
-\pgfdecorationsegmentamplitude=\dimen205
-\pgfdecorationsegmentlength=\dimen206
-))
-(/usr/share/texmf/tex/generic/pgf/libraries/decorations/pgflibrarydecorations.p
-athreplacing.code.tex)
-(/usr/share/texmf/tex/generic/pgf/libraries/decorations/pgflibrarydecorations.s
-hapes.code.tex))) (/usr/share/texlive/texmf-dist/tex/latex/tools/multicol.sty
-Package: multicol 2011/06/27 v1.7a multicolumn formatting (FMi)
-\c@tracingmulticols=\count163
-\mult@box=\box56
-\multicol@leftmargin=\dimen207
-\c@unbalance=\count164
-\c@collectmore=\count165
-\doublecol@number=\count166
-\multicoltolerance=\count167
-\multicolpretolerance=\count168
-\full@width=\dimen208
-\page@free=\dimen209
-\premulticols=\dimen210
-\postmulticols=\dimen211
-\multicolsep=\skip69
-\multicolbaselineskip=\skip70
-\partial@page=\box57
-\last@line=\box58
-\mult@rightbox=\box59
-\mult@grightbox=\box60
-\mult@gfirstbox=\box61
-\mult@firstbox=\box62
-\@tempa=\box63
-\@tempa=\box64
-\@tempa=\box65
-\@tempa=\box66
-\@tempa=\box67
-\@tempa=\box68
-\@tempa=\box69
-\@tempa=\box70
-\@tempa=\box71
-\@tempa=\box72
-\@tempa=\box73
-\@tempa=\box74
-\@tempa=\box75
-\@tempa=\box76
-\@tempa=\box77
-\@tempa=\box78
-\@tempa=\box79
-\c@columnbadness=\count169
-\c@finalcolumnbadness=\count170
-\last@try=\dimen212
-\multicolovershoot=\dimen213
-\multicolundershoot=\dimen214
-\mult@nat@firstbox=\box80
-\colbreak@box=\box81
-\multicol@sort@counter=\count171
-)
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibraryarrow
-s.code.tex
-File: tikzlibraryarrows.code.tex 2008/01/09 v2.10 (rcs-revision 1.1)
-
-(/usr/share/texmf/tex/generic/pgf/libraries/pgflibraryarrows.code.tex
-File: pgflibraryarrows.code.tex 2008/10/27 v2.10 (rcs-revision 1.9)
-\arrowsize=\dimen215
-))
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibraryautom
-ata.code.tex
-File: tikzlibraryautomata.code.tex 2008/07/14 v2.10 (rcs-revision 1.3)
-
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibraryshape
-s.multipart.code.tex
-File: tikzlibraryshapes.multipart.code.tex 2008/01/09 v2.10 (rcs-revision 1.1)
-
-(/usr/share/texmf/tex/generic/pgf/libraries/shapes/pgflibraryshapes.multipart.c
-ode.tex
-File: pgflibraryshapes.multipart.code.tex 2010/01/07 v2.10 (rcs-revision 1.2)
-\pgfnodepartlowerbox=\box82
-\pgfnodeparttwobox=\box83
-\pgfnodepartthreebox=\box84
-\pgfnodepartfourbox=\box85
-\pgfnodeparttwentybox=\box86
-\pgfnodepartnineteenbox=\box87
-\pgfnodeparteighteenbox=\box88
-\pgfnodepartseventeenbox=\box89
-\pgfnodepartsixteenbox=\box90
-\pgfnodepartfifteenbox=\box91
-\pgfnodepartfourteenbox=\box92
-\pgfnodepartthirteenbox=\box93
-\pgfnodeparttwelvebox=\box94
-\pgfnodepartelevenbox=\box95
-\pgfnodeparttenbox=\box96
-\pgfnodepartninebox=\box97
-\pgfnodeparteightbox=\box98
-\pgfnodepartsevenbox=\box99
-\pgfnodepartsixbox=\box100
-\pgfnodepartfivebox=\box101
-)))
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibrarysnake
-s.code.tex
-File: tikzlibrarysnakes.code.tex 2008/02/05 v2.10 (rcs-revision 1.6)
-
-
-Package tikz Warning: Snakes have been superseded by decorations. Please use th
-e decoration libraries instead of the snakes library on input line 14.
-
-
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibrarydecor
-ations.pathmorphing.code.tex
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibrarydecor
-ations.code.tex
-\tikz@lib@dec@box=\box102
-))
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibrarydecor
-ations.pathreplacing.code.tex)
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibrarydecor
-ations.shapes.code.tex))
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibraryshape
-s.code.tex
-File: tikzlibraryshapes.code.tex 2008/01/09 v2.10 (rcs-revision 1.1)
-
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibraryshape
-s.geometric.code.tex
-File: tikzlibraryshapes.geometric.code.tex 2008/01/09 v2.10 (rcs-revision 1.1)
-
-(/usr/share/texmf/tex/generic/pgf/libraries/shapes/pgflibraryshapes.geometric.c
-ode.tex
-File: pgflibraryshapes.geometric.code.tex 2008/06/26 v2.10 (rcs-revision 1.1)
-))
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibraryshape
-s.misc.code.tex
-File: tikzlibraryshapes.misc.code.tex 2008/01/09 v2.10 (rcs-revision 1.1)
-
-(/usr/share/texmf/tex/generic/pgf/libraries/shapes/pgflibraryshapes.misc.code.t
-ex
-File: pgflibraryshapes.misc.code.tex 2008/10/07 v2.10 (rcs-revision 1.3)
-))
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibraryshape
-s.symbols.code.tex
-File: tikzlibraryshapes.symbols.code.tex 2008/01/09 v2.10 (rcs-revision 1.1)
-
-(/usr/share/texmf/tex/generic/pgf/libraries/shapes/pgflibraryshapes.symbols.cod
-e.tex
-File: pgflibraryshapes.symbols.code.tex 2009/10/27 v2.10 (rcs-revision 1.3)
-))
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibraryshape
-s.arrows.code.tex
-File: tikzlibraryshapes.arrows.code.tex 2008/01/09 v2.10 (rcs-revision 1.1)
-
-(/usr/share/texmf/tex/generic/pgf/libraries/shapes/pgflibraryshapes.arrows.code
-.tex
-File: pgflibraryshapes.arrows.code.tex 2008/06/26 v2.10 (rcs-revision 1.1)
-))
-(/usr/share/texmf/tex/generic/pgf/frontendlayer/tikz/libraries/tikzlibraryshape
-s.callouts.code.tex
-(/usr/share/texmf/tex/generic/pgf/libraries/shapes/pgflibraryshapes.callouts.co
-de.tex))) (./main.aux)
-\openout1 = `main.aux'.
-
-LaTeX Font Info: Checking defaults for OML/cmm/m/it on input line 87.
-LaTeX Font Info: ... okay on input line 87.
-LaTeX Font Info: Checking defaults for T1/cmr/m/n on input line 87.
-LaTeX Font Info: ... okay on input line 87.
-LaTeX Font Info: Checking defaults for OT1/cmr/m/n on input line 87.
-LaTeX Font Info: ... okay on input line 87.
-LaTeX Font Info: Checking defaults for OMS/cmsy/m/n on input line 87.
-LaTeX Font Info: ... okay on input line 87.
-LaTeX Font Info: Checking defaults for OMX/cmex/m/n on input line 87.
-LaTeX Font Info: ... okay on input line 87.
-LaTeX Font Info: Checking defaults for U/cmr/m/n on input line 87.
-LaTeX Font Info: ... okay on input line 87.
-LaTeX Font Info: Try loading font information for U+msa on input line 87.
-
-(/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsa.fd
-File: umsa.fd 2013/01/14 v3.01 AMS symbols A
-)
-LaTeX Font Info: Try loading font information for U+msb on input line 87.
-
-(/usr/share/texlive/texmf-dist/tex/latex/amsfonts/umsb.fd
-File: umsb.fd 2013/01/14 v3.01 AMS symbols B
-)
-LaTeX Font Info: Try loading font information for U+stmry on input line 87.
-
-(/usr/share/texlive/texmf-dist/tex/latex/stmaryrd/Ustmry.fd)
-LaTeX Font Info: Try loading font information for U+lasy on input line 87.
-
-(/usr/share/texlive/texmf-dist/tex/latex/base/ulasy.fd
-File: ulasy.fd 1998/08/17 v2.2e LaTeX symbol font definitions
-)
-(/usr/share/texlive/texmf-dist/tex/context/base/supp-pdf.mkii
-[Loading MPS to PDF converter (version 2006.09.02).]
-\scratchcounter=\count172
-\scratchdimen=\dimen216
-\scratchbox=\box103
-\nofMPsegments=\count173
-\nofMParguments=\count174
-\everyMPshowfont=\toks45
-\MPscratchCnt=\count175
-\MPscratchDim=\dimen217
-\MPnumerator=\count176
-\makeMPintoPDFobject=\count177
-\everyMPtoPDFconversion=\toks46
-)
-Package caption Info: Begin \AtBeginDocument code.
-Package caption Info: End \AtBeginDocument code.
- ABD: EveryShipout initializing macros (./intro.tex
-LaTeX Font Info: Try loading font information for OMS+cmr on input line 26.
-
-(/usr/share/texlive/texmf-dist/tex/latex/base/omscmr.fd
-File: omscmr.fd 1999/05/25 v2.5h Standard LaTeX font definitions
-)
-LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <7> not available
-(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 26.
- [1
-Non-PDF special ignored!
-Non-PDF special ignored!
-Non-PDF special ignored!
-Non-PDF special ignored!
-Non-PDF special ignored!
-Non-PDF special ignored!
-Non-PDF special ignored!
-Non-PDF special ignored!
-Non-PDF special ignored!
-Non-PDF special ignored!{/var/lib/texmf/fonts/map/pdftex/updmap/pdftex.map}])
-Underfull \vbox (badness 10000) has occurred while \output is active []
-
- [2]
-(./preliminaries.tex
-LaTeX Font Info: Try loading font information for U+dsrom on input line 2.
-
-(/usr/share/texlive/texmf-dist/tex/latex/doublestroke/Udsrom.fd
-File: Udsrom.fd 1995/08/01 v0.1 Double stroke roman font definitions
-)
-<images/iter_f0c.pdf, id=34, 460.72125pt x 340.27126pt>
-File: images/iter_f0c.pdf Graphic file (type pdf)
-
-<use images/iter_f0c.pdf>
-Package pdftex.def Info: images/iter_f0c.pdf used on input line 60.
-(pdftex.def) Requested size: 230.36006pt x 170.13521pt.
- [3]) (./chaos.tex [4 <./images/iter_f0c.pdf>]
-[5]
-Overfull \hbox (12.18526pt too wide) in paragraph at lines 229--232
-[]\T1/cmr/m/n/10 The next $\OML/cmm/m/it/10 n \OMS/cmsy/m/n/10 ^^B [] []$ \T1/c
-mr/m/n/10 dig-its aim at mea-sur-ing how much $\OML/cmm/m/it/10 u[]; u[]; [] ;
-u[]$
- []
-
-[6]
-Underfull \hbox (badness 10000) in paragraph at lines 306--307
-
- []
-
-[7]
-Overfull \hbox (2.48117pt too wide) in paragraph at lines 374--377
-[]$\OML/cmm/m/it/10 d[]\OT1/cmr/m/n/10 (^^F(\OML/cmm/m/it/10 u[]; v[]\OT1/cmr/m
-/n/10 ); ^^F(\OML/cmm/m/it/10 u; v\OT1/cmr/m/n/10 )) = 10[]\OML/cmm/m/it/10 d[]
-\OT1/cmr/m/n/10 ((\OML/cmm/m/it/10 u[]; v[]\OT1/cmr/m/n/10 ); (\OML/cmm/m/it/10
- u; v\OT1/cmr/m/n/10 ))$\T1/cmr/m/n/10 . As the right
- []
-
-<graphe1.pdf, id=73, 106.3975pt x 99.37125pt>
-File: graphe1.pdf Graphic file (type pdf)
- <use graphe1.pdf>
-Package pdftex.def Info: graphe1.pdf used on input line 401.
-(pdftex.def) Requested size: 90.4383pt x 84.46596pt.
-
-<graphe2.pdf, id=74, 194.7275pt x 173.64874pt>
-File: graphe2.pdf Graphic file (type pdf)
- <use graphe2.pdf>
-Package pdftex.def Info: graphe2.pdf used on input line 409.
-(pdftex.def) Requested size: 165.51913pt x 147.60213pt.
-
-Overfull \hbox (58.82022pt too wide) in paragraph at lines 409--410
- [][]
- []
-
-[8]
-Overfull \hbox (8.8307pt too wide) in paragraph at lines 444--451
-[]\T1/cmr/m/n/10 Suppose that $\OT1/cmr/m/n/10 ^^@[](\OML/cmm/m/it/10 f\OT1/cmr
-/m/n/10 )$ \T1/cmr/m/n/10 is strongly con-nected. Let $\OML/cmm/m/it/10 x \OT1/
-cmr/m/n/10 = (\OML/cmm/m/it/10 e; \OT1/cmr/m/n/10 (\OML/cmm/m/it/10 u; v\OT1/cm
-r/m/n/10 ))\OML/cmm/m/it/10 ; [] \OT1/cmr/m/n/10 = ([]\OML/cmm/m/it/10 ; \OT1/c
-mr/m/n/10 ([]\OML/cmm/m/it/10 ; []\OT1/cmr/m/n/10 )) \OMS/cmsy/m/n/10 2
- []
-
-
-Underfull \hbox (badness 10000) in paragraph at lines 472--477
-[]\T1/cmr/m/n/10 Let $\OML/cmm/m/it/10 y \OT1/cmr/m/n/10 = (\OML/cmm/m/it/10 e;
- \OT1/cmr/m/n/10 ((\OML/cmm/m/it/10 u[]; :::; u[]; a[]; :::; a[]; a[]; :::; a[]
-; :::; a[]; :::; a[];$
- []
-
-[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 ;$
- []
-
-! Missing } inserted.
-<inserted text>
- }
-l.190 Since $a_{\mathsf{N}$
- is even, $d_{\mathsf{N}}$ is defined.
-?
-) (./stopping.tex [13] [14] [15] [16] [17]) (./prng.tex [18]
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 64.
-
-LaTeX Font Info: Font shape `OMS/cmr/m/n' in size <10> not available
-(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 64.
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 64.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 67.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 67.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 89.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 89.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 92.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 92.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 105.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 105.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 122.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 122.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 172.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 172.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 231.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 231.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 231.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 231.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 231.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 231.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 231.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 231.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 231.
-
-
-LaTeX Warning: Command \textcircled invalid in math mode on input line 231.
-
-
-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!
-) [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.
- []
-
-[21]) [22] (./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:
- 20136 strings out of 493304
- 370159 string characters out of 6139871
- 525134 words of memory out of 5000000
- 22909 multiletter control sequences out of 15000+600000
- 28957 words of font info for 91 fonts, out of 8000000 for 9000
- 1118 hyphenation exceptions out of 8191
- 48i,17n,75p,539b,695s stack positions out of 5000i,500n,10000p,200000b,80000s
-{/usr/share/texmf/fonts/enc/dvips/cm-super/cm-super-t1.enc}</us
-r/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmex10.pfb></usr/shar
-e/texlive/texmf-dist/fonts/type1/public/amsfonts/cmextra/cmex7.pfb></usr/share/
-texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmmi10.pfb></usr/share/texliv
-e/texmf-dist/fonts/type1/public/amsfonts/cm/cmmi12.pfb></usr/share/texlive/texm
-f-dist/fonts/type1/public/amsfonts/cm/cmmi5.pfb></usr/share/texlive/texmf-dist/
-fonts/type1/public/amsfonts/cm/cmmi6.pfb></usr/share/texlive/texmf-dist/fonts/t
-ype1/public/amsfonts/cm/cmmi7.pfb></usr/share/texlive/texmf-dist/fonts/type1/pu
-blic/amsfonts/cm/cmmi8.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/am
-sfonts/cm/cmmi9.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/
-cm/cmr10.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmr1
-2.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmr5.pfb></
-usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmr6.pfb></usr/shar
-e/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmr7.pfb></usr/share/texliv
-e/texmf-dist/fonts/type1/public/amsfonts/cm/cmr8.pfb></usr/share/texlive/texmf-
-dist/fonts/type1/public/amsfonts/cm/cmr9.pfb></usr/share/texlive/texmf-dist/fon
-ts/type1/public/amsfonts/cm/cmss10.pfb></usr/share/texlive/texmf-dist/fonts/typ
-e1/public/amsfonts/cm/cmss8.pfb></usr/share/texlive/texmf-dist/fonts/type1/publ
-ic/amsfonts/cm/cmsy10.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/ams
-fonts/cm/cmsy5.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/c
-m/cmsy6.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmsy7
-.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmsy8.pfb></
-usr/share/texlive/texmf-dist/fonts/type1/public/doublestroke/dsrom10.pfb></usr/
-share/texlive/texmf-dist/fonts/type1/public/doublestroke/dsrom8.pfb></usr/share
-/texlive/texmf-dist/fonts/type1/public/amsfonts/symbols/msam10.pfb></usr/share/
-texlive/texmf-dist/fonts/type1/public/amsfonts/symbols/msbm10.pfb></usr/share/t
-exlive/texmf-dist/fonts/type1/public/amsfonts/symbols/msbm7.pfb></usr/share/tex
-mf/fonts/type1/public/cm-super/sfbx0700.pfb></usr/share/texmf/fonts/type1/publi
-c/cm-super/sfbx1000.pfb></usr/share/texmf/fonts/type1/public/cm-super/sfbx1095.
-pfb></usr/share/texmf/fonts/type1/public/cm-super/sfcc0900.pfb></usr/share/texm
-f/fonts/type1/public/cm-super/sfcc1000.pfb></usr/share/texmf/fonts/type1/public
-/cm-super/sfcc1200.pfb></usr/share/texmf/fonts/type1/public/cm-super/sfrm0700.p
-fb></usr/share/texmf/fonts/type1/public/cm-super/sfrm0800.pfb></usr/share/texmf
-/fonts/type1/public/cm-super/sfrm0900.pfb></usr/share/texmf/fonts/type1/public/
-cm-super/sfrm1000.pfb></usr/share/texmf/fonts/type1/public/cm-super/sfrm1200.pf
-b></usr/share/texmf/fonts/type1/public/cm-super/sfti0700.pfb></usr/share/texmf/
-fonts/type1/public/cm-super/sfti0800.pfb></usr/share/texmf/fonts/type1/public/c
-m-super/sfti1000.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/stmaryrd
-/stmary10.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/stmaryrd/stmary
-7.pfb>
-Output written on main.pdf (22 pages, 615170 bytes).
-PDF statistics:
- 283 PDF objects out of 1000 (max. 8388607)
- 203 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)
-
\begin{document}
-\author{Jean-François Couchot, Christophe Guyeux, Pierre-Cyrille Heam}
-\address{FEMTO-ST Institute, University of Franche-Comté, Belfort, France}
+\author{Sylvain Contassot-Vivier, Jean-François Couchot, Christophe Guyeux, Pierre-Cyrille Heam}
+\address{LORIA, Université de Lorraine, Nancy, France\\
+FEMTO-ST Institute, University of Franche-Comté, Belfort, France}
-\keywords{Pseudorandom Number Generator, Theory of Chaos, Markov Matrice, Hamiltonian Path, Mixing Time, Stopping Time, Statistical Test}
+\keywords{Pseudorandom Number Generator, Theory of Chaos, Markov Matrice, Hamiltonian Path, Stopping Time, Statistical Test}
\subjclass{34C28, 37A25,11K45}
\section{Functions with Strongly Connected $\Gamma_{\{b\}}(f)$}\label{sec:SCCfunc}
\input{generating}
-\section{(Locally) Balanced Hamiltonian Cycle}\label{sec:hamilton}
+\section{Balanced Hamiltonian Cycle}\label{sec:hamilton}
\input{hamilton}
-With all this material, we can study the chaos properties of these
+
+Based on this setup,
+we can study the chaos properties of these
function.
This is the aims of the next section.
-
-
-
-Let thus be given such kind of map.
-This article focuses on studying its iterations according to
-the equation~(\ref{eq:asyn}) with a given strategy.
-First of all, this can be interpreted as walking into its iteration graph
-where the choice of the edge to follow is decided by the strategy.
+This section considers functions $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}} $
+issued from an hypercube where an Hamiltonian path has been removed
+as described in previous section.
Notice that the iteration graph is always a subgraph of
${\mathsf{N}}$-cube augmented with all the self-loop, \textit{i.e.}, all the
edges $(v,v)$ for any $v \in \Bool^{\mathsf{N}}$.
\end{xpl}
-% % Let us first recall the \emph{Total Variation} distance $\tv{\pi-\mu}$,
-% % which is defined for two distributions $\pi$ and $\mu$ on the same set
-% % $\Bool^n$ by:
-% % $$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$
-% % It is known that
-% % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$
-
-% % Let then $M(x,\cdot)$ be the
-% % distribution induced by the $x$-th row of $M$. If the Markov chain
-% % induced by
-% % $M$ has a stationary distribution $\pi$, then we define
-% % $$d(t)=\max_{x\in\Bool^n}\tv{M^t(x,\cdot)-\pi}.$$
-% Intuitively $d(t)$ is the largest deviation between
-% the distribution $\pi$ and $M^t(x,\cdot)$, which
-% is the result of iterating $t$ times the function.
-% Finally, let $\varepsilon$ be a positive number, the \emph{mixing time}
-% with respect to $\varepsilon$ is given by
-% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-% It defines the smallest iteration number
-% that is sufficient to obtain a deviation lesser than $\varepsilon$.
-% Notice that the upper and lower bounds of mixing times cannot
-% directly be computed with eigenvalues formulae as expressed
-% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work
-% only consider reversible Markov matrices whereas we do no restrict our
-% matrices to such a form.
-
-
-
-
-
-
-
-This section considers functions $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}} $
-issued from an hypercube where an Hamiltonian path has been removed.
A specific random walk in this modified hypercube is first
-introduced. We further detail
-a theoretical study on the length of the path
-which is sufficient to follow to get a uniform distribution.
+introduced (See section~\ref{sub:stop:formal}). We further
+theoretical study this random walk to
+provide a upper bound of fair sequences
+(See section~\ref{sub:stop:bound}).
+We finally complete these study with experimental
+results that reduce this bound (Sec.~\ref{sub:stop:stop}).
Notice that for a general references on Markov chains
-see~\cite{LevinPeresWilmer2006}
-, and particularly Chapter~5 on stopping times.
-
+see~\cite{LevinPeresWilmer2006},
+and particularly Chapter~5 on stopping times.
+\subsection{Formalizing the Random Walk}\label{sub:stop:formal}
First of all, let $\pi$, $\mu$ be two distributions on $\Bool^{\mathsf{N}}$. The total
variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is
and
$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
+
+Intuitively speaking, $t_{\rm mix}$ is a mixing time
+\textit{i.e.}, is the time until the matrix $X$ of a Markov chain
+is $\epsilon$-close to a stationary distribution.
+
+
+
One can prove that
$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
% It is known that $d(t+1)\leq d(t)$. \JFC{references ? Cela a-t-il
-% un intérêt dans la preuve ensuite.}
+% un intérêt dans la preuve ensuite.}
%and
% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-% One can prove that \JFc{Ou cela a-t-il été fait?}
+% One can prove that \JFc{Ou cela a-t-il été fait?}
% $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$
such that the distribution of $X_\tau$ is $\pi$:
$$\P_X(X_\tau=Y)=\pi(Y).$$
+\subsection{Upper bound of Stopping Time}\label{sub:stop:bound}
+
+
A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is
independent of $\tau$.
-%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
+%%%%%%%%%%%%%%%%%%%%%%%%%%%ù
%\section{Stopping time}
An integer $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ is said {\it fair}
$\frac{1}{2}$. Since $h(X_{\tau_\ell-1})\neq\ell$ the value of the $\ell$-th
bit of $X_{\tau_\ell}$
is $0$ or $1$ with the same probability ($\frac{1}{2}$).
+This probability is independent of the value of the other bits.
+
+
- Moving next in the chain, at each step,
+Moving next in the chain, at each step,
the $l$-th bit is switched from $0$ to $1$ or from $1$ to $0$ each time with
the same probability. Therefore, for $t\geq \tau_\ell$, the
$\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the
under the following constraint: for each vertex in the $\mathsf{N}$-cube
there are one ongoing arc and one outgoing arc that are removed.
The calculus does not consider (balanced) Hamiltonian cycles, which
-are more regular and more binding than this constraint. Moreover, the bound
+are more regular and more binding than this constraint.
+Moreover, the bound
is obtained using Markov Inequality which is frequently coarse. For the
classical random walkin the $\mathsf{N}$-cube, without removing any
Hamiltonian cylce, the mixing time is in $\Theta(N\ln N)$.
We conjecture that in our context, the mixing time is also in $\Theta(N\ln
-N)$.
-%In this later context, we claim that the upper bound for the stopping time
-%should be reduced.
+N)$.
+
+
+In this later context, we claim that the upper bound for the stopping time
+should be reduced. This fact is studied in the next section.
+
+\subsection{Practical Evaluation of Stopping Times}\label{sub:stop:exp}
+
+Let be given a function $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$
+and an initial seed $x^0$.
+The pseudo code given in algorithm~\ref{algo:stop} returns the smallest
+number of iterations such that all elements $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ are fair. It allows to deduce an approximation of $E[\ts]$
+by calling this code many times with many instances of function and many
+seeds.
+
+Practically speaking, for each number $\mathsf{N}$,$ 3 \le \mathsf{N} \le 16$,
+10 functions have been generaed according to method presented in section~\ref{sec:hamilton}. For each of them, the calculus of the approximation of $E[\ts]$
+is executed 10000 times with a random seed. The table~\ref{table:stopping:moy}
+summarizes results. It can be observed that the approximation is largely
+wœsmaller than the upper bound given in theorem~\ref{prop:stop}.
+
+\begin{algorithm}[ht]
+%\begin{scriptsize}
+\KwIn{a function $f$, an initial configuration $x^0$ ($\mathsf{N}$ bits)}
+\KwOut{a number of iterations $\textit{nbit}$}
+
+$\textit{nbit} \leftarrow 0$\;
+$x\leftarrow x^0$\;
+$\textit{visited}\leftarrow\emptyset$\;
+
+\While{$\left\vert{\textit{visited}}\right\vert < \mathsf{N} $}
+{
+ $ s \leftarrow \textit{Random}(n)$ \;
+ $\textit{image} \leftarrow f(x) $\;
+ \If{$x[s] \neq \textit{image}[s]$}{
+ $\textit{visited} \leftarrow \textit{visited} \cup \{s\}$
+ }
+ $x[s] \leftarrow \textit{image}[s]$\;
+ $\textit{nbit} \leftarrow \textit{nbit}+1$\;
+}
+\Return{$\textit{nbit}$}\;
+%\end{scriptsize}
+\caption{Pseudo Code of the stoping time calculus}
+\label{algo:stop}
+\end{algorithm}
+
+
+
+
+\begin{table}
+$$
+\begin{array}{|*{15}{l|}}
+\hline
+\mathsf{N} & 3 & 4 & 5 & 6 & 7& 8 & 9 & 10& 11 & 12 & 13 & 14 & 15 & 16 \\
+\hline
+\mathsf{N} & 3 & 10.9 & 5 & 17.7 & 7& 25 & 9 & 32.7& 11 & 40.8 & 13 & 49.2 & 15 & 16 \\
+\hline
+\end{array}
+$$
+\caption{Average Stopping Time}\label{table:stopping:moy}
+\end{table}
