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.
\@writefile{toc}{\contentsline {section}{\tocsection {}{1}{Introduction}}{1}}
\citation{guyeuxTaiwan10,bcgr11:ip}
\citation{wbg10ip}
-\citation{chgw14oip}
+\citation{DBLP:conf/secrypt/CouchotHGWB14}
+\citation{bcgr11:ip}
\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{DBLP:conf/secrypt/CouchotHGWB14}
\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{CI Algorithm}{{1}{4}}
\@writefile{toc}{\contentsline {section}{\tocsection {}{3}{Proof Of Chaos}}{4}}
\newlabel{sec:proofOfChaos}{{3}{4}}
+\citation{bcgr11:ip}
\citation{Devaney}
\citation{Banks92}
\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{3.1}{Devaney's Chaotic Dynamical Systems}}{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}}
-\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{3.5}{Proofs of chaos}}{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}
+\@writefile{toc}{\contentsline {section}{\tocsection {}{4}{Functions with Strongly Connected $\Gamma _{\{b\}}(f)$}}{11}}
+\newlabel{sec:SCCfunc}{{4}{11}}
+\@writefile{toc}{\contentsline {section}{\tocsection {}{5}{Balanced Hamiltonian Cycle}}{11}}
+\newlabel{sec:hamilton}{{5}{11}}
\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{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}}{12}}
+\citation{ZanSup04}
+\newlabel{item:u'}{{2}{13}}
+\newlabel{item:VW}{{3}{13}}
+\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{5.2}{Balanced Codes}}{13}}
\newlabel{prop:balanced}{{5.1}{13}}
-\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{5.3}{Toward a local uniform distribution of switches}}{13}}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{6}{Stopping Time}}{13}}
-\newlabel{sec:hypercube}{{6}{13}}
+\newlabel{eq:sys:zt1}{{3}{14}}
+\newlabel{eq:sys:zt2}{{4}{14}}
+\newlabel{eq:TCN:def}{{5}{15}}
+\@writefile{toc}{\contentsline {section}{\tocsection {}{6}{Stopping Time}}{15}}
+\newlabel{sec:hypercube}{{6}{15}}
\citation{LevinPeresWilmer2006}
-\newlabel{eq:Markov:rairo}{{3}{15}}
-\newlabel{lm:h}{{6.2}{15}}
+\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{6.1}{Formalizing the Random Walk}}{16}}
+\newlabel{sub:stop:formal}{{6.1}{16}}
+\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{6.2}{Upper bound of Stopping Time}}{17}}
+\newlabel{sub:stop:bound}{{6.2}{17}}
+\newlabel{eq:Markov:rairo}{{6}{17}}
+\newlabel{lm:h}{{6.2}{17}}
+\newlabel{prop:stop}{{6.4}{18}}
+\newlabel{prop:lambda}{{6.5}{18}}
\citation{proba}
-\newlabel{prop:stop}{{6.4}{16}}
-\newlabel{prop:lambda}{{6.5}{16}}
-\newlabel{lm:stopprime}{{6.6}{17}}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{7}{Experiments}}{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{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Functions with DSCC Matrix and smallest MT\relax }}{19}}
-\newlabel{table:nc}{{1}{19}}
+\newlabel{lm:stopprime}{{6.6}{19}}
+\@writefile{toc}{\contentsline {subsection}{\tocsubsection {}{6.3}{Practical Evaluation of Stopping Times}}{20}}
+\newlabel{sub:stop:exp}{{6.3}{20}}
+\@writefile{loa}{\contentsline {algocf}{\numberline {2}{\ignorespaces Pseudo Code of the stoping time calculus\relax }}{20}}
+\newlabel{algo:stop}{{2}{20}}
+\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces Average Stopping Time\relax }}{21}}
+\newlabel{table:stopping:moy}{{1}{21}}
+\@writefile{toc}{\contentsline {section}{\tocsection {}{7}{Experiments}}{21}}
+\newlabel{sec:prng}{{7}{21}}
+\@writefile{loa}{\contentsline {algocf}{\numberline {3}{\ignorespaces Pseudo Code of the $\chi _{\textit {15Rairo}}$ PRNG\relax }}{21}}
+\newlabel{CI Algorithm:2}{{3}{21}}
+\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces Functions with DSCC Matrix and smallest MT\relax }}{22}}
+\newlabel{table:nc}{{2}{22}}
\bibstyle{alpha}
\bibdata{biblio}
\bibcite{Banks92}{BBCS92}
-\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces NIST SP 800-22 test results ($\mathbb {P}_T$)\relax }}{20}}
-\newlabel{The passing rate}{{2}{20}}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{8}{Conclusion}}{20}}
+\@writefile{lot}{\contentsline {table}{\numberline {3}{\ignorespaces NIST SP 800-22 test results ($\mathbb {P}_T$)\relax }}{23}}
+\newlabel{The passing rate}{{3}{23}}
+\@writefile{toc}{\contentsline {section}{\tocsection {}{8}{Conclusion}}{23}}
\bibcite{bcgr11:ip}{BCGR11}
\bibcite{Nist10}{BR10}
\bibcite{DBLP:journals/combinatorics/BhatS96}{BS96}
\bibcite{Bykov2016}{Byk16}
-\bibcite{chgw14oip}{CHG{$^{+}$}14a}
-\bibcite{DBLP:conf/secrypt/CouchotHGWB14}{CHG{$^{+}$}14b}
+\bibcite{DBLP:conf/secrypt/CouchotHGWB14}{CHG{$^{+}$}14}
\bibcite{5376454}{CMZ09}
\bibcite{Devaney}{Dev89}
\bibcite{guyeuxTaiwan10}{GWB10}
\bibcite{915396}{SPK01}
\bibcite{ZanSup04}{SZ04}
\bibcite{wbg10ip}{WBGF10}
-\@writefile{toc}{\contentsline {section}{\tocsection {}{}{References}}{21}}
\newlabel{tocindent-1}{0pt}
\newlabel{tocindent0}{12.77466pt}
\newlabel{tocindent1}{17.77344pt}
\newlabel{tocindent2}{25.54932pt}
\newlabel{tocindent3}{0pt}
+\@writefile{toc}{\contentsline {section}{\tocsection {}{}{References}}{24}}
\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.
-This is BibTeX, Version 0.99d (TeX Live 2015/dev/Debian)
+This is BibTeX, Version 0.99d (TeX Live 2015/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,
+You've used 18 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
+ 690 strings with 7823 characters,
+and the built_in function-call counts, 7931 in all, are:
+= -- 798
+> -- 396
+< -- 11
++ -- 138
+- -- 136
+* -- 586
+:= -- 1285
+add.period$ -- 58
+call.type$ -- 18
+change.case$ -- 116
chr.to.int$ -- 18
-cite$ -- 19
-duplicate$ -- 338
-empty$ -- 604
-format.name$ -- 169
-if$ -- 1790
-int.to.chr$ -- 2
+cite$ -- 18
+duplicate$ -- 312
+empty$ -- 562
+format.name$ -- 156
+if$ -- 1651
+int.to.chr$ -- 1
int.to.str$ -- 0
-missing$ -- 21
-newline$ -- 100
-num.names$ -- 59
-pop$ -- 119
+missing$ -- 20
+newline$ -- 94
+num.names$ -- 56
+pop$ -- 109
preamble$ -- 1
-purify$ -- 146
+purify$ -- 136
quote$ -- 0
-skip$ -- 299
+skip$ -- 279
stack$ -- 0
-substring$ -- 463
-swap$ -- 80
-text.length$ -- 12
+substring$ -- 424
+swap$ -- 70
+text.length$ -- 11
text.prefix$ -- 3
top$ -- 0
-type$ -- 140
+type$ -- 132
warning$ -- 0
-while$ -- 80
-width$ -- 21
-write$ -- 259
+while$ -- 74
+width$ -- 19
+write$ -- 243
-This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2015/dev/Debian) (preloaded format=pdflatex 2015.4.13) 7 APR 2016 20:24
+This is pdfTeX, Version 3.14159265-2.6-1.40.16 (TeX Live 2015/Debian) (preloaded format=pdflatex 2016.5.31) 22 JUN 2016 11:08
entering extended mode
restricted \write18 enabled.
%&-line parsing enabled.
**main.tex
(./main.tex
-LaTeX2e <2014/05/01>
-Babel <3.9l> and hyphenation patterns for 79 languages loaded.
+LaTeX2e <2016/02/01>
+Babel <3.9q> and hyphenation patterns for 5 language(s) 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
+Document Class: amsart 2015/03/04 v2.20.2
\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
+Package: amsmath 2016/03/03 v2.15a 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
+Package: amstext 2000/06/29 v2.01 AMS text
(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsgen.sty
-File: amsgen.sty 1999/11/30 v2.0
+File: amsgen.sty 1999/11/30 v2.0 generic functions
\@emptytoks=\toks14
\ex@=\dimen104
))
(/usr/share/texlive/texmf-dist/tex/latex/amsmath/amsbsy.sty
-Package: amsbsy 1999/11/29 v1.2d
+Package: amsbsy 1999/11/29 v1.2d Bold Symbols
\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.
+LaTeX Info: Redefining \frac on input line 199.
\uproot@=\count80
\leftroot@=\count81
-LaTeX Info: Redefining \overline on input line 306.
+LaTeX Info: Redefining \overline on input line 297.
\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.
+LaTeX Info: Redefining \ldots on input line 394.
+LaTeX Info: Redefining \dots on input line 397.
+LaTeX Info: Redefining \cdots on input line 518.
\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.
+LaTeX Font Info: Redeclaring font encoding OML on input line 630.
+LaTeX Font Info: Redeclaring font encoding OMS on input line 631.
\macc@depth=\count84
\c@MaxMatrixCols=\count85
\dotsspace@=\muskip10
\multlinegap=\skip43
\multlinetaggap=\skip44
\mathdisplay@stack=\toks18
-LaTeX Info: Redefining \[ on input line 2665.
-LaTeX Info: Redefining \] on input line 2666.
+LaTeX Info: Redefining \[ on input line 2735.
+LaTeX Info: Redefining \] on input line 2736.
)
LaTeX Font Info: Try loading font information for U+msa on input line 388.
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
+\copyins=\insert199
\abstractbox=\box28
\listisep=\skip45
\c@part=\count91
)
(/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
+LaTeX Info: Redefining \nocite on input line 332.
+Package: cite 2015/02/27 v 5.5
)
\@b@rnngttl=\box29
\@b@rnngthr=\box30
\c@thrm=\count104
)
(/usr/share/texlive/texmf-dist/tex/latex/graphics/graphicx.sty
-Package: graphicx 2014/04/25 v1.0g Enhanced LaTeX Graphics (DPC,SPQR)
+Package: graphicx 2014/10/28 v1.0g Enhanced LaTeX Graphics (DPC,SPQR)
(/usr/share/texlive/texmf-dist/tex/latex/graphics/keyval.sty
-Package: keyval 2014/05/08 v1.15 key=value parser (DPC)
+Package: keyval 2014/10/28 v1.15 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)
+Package: graphics 2016/01/03 v1.0q 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)
+Package: trig 2016/01/03 v1.10 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.
+Package graphics Info: Driver file: pdftex.def on input line 95.
(/usr/share/texlive/texmf-dist/tex/latex/pdftex-def/pdftex.def
File: pdftex.def 2011/05/27 v0.06d Graphics/color for pdfTeX
\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)
+Package: caption 2016/02/21 v3.3-144 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.
+Package: caption3 2016/02/04 v1.7-139 caption3 kernel (AR)
+Package caption3 Info: TeX engine: e-TeX on input line 67.
\captionmargin=\dimen116
\captionmargin@=\dimen117
\captionwidth=\dimen118
\c@ContinuedFloat=\count106
)
(/usr/share/texlive/texmf-dist/tex/latex/caption/subcaption.sty
-Package: subcaption 2013/02/03 v1.1-62 Sub-captions (AR)
+Package: subcaption 2016/02/20 v1.1-142 Sub-captions (AR)
\c@subfigure=\count107
\c@subtable=\count108
)
Package: ifthen 2014/09/29 v1.1c Standard LaTeX ifthen package (DPC)
)
(/usr/share/texlive/texmf-dist/tex/latex/graphics/color.sty
-Package: color 2014/04/23 v1.1a Standard LaTeX Color (DPC)
+Package: color 2016/01/03 v1.1b 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 137.
+Package color Info: Driver file: pdftex.def on input line 143.
)
(/usr/share/texlive/texmf-dist/tex/latex/algorithm2e/algorithm2e.sty
Package: algorithm2e 2013/01/06 v5.00 algorithms environments
\c@AlgoLine=\count109
+\algocf@hangindent=\skip51
(/usr/share/texlive/texmf-dist/tex/latex/tools/xspace.sty
Package: xspace 2014/10/28 v1.13 Space after command names (DPC,MH)
LaTeX Info: Redefining \smaller on input line 151.
)
********************************************************
-Package `algorithm2e' Release 5.0 -- january 06 2013 --
+Package `algorithm2e' Release 5.1 -- october 19 2015 --
- 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)
+- Author: Christophe Fiorio (christophe.fiorio@umontpellier.fr)
********************************************************
-\skiptotal=\skip51
-\skiplinenumber=\skip52
-\skiprule=\skip53
-\skiphlne=\skip54
-\skiptext=\skip55
-\skiplength=\skip56
-\algomargin=\skip57
-\skipalgocfslide=\skip58
+\skiptotal=\skip52
+\skiplinenumber=\skip53
+\skiprule=\skip54
+\skiphlne=\skip55
+\skiptext=\skip56
+\skiplength=\skip57
+\algomargin=\skip58
+\skipalgocfslide=\skip59
\algowidth=\dimen123
\inoutsize=\dimen124
\inoutindent=\dimen125
\interspacetitleruled=\dimen126
\interspacealgoruled=\dimen127
\interspacetitleboxruled=\dimen128
+\algocf@ruledwidth=\skip60
\algocf@inoutbox=\box36
\algocf@inputbox=\box37
-\AlCapSkip=\skip59
-\AlCapHSkip=\skip60
-\algoskipindent=\skip61
+\AlCapSkip=\skip61
+\AlCapHSkip=\skip62
+\algoskipindent=\skip63
\algocf@nlbox=\box38
\algocf@hangingbox=\box39
\algocf@untilbox=\box40
-\algocf@skipuntil=\skip62
+\algocf@skipuntil=\skip64
\algocf@capbox=\box41
-\algoheightruledefault=\skip63
-\algoheightrule=\skip64
-\algotitleheightruledefault=\skip65
-\algotitleheightrule=\skip66
+\algoheightruledefault=\skip65
+\algoheightrule=\skip66
+\algotitleheightruledefault=\skip67
+\algotitleheightrule=\skip68
\c@algocfline=\count110
\c@algocfproc=\count111
\c@algocf=\count112
e
)))
(/usr/share/texlive/texmf-dist/tex/latex/base/inputenc.sty
-Package: inputenc 2014/04/30 v1.2b Input encoding file
+Package: inputenc 2015/03/17 v1.2c Input encoding file
\inpenc@prehook=\toks26
\inpenc@posthook=\toks27
(/usr/share/texlive/texmf-dist/tex/latex/base/utf8.def
-File: utf8.def 2014/09/29 v1.1m UTF-8 support for inputenc
+File: utf8.def 2015/12/03 v1.1r 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 2014/09/29 v1.1m UTF-8 support for inputenc
+File: t1enc.dfu 2015/12/03 v1.1r UTF-8 support for inputenc
+ defining Unicode char U+00A0 (decimal 160)
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+00AD (decimal 173)
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+00FD (decimal 253)
defining Unicode char U+00FE (decimal 254)
defining Unicode char U+00FF (decimal 255)
+ defining Unicode char U+0100 (decimal 256)
+ defining Unicode char U+0101 (decimal 257)
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+0108 (decimal 264)
+ defining Unicode char U+0109 (decimal 265)
+ defining Unicode char U+010A (decimal 266)
+ defining Unicode char U+010B (decimal 267)
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+0112 (decimal 274)
+ defining Unicode char U+0113 (decimal 275)
+ defining Unicode char U+0114 (decimal 276)
+ defining Unicode char U+0115 (decimal 277)
+ defining Unicode char U+0116 (decimal 278)
+ defining Unicode char U+0117 (decimal 279)
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+011C (decimal 284)
+ defining Unicode char U+011D (decimal 285)
defining Unicode char U+011E (decimal 286)
defining Unicode char U+011F (decimal 287)
+ defining Unicode char U+0120 (decimal 288)
+ defining Unicode char U+0121 (decimal 289)
+ defining Unicode char U+0122 (decimal 290)
+ defining Unicode char U+0123 (decimal 291)
+ defining Unicode char U+0124 (decimal 292)
+ defining Unicode char U+0125 (decimal 293)
+ defining Unicode char U+0128 (decimal 296)
+ defining Unicode char U+0129 (decimal 297)
+ defining Unicode char U+012A (decimal 298)
+ defining Unicode char U+012B (decimal 299)
+ defining Unicode char U+012C (decimal 300)
+ defining Unicode char U+012D (decimal 301)
+ defining Unicode char U+012E (decimal 302)
+ defining Unicode char U+012F (decimal 303)
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+0134 (decimal 308)
+ defining Unicode char U+0135 (decimal 309)
+ defining Unicode char U+0136 (decimal 310)
+ defining Unicode char U+0137 (decimal 311)
defining Unicode char U+0139 (decimal 313)
defining Unicode char U+013A (decimal 314)
+ defining Unicode char U+013B (decimal 315)
+ defining Unicode char U+013C (decimal 316)
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+0145 (decimal 325)
+ defining Unicode char U+0146 (decimal 326)
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+014C (decimal 332)
+ defining Unicode char U+014D (decimal 333)
+ defining Unicode char U+014E (decimal 334)
+ defining Unicode char U+014F (decimal 335)
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+0156 (decimal 342)
+ defining Unicode char U+0157 (decimal 343)
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+015C (decimal 348)
+ defining Unicode char U+015D (decimal 349)
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+0163 (decimal 355)
defining Unicode char U+0164 (decimal 356)
defining Unicode char U+0165 (decimal 357)
+ defining Unicode char U+0168 (decimal 360)
+ defining Unicode char U+0169 (decimal 361)
+ defining Unicode char U+016A (decimal 362)
+ defining Unicode char U+016B (decimal 363)
+ defining Unicode char U+016C (decimal 364)
+ defining Unicode char U+016D (decimal 365)
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+0172 (decimal 370)
+ defining Unicode char U+0173 (decimal 371)
+ defining Unicode char U+0174 (decimal 372)
+ defining Unicode char U+0175 (decimal 373)
+ defining Unicode char U+0176 (decimal 374)
+ defining Unicode char U+0177 (decimal 375)
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+017C (decimal 380)
defining Unicode char U+017D (decimal 381)
defining Unicode char U+017E (decimal 382)
+ defining Unicode char U+01CD (decimal 461)
+ defining Unicode char U+01CE (decimal 462)
+ defining Unicode char U+01CF (decimal 463)
+ defining Unicode char U+01D0 (decimal 464)
+ defining Unicode char U+01D1 (decimal 465)
+ defining Unicode char U+01D2 (decimal 466)
+ defining Unicode char U+01D3 (decimal 467)
+ defining Unicode char U+01D4 (decimal 468)
+ defining Unicode char U+01E2 (decimal 482)
+ defining Unicode char U+01E3 (decimal 483)
+ defining Unicode char U+01E6 (decimal 486)
+ defining Unicode char U+01E7 (decimal 487)
+ defining Unicode char U+01E8 (decimal 488)
+ defining Unicode char U+01E9 (decimal 489)
+ defining Unicode char U+01EA (decimal 490)
+ defining Unicode char U+01EB (decimal 491)
+ defining Unicode char U+01F0 (decimal 496)
+ defining Unicode char U+01F4 (decimal 500)
+ defining Unicode char U+01F5 (decimal 501)
+ defining Unicode char U+0218 (decimal 536)
+ defining Unicode char U+0219 (decimal 537)
+ defining Unicode char U+021A (decimal 538)
+ defining Unicode char U+021B (decimal 539)
+ defining Unicode char U+01E02 (decimal 7682)
+ defining Unicode char U+01E03 (decimal 7683)
defining Unicode char U+200C (decimal 8204)
defining Unicode char U+2013 (decimal 8211)
defining Unicode char U+2014 (decimal 8212)
... processing UTF-8 mapping file for font encoding OT1
(/usr/share/texlive/texmf-dist/tex/latex/base/ot1enc.dfu
-File: ot1enc.dfu 2014/09/29 v1.1m UTF-8 support for inputenc
+File: ot1enc.dfu 2015/12/03 v1.1r UTF-8 support for inputenc
+ defining Unicode char U+00A0 (decimal 160)
defining Unicode char U+00A1 (decimal 161)
defining Unicode char U+00A3 (decimal 163)
+ defining Unicode char U+00AD (decimal 173)
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+0142 (decimal 322)
defining Unicode char U+0152 (decimal 338)
defining Unicode char U+0153 (decimal 339)
+ defining Unicode char U+0174 (decimal 372)
+ defining Unicode char U+0175 (decimal 373)
+ defining Unicode char U+0176 (decimal 374)
+ defining Unicode char U+0177 (decimal 375)
+ defining Unicode char U+0218 (decimal 536)
+ defining Unicode char U+0219 (decimal 537)
+ defining Unicode char U+021A (decimal 538)
+ defining Unicode char U+021B (decimal 539)
defining Unicode char U+2013 (decimal 8211)
defining Unicode char U+2014 (decimal 8212)
defining Unicode char U+2018 (decimal 8216)
... processing UTF-8 mapping file for font encoding OMS
(/usr/share/texlive/texmf-dist/tex/latex/base/omsenc.dfu
-File: omsenc.dfu 2014/09/29 v1.1m UTF-8 support for inputenc
+File: omsenc.dfu 2015/12/03 v1.1r 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)
(/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.
+LaTeX Font Info: Redeclaring font encoding T1 on input line 48.
))
(/usr/share/texlive/texmf-dist/tex/generic/babel/babel.sty
-Package: babel 2014/09/25 3.9l The Babel package
+Package: babel 2016/02/24 3.9q 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 2014/09/25 3.9l Babel common definitions
+File: babel.def 2016/02/24 3.9q Babel common definitions
\babel@savecnt=\count113
\U@D=\dimen129
)
+\l@british = a dialect from \language\l@english
+\l@UKenglish = a dialect from \language\l@english
\l@canadian = a dialect from \language\l@american
\l@australian = a dialect from \language\l@british
\l@newzealand = a dialect from \language\l@british
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.
+(Font) U/lasy/m/n --> U/lasy/b/n on input line 52.
)
(/usr/share/texlive/texmf-dist/tex/latex/amsfonts/eufrak.sty
(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)
+Package: pstricks 2015/11/14 v0.62 LaTeX wrapper for `PSTricks' (RN,HV)
+(/usr/share/texlive/texmf-dist/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/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 2014/05/25 v2.7 package option processing (HA)
+Package: xkeyval 2014/12/03 v2.7a package option processing (HA)
(/usr/share/texlive/texmf-dist/tex/generic/xkeyval/xkeyval.tex
(/usr/share/texlive/texmf-dist/tex/generic/xkeyval/xkvutils.tex
\XKV@tempa@toks=\toks29
)
\XKV@depth=\count114
-File: xkeyval.tex 2014/05/25 v2.7 key=value parser (HA)
+File: xkeyval.tex 2014/12/03 v2.7a key=value parser (HA)
)))
(/usr/share/texlive/texmf-dist/tex/generic/pstricks/pst-fp.tex
`pst-fp' v0.05, 2010/01/17 (hv)
)
\psLoopIndex=\count132
-`PSTricks' v2.57 <2014/08/27> (tvz)
+`PSTricks' v2.64b <2015/14/11> (tvz)
\pst@dima=\dimen143
\pst@dimb=\dimen144
\pst@dimc=\dimen145
\sh@wgridYunit=\dimen166
\pst@shift=\dimen167
)
-File: pstricks.tex 2014/08/27 v2.57 `PSTricks' (tvz,hv)
+File: pstricks.tex 2015/14/11 v2.64b `PSTricks' (tvz,hv)
(/usr/share/texlive/texmf-dist/tex/generic/pstricks/pst-fp.tex)
-File: pst-fp.tex 2014/08/27 v2.57 `PST-fp' (hv)
-
-(/usr/share/texlive/texmf-dist/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
+File: pst-fp.tex 2015/14/11 v2.64b `PST-fp' (hv)
)
-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
\psrow=\count145
\pscol=\count146
\psmatrixcnt=\count147
-\psrowsep=\skip67
-\pscolsep=\skip68
+\psrowsep=\skip69
+\pscolsep=\skip70
\pst@args=\count148
\num@pts=\count149
\pst@argcnt=\count150
(/usr/share/texlive/texmf-dist/tex/generic/pst-coil/pst-coil.tex
v1.35, 2014/08/04
(/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)
+File: pst-coil.tex 2015/05/13 v1.07 `PST-coil' (tvz,hv)
)
(/usr/share/texlive/texmf-dist/tex/latex/url/url.sty
\Urlmuskip=\muskip11
Package: everyshi 2001/05/15 v3.00 EveryShipout Package (MS)
))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfrcs.code.tex
-Package: pgfrcs 2013/12/20 v3.0.0 (rcs-revision 1.28)
+Package: pgfrcs 2015/08/07 v3.0.1a (rcs-revision 1.31)
))
-Package: pgf 2013/12/18 v3.0.0 (rcs-revision 1.14)
+Package: pgf 2015/08/07 v3.0.1a (rcs-revision 1.15)
(/usr/share/texlive/texmf-dist/tex/latex/pgf/basiclayer/pgfcore.sty
(/usr/share/texlive/texmf-dist/tex/latex/pgf/systemlayer/pgfsys.sty
(/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgfsys.code.tex
-Package: pgfsys 2013/11/30 v3.0.0 (rcs-revision 1.47)
+Package: pgfsys 2014/07/09 v3.0.1a (rcs-revision 1.48)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfkeys.code.tex)
\pgf@x=\dimen170
Driver file for pgf: pgfsys-pdftex.def
(/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgfsys-pdftex.def
-File: pgfsys-pdftex.def 2013/07/18 (rcs-revision 1.33)
+File: pgfsys-pdftex.def 2014/10/11 (rcs-revision 1.35)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/systemlayer/pgfsys-common-pdf.de
f
File: pgfsysprotocol.code.tex 2006/10/16 (rcs-revision 1.4)
))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcore.code.tex
-Package: pgfcore 2010/04/11 v3.0.0 (rcs-revision 1.7)
+Package: pgfcore 2010/04/11 v3.0.1a (rcs-revision 1.7)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmath.code.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepoints.code.te
)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathusage.code
.tex
-File: pgfcorepathusage.code.tex 2013/12/13 (rcs-revision 1.23)
+File: pgfcorepathusage.code.tex 2014/11/02 (rcs-revision 1.24)
\pgf@shorten@end@additional=\dimen194
\pgf@shorten@start@additional=\dimen195
)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorescopes.code.te
x
-File: pgfcorescopes.code.tex 2013/10/09 (rcs-revision 1.44)
+File: pgfcorescopes.code.tex 2015/05/08 (rcs-revision 1.46)
\pgfpic=\box49
\pgf@hbox=\box50
\pgf@layerbox@main=\box51
)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoregraphicstate.c
ode.tex
-File: pgfcoregraphicstate.code.tex 2013/09/19 (rcs-revision 1.11)
+File: pgfcoregraphicstate.code.tex 2014/11/02 (rcs-revision 1.12)
\pgflinewidth=\dimen196
)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoretransformation
s.code.tex
-File: pgfcoretransformations.code.tex 2013/10/10 (rcs-revision 1.17)
+File: pgfcoretransformations.code.tex 2015/08/07 (rcs-revision 1.20)
\pgf@pt@x=\dimen197
\pgf@pt@y=\dimen198
-\pgf@pt@temp=\dimen199
+\pgf@pt@temp=\dimen256
)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorequick.code.tex
File: pgfcorequick.code.tex 2008/10/09 (rcs-revision 1.3)
)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorearrows.code.te
x
-File: pgfcorearrows.code.tex 2013/11/07 (rcs-revision 1.40)
-\pgfarrowsep=\dimen200
+File: pgfcorearrows.code.tex 2015/05/14 (rcs-revision 1.43)
+\pgfarrowsep=\dimen257
)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreshade.code.tex
File: pgfcoreshade.code.tex 2013/07/15 (rcs-revision 1.15)
-\pgf@max=\dimen201
+\pgf@max=\dimen258
\pgf@sys@shading@range@num=\count158
)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreimage.code.tex
(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreexternal.code.
tex
-File: pgfcoreexternal.code.tex 2013/07/15 (rcs-revision 1.20)
+File: pgfcoreexternal.code.tex 2014/07/09 (rcs-revision 1.21)
\pgfexternal@startupbox=\box52
))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/basiclayer/pgfcorelayers.code.te
File: pgfcorepatterns.code.tex 2013/11/07 (rcs-revision 1.5)
)))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/modules/pgfmoduleshapes.code.tex
-File: pgfmoduleshapes.code.tex 2013/10/31 (rcs-revision 1.34)
+File: pgfmoduleshapes.code.tex 2014/03/21 (rcs-revision 1.35)
\pgfnodeparttextbox=\box53
) (/usr/share/texlive/texmf-dist/tex/generic/pgf/modules/pgfmoduleplot.code.tex
-File: pgfmoduleplot.code.tex 2013/07/31 (rcs-revision 1.12)
+File: pgfmoduleplot.code.tex 2015/08/03 (rcs-revision 1.13)
)
(/usr/share/texlive/texmf-dist/tex/latex/pgf/compatibility/pgfcomp-version-0-65
.sty
-Package: pgfcomp-version-0-65 2007/07/03 v3.0.0 (rcs-revision 1.7)
-\pgf@nodesepstart=\dimen202
-\pgf@nodesepend=\dimen203
+Package: pgfcomp-version-0-65 2007/07/03 v3.0.1a (rcs-revision 1.7)
+\pgf@nodesepstart=\dimen259
+\pgf@nodesepend=\dimen260
)
(/usr/share/texlive/texmf-dist/tex/latex/pgf/compatibility/pgfcomp-version-1-18
.sty
-Package: pgfcomp-version-1-18 2007/07/23 v3.0.0 (rcs-revision 1.1)
+Package: pgfcomp-version-1-18 2007/07/23 v3.0.1a (rcs-revision 1.1)
)) (/usr/share/texlive/texmf-dist/tex/latex/pgf/utilities/pgffor.sty
(/usr/share/texlive/texmf-dist/tex/latex/pgf/utilities/pgfkeys.sty
(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgfkeys.code.tex))
(/usr/share/texlive/texmf-dist/tex/latex/pgf/math/pgfmath.sty
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmath.code.tex))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/utilities/pgffor.code.tex
-Package: pgffor 2013/12/13 v3.0.0 (rcs-revision 1.25)
+Package: pgffor 2013/12/13 v3.0.1a (rcs-revision 1.25)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/math/pgfmath.code.tex)
-\pgffor@iter=\dimen204
-\pgffor@skip=\dimen205
+\pgffor@iter=\dimen261
+\pgffor@skip=\dimen262
\pgffor@stack=\toks46
\pgffor@toks=\toks47
))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/tikz.code.tex
-Package: tikz 2013/12/13 v3.0.0 (rcs-revision 1.142)
+Package: tikz 2015/08/07 v3.0.1a (rcs-revision 1.151)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/pgflibraryplothandlers
.code.tex
-File: pgflibraryplothandlers.code.tex 2013/08/31 v3.0.0 (rcs-revision 1.20)
+File: pgflibraryplothandlers.code.tex 2013/08/31 v3.0.1a (rcs-revision 1.20)
\pgf@plot@mark@count=\count159
-\pgfplotmarksize=\dimen206
-)
-\tikz@lastx=\dimen207
-\tikz@lasty=\dimen208
-\tikz@lastxsaved=\dimen209
-\tikz@lastysaved=\dimen210
-\tikzleveldistance=\dimen211
-\tikzsiblingdistance=\dimen212
+\pgfplotmarksize=\dimen263
+)
+\tikz@lastx=\dimen264
+\tikz@lasty=\dimen265
+\tikz@lastxsaved=\dimen266
+\tikz@lastysaved=\dimen267
+\tikzleveldistance=\dimen268
+\tikzsiblingdistance=\dimen269
\tikz@figbox=\box54
\tikz@figbox@bg=\box55
\tikz@tempbox=\box56
(/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik
zlibrarytopaths.code.tex
-File: tikzlibrarytopaths.code.tex 2008/06/17 v3.0.0 (rcs-revision 1.2)
+File: tikzlibrarytopaths.code.tex 2008/06/17 v3.0.1a (rcs-revision 1.2)
)))
(/usr/share/texlive/texmf-dist/tex/latex/pgf/compatibility/pgflibrarysnakes.sty
(/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/pgflibrarysnakes.code.
tex
-File: pgflibrarysnakes.code.tex 2013/07/15 v3.0.0 (rcs-revision 1.25)
+File: pgflibrarysnakes.code.tex 2013/07/15 v3.0.1a (rcs-revision 1.25)
Package pgf Warning: Snakes have been superseded by decorations. Use the decora
decorations.pathmorphing.code.tex
(/usr/share/texlive/texmf-dist/tex/generic/pgf/modules/pgfmoduledecorations.cod
e.tex
-\pgfdecoratedcompleteddistance=\dimen213
-\pgfdecoratedremainingdistance=\dimen214
-\pgfdecoratedinputsegmentcompleteddistance=\dimen215
-\pgfdecoratedinputsegmentremainingdistance=\dimen216
-\pgf@decorate@distancetomove=\dimen217
+\pgfdecoratedcompleteddistance=\dimen270
+\pgfdecoratedremainingdistance=\dimen271
+\pgfdecoratedinputsegmentcompleteddistance=\dimen272
+\pgfdecoratedinputsegmentremainingdistance=\dimen273
+\pgf@decorate@distancetomove=\dimen274
\pgf@decorate@repeatstate=\count168
-\pgfdecorationsegmentamplitude=\dimen218
-\pgfdecorationsegmentlength=\dimen219
+\pgfdecorationsegmentamplitude=\dimen275
+\pgfdecorationsegmentlength=\dimen276
))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/decorations/pgflibrary
decorations.pathreplacing.code.tex)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/decorations/pgflibrary
decorations.shapes.code.tex)))
(/usr/share/texlive/texmf-dist/tex/latex/tools/multicol.sty
-Package: multicol 2014/10/28 v1.8i multicolumn formatting (FMi)
+Package: multicol 2015/08/19 v1.8n multicolumn formatting (FMi)
\c@tracingmulticols=\count169
\mult@box=\box58
-\multicol@leftmargin=\dimen220
+\multicol@leftmargin=\dimen277
\c@unbalance=\count170
\c@collectmore=\count171
\doublecol@number=\count172
\multicoltolerance=\count173
\multicolpretolerance=\count174
-\full@width=\dimen221
-\page@free=\dimen222
-\premulticols=\dimen223
-\postmulticols=\dimen224
-\multicolsep=\skip69
-\multicolbaselineskip=\skip70
+\full@width=\dimen278
+\page@free=\dimen279
+\premulticols=\dimen280
+\postmulticols=\dimen281
+\multicolsep=\skip71
+\multicolbaselineskip=\skip72
\partial@page=\box59
\last@line=\box60
-\maxbalancingoverflow=\dimen225
+\maxbalancingoverflow=\dimen282
\mult@rightbox=\box61
\mult@grightbox=\box62
\mult@gfirstbox=\box63
\@tempa=\box81
\c@columnbadness=\count175
\c@finalcolumnbadness=\count176
-\last@try=\dimen226
-\multicolovershoot=\dimen227
-\multicolundershoot=\dimen228
+\last@try=\dimen283
+\multicolovershoot=\dimen284
+\multicolundershoot=\dimen285
\mult@nat@firstbox=\box82
\colbreak@box=\box83
\mc@col@check@num=\count177
)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik
zlibraryarrows.code.tex
-File: tikzlibraryarrows.code.tex 2008/01/09 v3.0.0 (rcs-revision 1.1)
+File: tikzlibraryarrows.code.tex 2008/01/09 v3.0.1a (rcs-revision 1.1)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/pgflibraryarrows.code.
tex
-File: pgflibraryarrows.code.tex 2013/09/23 v3.0.0 (rcs-revision 1.16)
-\arrowsize=\dimen229
+File: pgflibraryarrows.code.tex 2013/09/23 v3.0.1a (rcs-revision 1.16)
+\arrowsize=\dimen286
))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik
zlibraryautomata.code.tex
-File: tikzlibraryautomata.code.tex 2008/07/14 v3.0.0 (rcs-revision 1.3)
+File: tikzlibraryautomata.code.tex 2008/07/14 v3.0.1a (rcs-revision 1.3)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik
zlibraryshapes.multipart.code.tex
-File: tikzlibraryshapes.multipart.code.tex 2008/01/09 v3.0.0 (rcs-revision 1.1)
-
+File: tikzlibraryshapes.multipart.code.tex 2008/01/09 v3.0.1a (rcs-revision 1.1
+)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/shapes/pgflibraryshape
s.multipart.code.tex
-File: pgflibraryshapes.multipart.code.tex 2010/01/07 v3.0.0 (rcs-revision 1.2)
+File: pgflibraryshapes.multipart.code.tex 2010/01/07 v3.0.1a (rcs-revision 1.2)
+
\pgfnodepartlowerbox=\box84
\pgfnodeparttwobox=\box85
\pgfnodepartthreebox=\box86
)))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik
zlibrarysnakes.code.tex
-File: tikzlibrarysnakes.code.tex 2013/07/15 v3.0.0 (rcs-revision 1.7)
+File: tikzlibrarysnakes.code.tex 2013/07/15 v3.0.1a (rcs-revision 1.7)
Package pgf Warning: Snakes have been superseded by decorations. Please use the
zlibrarydecorations.shapes.code.tex))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik
zlibraryshapes.code.tex
-File: tikzlibraryshapes.code.tex 2008/01/09 v3.0.0 (rcs-revision 1.1)
+File: tikzlibraryshapes.code.tex 2008/01/09 v3.0.1a (rcs-revision 1.1)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik
zlibraryshapes.geometric.code.tex
-File: tikzlibraryshapes.geometric.code.tex 2008/01/09 v3.0.0 (rcs-revision 1.1)
-
+File: tikzlibraryshapes.geometric.code.tex 2008/01/09 v3.0.1a (rcs-revision 1.1
+)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/shapes/pgflibraryshape
s.geometric.code.tex
-File: pgflibraryshapes.geometric.code.tex 2008/06/26 v3.0.0 (rcs-revision 1.1)
+File: pgflibraryshapes.geometric.code.tex 2008/06/26 v3.0.1a (rcs-revision 1.1)
+
))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik
zlibraryshapes.misc.code.tex
-File: tikzlibraryshapes.misc.code.tex 2008/01/09 v3.0.0 (rcs-revision 1.1)
+File: tikzlibraryshapes.misc.code.tex 2008/01/09 v3.0.1a (rcs-revision 1.1)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/shapes/pgflibraryshape
s.misc.code.tex
-File: pgflibraryshapes.misc.code.tex 2013/07/18 v3.0.0 (rcs-revision 1.5)
+File: pgflibraryshapes.misc.code.tex 2013/07/18 v3.0.1a (rcs-revision 1.5)
))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik
zlibraryshapes.symbols.code.tex
-File: tikzlibraryshapes.symbols.code.tex 2008/01/09 v3.0.0 (rcs-revision 1.1)
+File: tikzlibraryshapes.symbols.code.tex 2008/01/09 v3.0.1a (rcs-revision 1.1)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/shapes/pgflibraryshape
s.symbols.code.tex
-File: pgflibraryshapes.symbols.code.tex 2013/09/11 v3.0.0 (rcs-revision 1.6)
+File: pgflibraryshapes.symbols.code.tex 2013/09/11 v3.0.1a (rcs-revision 1.6)
))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik
zlibraryshapes.arrows.code.tex
-File: tikzlibraryshapes.arrows.code.tex 2008/01/09 v3.0.0 (rcs-revision 1.1)
+File: tikzlibraryshapes.arrows.code.tex 2008/01/09 v3.0.1a (rcs-revision 1.1)
(/usr/share/texlive/texmf-dist/tex/generic/pgf/libraries/shapes/pgflibraryshape
s.arrows.code.tex
-File: pgflibraryshapes.arrows.code.tex 2008/06/26 v3.0.0 (rcs-revision 1.1)
+File: pgflibraryshapes.arrows.code.tex 2008/06/26 v3.0.1a (rcs-revision 1.1)
))
(/usr/share/texlive/texmf-dist/tex/generic/pgf/frontendlayer/tikz/libraries/tik
zlibraryshapes.callouts.code.tex
(/usr/share/texlive/texmf-dist/tex/context/base/supp-pdf.mkii
[Loading MPS to PDF converter (version 2006.09.02).]
\scratchcounter=\count178
-\scratchdimen=\dimen230
+\scratchdimen=\dimen287
\scratchbox=\box105
\nofMPsegments=\count179
\nofMParguments=\count180
\everyMPshowfont=\toks48
\MPscratchCnt=\count181
-\MPscratchDim=\dimen231
+\MPscratchDim=\dimen288
\MPnumerator=\count182
\makeMPintoPDFobject=\count183
\everyMPtoPDFconversion=\toks49
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 30.
-LaTeX Warning: Citation `915396' on page 1 undefined on input line 2.
-
-
-LaTeX Warning: Citation `915385' on page 1 undefined on input line 2.
-
-
-LaTeX Warning: Citation `5376454' on page 1 undefined on input line 2.
-
-
-LaTeX Warning: Citation `915396' on page 1 undefined on input line 5.
-
-
-LaTeX Warning: Citation `915385' on page 1 undefined on input line 5.
-
-
-LaTeX Warning: Citation `5376454' on page 1 undefined on input line 5.
-
-
-LaTeX Warning: Citation `Marsaglia1996' on page 1 undefined on input line 10.
-
-
-LaTeX Warning: Citation `Nist10' on page 1 undefined on input line 10.
-
-
-LaTeX Warning: Citation `LEcuyerS07' on page 1 undefined on input line 10.
-
-
-LaTeX Warning: Citation `Devaney' on page 1 undefined on input line 19.
-
-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 2014/09/29 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.
+(Font) Font shape `OMS/cmsy/m/n' tried instead on input line 30.
[1
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}]
-
-LaTeX Warning: Citation `guyeuxTaiwan10' on page 2 undefined on input line 31.
-
-
-LaTeX Warning: Citation `bcgr11:ip' on page 2 undefined on input line 31.
-
-
-LaTeX Warning: Citation `wbg10ip' on page 2 undefined on input line 32.
-
-
-LaTeX Warning: Citation `chgw14oip' on page 2 undefined on input line 33.
-
-
-LaTeX Warning: Citation `bcgr11:ip' on page 2 undefined on input line 35.
-
-
-LaTeX Warning: Citation `chgw14oip' on page 2 undefined on input line 42.
-
-
-LaTeX Warning: Citation `chgw14oip' on page 2 undefined on input line 58.
-
-
-LaTeX Warning: Reference `sec:hypercube' on page 2 undefined on input line 96.
-
-
-LaTeX Warning: Reference `sec:prng' on page 2 undefined on input line 100.
-
-)
Underfull \vbox (badness 10000) has occurred while \output is active []
- [2]
+ [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>
+) [3]
+<images/iter_f0c.pdf, id=41, 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.
-
-
-LaTeX Warning: Citation `DBLP:conf/secrypt/CouchotHGWB14' on page 3 undefined o
-n input line 66.
-
-) [3] (./chaos.tex
-
-LaTeX Warning: Citation `bcgr11:ip' on page 4 undefined on input line 2.
-
-
-LaTeX Warning: Citation `bcgr11:ip' on page 4 undefined on input line 21.
-
-[4 <./images/iter_f0c.pdf>]
-
-LaTeX Warning: Citation `Devaney' on page 5 undefined on input line 62.
-
-
-LaTeX Warning: Citation `Banks92' on page 5 undefined on input line 79.
-
-[5]
+) (./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; v\OT1/cmr/m/n/10 ))$\T1/cmr/m/n/10 . As the right
[]
-<graphe1.pdf, id=73, 106.3975pt x 99.37125pt>
+<graphe1.pdf, id=72, 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>
+<graphe2.pdf, id=73, 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.
mr/m/n/10 ([]\OML/cmm/m/it/10 ; []\OT1/cmr/m/n/10 )) \OMS/cmsy/m/n/10 2
[]
-
+[9 <./graphe1.pdf> <./graphe2.pdf>]
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
-
-LaTeX Warning: Citation `bcgr11:ip' on page 10 undefined on input line 2.
-
-
-LaTeX Warning: Citation `DBLP:conf/secrypt/CouchotHGWB14' on page 10 undefined
-on input line 9.
-
-[10]
-
-LaTeX Warning: Citation `bcgr11:ip' on page 11 undefined on input line 61.
-
-) (./hamilton.tex
-
-LaTeX Warning: Citation `Robinson:1981:CS' on page 11 undefined on input line 2
-.
-
-
-LaTeX Warning: Citation `DBLP:journals/combinatorics/BhatS96' on page 11 undefi
-ned on input line 2.
-
-
-LaTeX Warning: Citation `ZanSup04' on page 11 undefined on input line 2.
-
-
-LaTeX Warning: Citation `Bykov2016' on page 11 undefined on input line 2.
-
-
-LaTeX Warning: Citation `DBLP:journals/combinatorics/BhatS96' on page 11 undefi
-ned on input line 4.
-
-
-LaTeX Warning: Citation `ZanSup04' on page 11 undefined on input line 4.
-
-
-LaTeX Warning: Citation `Bykov2016' on page 11 undefined on input line 14.
-
-
-LaTeX Warning: Citation `ZanSup04' on page 11 undefined on input line 27.
-
-
-LaTeX Warning: Citation `DBLP:journals/combinatorics/BhatS96' on page 11 undefi
-ned on input line 27.
-
-
-LaTeX Warning: Citation `Bykov2016' on page 11 undefined on input line 28.
-
-
-LaTeX Warning: Citation `ZanSup04' on page 11 undefined on input line 31.
-
-[11]
-
-LaTeX Warning: Citation `Robinson:1981:CS' on page 12 undefined on input line 3
-7.
-
-
-LaTeX Warning: Citation `DBLP:journals/combinatorics/BhatS96' on page 12 undefi
-ned on input line 37.
-
-
-LaTeX Warning: Citation `ZanSup04' on page 12 undefined on input line 38.
-
-
-LaTeX Warning: Citation `Robinson:1981:CS' on page 12 undefined on input line 4
-0.
-
-
-LaTeX Warning: Citation `DBLP:journals/combinatorics/BhatS96' on page 12 undefi
-ned on input line 43.
-
-
-LaTeX Warning: Citation `ZanSup04' on page 12 undefined on input line 45.
-
-
-LaTeX Warning: Citation `ZanSup04' on page 12 undefined on input line 62.
-
-
-LaTeX Warning: Citation `ZanSup04' on page 12 undefined on input line 84.
-
-[12]
-Overfull \hbox (104.68428pt too wide) in paragraph at lines 119--124
+) (./generating.tex [10]) (./hamilton.tex [11] [12]
+Overfull \hbox (104.68428pt too wide) in paragraph at lines 120--125
[]\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/
[]
-Overfull \hbox (116.14502pt too wide) in paragraph at lines 125--130
+Overfull \hbox (116.14502pt too wide) in paragraph at lines 126--131
[]\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
/10 ;$
[]
-Runaway argument?
-{2^{\mathsf {N} -n.a_{\mathsf {N}}}{2} \\ c_{\mathsf {N}} = \mathsf {\ETC.
-! Paragraph ended before \@genfrac was complete.
-<to be read again>
- \par
-l.189
-
-? r
-OK, entering \nonstopmode...
-! Missing $ inserted.
-<inserted text>
- $
-l.190 Since $a_
- {\mathsf{N}$ is even, $d_{\mathsf{N}}$ is defined.
-I've inserted a begin-math/end-math symbol since I think
-you left one out. Proceed, with fingers crossed.
-
-! Missing } inserted.
-<inserted text>
- }
-l.190 Since $a_{\mathsf{N}$
- is even, $d_{\mathsf{N}}$ is defined.
-I've inserted something that you may have forgotten.
-(See the <inserted text> above.)
-With luck, this will get me unwedged. But if you
-really didn't forget anything, try typing `2' now; then
-my insertion and my current dilemma will both disappear.
-
-
-! LaTeX Error: Something's wrong--perhaps a missing \item.
-
-See the LaTeX manual or LaTeX Companion for explanation.
-Type H <return> for immediate help.
- ...
-
-l.194 \subsection
- {Toward a local uniform distribution of switches}
-Try typing <return> to proceed.
-If that doesn't work, type X <return> to quit.
-
-
-! LaTeX Error: Something's wrong--perhaps a missing \item.
-
-See the LaTeX manual or LaTeX Companion for explanation.
-Type H <return> for immediate help.
- ...
-
-l.194 \subsection
- {Toward a local uniform distribution of switches}
-Try typing <return> to proceed.
-If that doesn't work, type X <return> to quit.
-
-! Missing } inserted.
-<inserted text>
- }
-l.194 ...a local uniform distribution of switches}
-
-I've inserted something that you may have forgotten.
-(See the <inserted text> above.)
-With luck, this will get me unwedged. But if you
-really didn't forget anything, try typing `2' now; then
-my insertion and my current dilemma will both disappear.
-
-! Missing \cr inserted.
-<inserted text>
- \cr
-l.194 ...a local uniform distribution of switches}
-
-I'm guessing that you meant to end an alignment here.
-
-! Missing $ inserted.
-<inserted text>
- $
-l.194 ...a local uniform distribution of switches}
-
-I've inserted a begin-math/end-math symbol since I think
-you left one out. Proceed, with fingers crossed.
-
-)
-! Missing $ inserted.
-<inserted text>
- $
-l.122
-
-I've inserted a begin-math/end-math symbol since I think
-you left one out. Proceed, with fingers crossed.
-
-! Missing \endgroup inserted.
-<inserted text>
- \endgroup
-l.122
-
-I've inserted something that you may have forgotten.
-(See the <inserted text> above.)
-With luck, this will get me unwedged. But if you
-really didn't forget anything, try typing `2' now; then
-my insertion and my current dilemma will both disappear.
-
-! Missing \right. inserted.
-<inserted text>
- \right .
-l.122
-
-I've inserted something that you may have forgotten.
-(See the <inserted text> above.)
-With luck, this will get me unwedged. But if you
-really didn't forget anything, try typing `2' now; then
-my insertion and my current dilemma will both disappear.
-
-! Display math should end with $$.
-<to be read again>
- \par
-l.122
-
-The `$' that I just saw supposedly matches a previous `$$'.
-So I shall assume that you typed `$$' both times.
-
-
-Overfull \hbox (482.90009pt too wide) detected at line 122
-[] \OMS/cmsy/m/n/10 , []
- []
-
-(./stopping.tex [13]
-
-LaTeX Warning: Citation `LevinPeresWilmer2006' on page 14 undefined on input li
-ne 85.
-
-[14] [15]
-
-LaTeX Warning: Reference `lm:h' on page 16 undefined on input line 301.
-
-
-LaTeX Warning: Citation `proba' on page 16 undefined on input line 314.
-
-[16]
-
-LaTeX Warning: Reference `prop:stop' on page 17 undefined on input line 360.
-
+[13]
+Underfull \vbox (badness 2368) has occurred while \output is active []
-LaTeX Warning: Reference `prop:stop' on page 17 undefined on input line 367.
+ [14]
+Package amsmath Warning: Foreign command \atopwithdelims;
+(amsmath) \frac or \genfrac should be used instead
+(amsmath) on input line 324.
-LaTeX Warning: Reference `prop:lambda' on page 17 undefined on input line 368.
+) (./stopping.tex [15]
+LaTeX Warning: Reference `sub:stop:stop' on page 16 undefined on input line 47.
-LaTeX Warning: Reference `lm:stopprime' on page 17 undefined on input line 368.
-
-
-) [17] (./prng.tex
-
-LaTeX Warning: Reference `CI Algorithm:2' on page 18 undefined on input line 13
-.
-
-
-LaTeX Warning: Reference `sec:hypercube' on page 18 undefined on input line 44.
-
-
-
-LaTeX Warning: Reference `eq:Markov:rairo' on page 18 undefined on input line 5
-9.
-
-
-LaTeX Warning: Reference `table:nc' on page 18 undefined on input line 62.
+[16] [17] [18] [19]) (./prng.tex [20]
LaTeX Warning: Command \textcircled invalid in math mode on input line 64.
LaTeX Warning: Command \textcircled invalid in math mode on input line 67.
-[18]
-
-LaTeX Warning: Reference `sec:hypercube' on page 19 undefined on input line 76.
-
-
+[21]
LaTeX Warning: Command \textcircled invalid in math mode on input line 89.
LaTeX Warning: Command \textcircled invalid in math mode on input line 172.
-LaTeX Warning: Reference `The passing rate' on page 19 undefined on input line
-214.
-
-
-LaTeX Warning: Reference `The passing rate' on page 19 undefined on input line
-217.
-
-
LaTeX Warning: Command \textcircled invalid in math mode on input line 231.
) (./conclusion.tex
Missing character: There is no p in font dsrom8!
Missing character: There is no p in font dsrom8!
- [19]) (./main.bbl
+ [22]) (./main.bbl
Underfull \vbox (badness 10000) has occurred while \output is active []
- [20]
-Underfull \hbox (badness 10000) in paragraph at lines 81--84
+ [23]
+Underfull \hbox (badness 10000) in paragraph at lines 73--76
[]\T1/cmr/m/n/8 G. Marsaglia. Diehard: a bat-tery of tests of ran-dom-ness.
[]
-
+)
Underfull \vbox (badness 10000) has occurred while \output is active []
- [21])
-[22] (./main.aux)
+ [24]
+[25] (./main.aux)
LaTeX Warning: There were undefined references.
-
-LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
-
)
(\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:
- 22192 strings out of 493105
- 431459 string characters out of 6137072
- 566154 words of memory out of 5000000
- 24950 multiletter control sequences out of 15000+600000
+ 21959 strings out of 494924
+ 430391 string characters out of 6179708
+ 548115 words of memory out of 5000000
+ 24546 multiletter control sequences out of 15000+600000
28957 words of font info for 91 fonts, out of 8000000 for 9000
- 1302 hyphenation exceptions out of 8191
- 54i,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, 613533 bytes).
+ 175 hyphenation exceptions out of 8191
+ 54i,17n,77p,539b,699s stack positions out of 5000i,500n,10000p,200000b,80000s
+ </home/couchot/.texmf-var/fonts/pk/ljfour/jknappen/ec/eccc0900
+.600pk> </home/couchot/.texmf-var/fonts/pk/ljfour/jknappen/ec/ecbx0700.600pk> <
+/home/couchot/.texmf-var/fonts/pk/ljfour/jknappen/ec/eccc1000.600pk> </home/cou
+chot/.texmf-var/fonts/pk/ljfour/jknappen/ec/ecti0700.600pk> </home/couchot/.tex
+mf-var/fonts/pk/ljfour/jknappen/ec/ecti1000.600pk> </home/couchot/.texmf-var/fo
+nts/pk/ljfour/jknappen/ec/ecrm0700.600pk> </home/couchot/.texmf-var/fonts/pk/lj
+four/jknappen/ec/ecti0800.600pk> </home/couchot/.texmf-var/fonts/pk/ljfour/jkna
+ppen/ec/ecrm1200.600pk> </home/couchot/.texmf-var/fonts/pk/ljfour/jknappen/ec/e
+crm1000.600pk> </home/couchot/.texmf-var/fonts/pk/ljfour/jknappen/ec/ecrm0900.6
+00pk> </home/couchot/.texmf-var/fonts/pk/ljfour/jknappen/ec/eccc1200.600pk> </h
+ome/couchot/.texmf-var/fonts/pk/ljfour/jknappen/ec/ecbx1095.600pk> </home/couch
+ot/.texmf-var/fonts/pk/ljfour/jknappen/ec/ecrm0800.600pk> </home/couchot/.texmf
+-var/fonts/pk/ljfour/jknappen/ec/ecbx1000.600pk></usr/share/texlive/texmf-dist/
+fonts/type1/public/amsfonts/cm/cmex10.pfb></usr/share/texlive/texmf-dist/fonts/
+type1/public/amsfonts/cmextra/cmex7.pfb></usr/share/texlive/texmf-dist/fonts/ty
+pe1/public/amsfonts/cm/cmmi10.pfb></usr/share/texlive/texmf-dist/fonts/type1/pu
+blic/amsfonts/cm/cmmi12.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/a
+msfonts/cm/cmmi5.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts
+/cm/cmmi6.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmm
+i7.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmmi8.pfb>
+</usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmmi9.pfb></usr/s
+hare/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmr10.pfb></usr/share/te
+xlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmr12.pfb></usr/share/texlive/t
+exmf-dist/fonts/type1/public/amsfonts/cm/cmr5.pfb></usr/share/texlive/texmf-dis
+t/fonts/type1/public/amsfonts/cm/cmr6.pfb></usr/share/texlive/texmf-dist/fonts/
+type1/public/amsfonts/cm/cmr7.pfb></usr/share/texlive/texmf-dist/fonts/type1/pu
+blic/amsfonts/cm/cmr8.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/ams
+fonts/cm/cmr9.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm
+/cmss10.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmss8
+.pfb></usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmsy10.pfb><
+/usr/share/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmsy5.pfb></usr/sh
+are/texlive/texmf-dist/fonts/type1/public/amsfonts/cm/cmsy6.pfb></usr/share/tex
+live/texmf-dist/fonts/type1/public/amsfonts/cm/cmsy7.pfb></usr/share/texlive/te
+xmf-dist/fonts/type1/public/amsfonts/cm/cmsy8.pfb></usr/share/texlive/texmf-dis
+t/fonts/type1/public/doublestroke/dsrom10.pfb></usr/share/texlive/texmf-dist/fo
+nts/type1/public/doublestroke/dsrom8.pfb></usr/share/texlive/texmf-dist/fonts/t
+ype1/public/amsfonts/symbols/msam10.pfb></usr/share/texlive/texmf-dist/fonts/ty
+pe1/public/amsfonts/symbols/msbm10.pfb></usr/share/texlive/texmf-dist/fonts/typ
+e1/public/amsfonts/symbols/msbm7.pfb></usr/share/texlive/texmf-dist/fonts/type1
+/public/stmaryrd/stmary10.pfb></usr/share/texlive/texmf-dist/fonts/type1/public
+/stmaryrd/stmary7.pfb>
+Output written on main.pdf (25 pages, 495003 bytes).
PDF statistics:
- 283 PDF objects out of 1000 (max. 8388607)
- 203 compressed objects within 3 object streams
+ 847 PDF objects out of 1000 (max. 8388607)
+ 223 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})$$
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$.
$\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
The calculus does not consider (balanced) Hamiltonian cycles, which
are more regular and more binding than this constraint.
In this later context, we claim that the upper bound for the stopping time
-should be reduced.
+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
+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}
