From: couchot Date: Tue, 6 Sep 2016 19:23:06 +0000 (+0200) Subject: avant soummission X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/commitdiff_plain/3fc31015143d2bab7226a54390f3e1c5eba8f4d5 avant soummission --- diff --git a/biblio.bib b/biblio.bib index 8e60a54..5e9f408 100644 --- a/biblio.bib +++ b/biblio.bib @@ -145,6 +145,20 @@ OPTannote = {} } +@inproceedings{bfgw11:ip, +inhal = {no}, +domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, +equipe = {and}, +classement = {ACTI}, +author = {Bahi, Jacques and Fang, Xiaole and Guyeux, Christophe and Wang, Qianxue}, +title = {On the design of a family of {CI} pseudo-random number generators}, +booktitle = {WICOM'11, 7th Int. IEEE Conf. on Wireless Communications, Networking and Mobile Computing}, +pages = {1--4}, +address = {Wuhan, China}, +month = sep, +year = 2011, + +} @Article{Rob78, author = {F.~Robert}, title = {Th\'{e}or\`{e}me de Perron-Frobenius et Stein-Rosenberg booléens}, @@ -488,7 +502,6 @@ bibsource = "DBLP, http://dblp.uni-trier.de/db/journals/cacm/cacm4.html#Kuehn61", pages = "350--352", - URL = "http://doi.acm.org/10.1145/366678.366690", } @TechReport{ICSI-TR-90-039, @@ -534,7 +547,6 @@ bibsource = "DBLP, http://dblp.uni-trier.de/db/journals/mcma/mcma10.html#Sugita04", pages = "609--615", - URL = "http://dx.doi.org/10.1515/mcma.2004.10.3-4.609", } @Article{Marsaglia98, @@ -636,11 +648,9 @@ year = 2014, publisher = {IEEE Computer Society Press}, note = {Best Paper award}, classement = {ACTI}, - doi = {10.1109/INTERNET.2010.30}, domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, equipe = {and}, inhal = {no}, - url = {http://doi.ieeecomputersociety.org/10.1109/INTERNET.2010.30} } @@ -657,11 +667,9 @@ year = 2014, address = {Sanya, China}, month = oct, classement = {ACTI}, - doi = {10.1007/978-3-642-16515-3_26}, domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, equipe = {and}, inhal = {no}, - url = {http://dx.doi.org/10.1007/978-3-642-16515-3_26} } @@ -675,11 +683,9 @@ year = 2014, address = {Cannes, France}, month = aug, classement = {ACTI}, - doi = {10.1109/INTERNET.2009.18}, domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, equipe = {and}, inhal = {no}, - url = {http://dx.doi.org/10.1109/INTERNET.2009.18} } @INPROCEEDINGS{guyeuxTaiwan10, @@ -691,7 +697,6 @@ month={Oct}, volume={13}, pages={V13-643-V13-647}, keywords={cryptography;data encapsulation;random number generation;DieHARD statistical test suite;XORshifts PRNG;chaotic iterations;cryptographic applications;data hiding;pseudo-random number generator;Authentication;Cryptography;DNA;Generators;Discrete chaotic iterations;Internet security;Pseudo-random number generator;Statistical tests;Topological chaos;data hiding}, -doi={10.1109/ICCASM.2010.5622199}, publisher={IEEE} } @@ -720,11 +725,9 @@ year = 2011} month = jul, note = {Best paper award}, classement = {ACTI}, - doi = {10.1109/IJCNN.2010.5596512}, domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, equipe = {and}, inhal = {no}, - url = {http://dx.doi.org/10.1109/IJCNN.2010.5596512} } @@ -760,7 +763,6 @@ year = 2011} number = {4}, bibdate = {2007-11-06}, bibsource = {DBLP, http://dblp.uni-trier.de/db/journals/toms/toms33.html#LEcuyerS07}, - url = {http://doi.acm.org/10.1145/1268776.1268777} } @@ -803,7 +805,6 @@ volume={48}, number={3}, pages={382-385}, keywords={CMOS analogue integrated circuits;chaos generators;circuit simulation;piecewise linear techniques;random number generation;redundancy;switched current circuits;0.8 micron;1 Mbit/s;chaos-based random number generators;chaotic piecewise-linear one-dimensional map;output bit rate;parasitic attractors;periodic attractors;post-layout circuit simulations;process conditions;redundancy;standard CMOS process;switched current techniques;Bit rate;CMOS process;Chaos;Circuits;Electric breakdown;Information analysis;Piecewise linear techniques;Power supplies;Random number generation;Temperature}, -doi={10.1109/81.915396}, ISSN={1057-7122},} @@ -817,7 +818,6 @@ volume={48}, number={3}, pages={281-288}, keywords={Markov processes;chaos;cryptography;piecewise linear techniques;random number generation;Markov generating partition;Markov information source;chaos-based random number generators;cryptography;information generation process;parameter values;piecewise-linear one-dimensional map;random number generator;Chaos;Cryptographic protocols;Cryptography;Current measurement;Low-frequency noise;Noise measurement;Random number generation;Random sequences;Security;Semiconductor device noise}, -doi={10.1109/81.915385}, ISSN={1057-7122},} @INPROCEEDINGS{5376454, @@ -829,7 +829,6 @@ month={Dec}, volume={1}, pages={494-498}, keywords={binary sequences;chaos;discrete systems;random number generation;synchronisation;2D Arnold cat map;6D discrete chaos map;FIPA-140-2 tests;National Institute of Standard and Technology;binary number sequences;chaos-based pseudorandom number generator;confidence interval analysis;generalized chaos synchronization theorem;performance analysis;Chaos;Chaotic communication;Computational intelligence;NIST;Nonlinear dynamical systems;Performance analysis;Random number generation;Security;Space technology;Testing;Discrete chaos map;generalized chaos synchronization;one-time-pad;statistical test}, -doi={10.1109/CIS.2009.203}, publisher={IEEE} } @@ -845,8 +844,6 @@ title = {Suitability of chaotic iterations schemes using {XORshift} for security journal = {JNCA, Journal of Network and Computer Applications}, pages = {282--292}, volume = 37, -doi = {10.1016/j.jnca.2013.03.001}, -url = {http://dx.doi.org/10.1016/j.jnca.2013.03.001}, abstract = {The design and engineering of original cryptographic solutions is a major concern to provide secure information systems. In a previous study, we have described a generator based on chaotic iterations, which uses the well-known XORshift generator. By doing so, we have improved the statistical performances of XORshift and make it behave chaotically, as defined by Devaney. The speed and security of this former generator have been improved in a second study, to make its usage more relevant in the Internet security context. In this paper, these contributions are summarized and a new version of the generator is introduced. It is based on a new Lookup Table implying a large improvement of speed. A comparison and a security analysis between the XORshift and these three versions of our generator are proposed, and various new statistical results are given. Finally, an application in the information hiding framework is presented, to give an illustrative example of the use of such a generator in the Internet security field.}, publisher = {Elsevier}, year = 2013, @@ -899,7 +896,6 @@ year = 2013, number = "5", volume = "109", pages = "267--272", - URL = "http://dx.doi.org/10.1016/j.ipl.2008.10.015", } @inproceedings{DBLP:conf/secrypt/CouchotHGWB14, @@ -947,11 +943,9 @@ year = 2013, publisher = {IEEE Computer Society Press}, note = {Best Paper award}, classement = {ACTI}, - doi = {10.1109/INTERNET.2010.30}, domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, equipe = {and}, inhal = {no}, - url = {http://doi.ieeecomputersociety.org/10.1109/INTERNET.2010.30} } @@ -969,11 +963,9 @@ year = 2013, address = {Cannes, France}, month = aug, classement = {ACTI}, - doi = {10.1109/INTERNET.2009.18}, domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, equipe = {and}, inhal = {no}, - url = {http://dx.doi.org/10.1109/INTERNET.2009.18} } @@ -992,11 +984,9 @@ year = 2013, address = {Oslo, Norway}, month = aug, classement = {ACTI}, - doi = {10.1007/978-3-642-22953-4_11}, domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, equipe = {and}, inhal = {no}, - url = {http://dx.doi.org/10.1007/978-3-642-22953-4_11} } @@ -1041,8 +1031,6 @@ number="1", pages="78--85", abstract="We consider locally balanced Gray codes.We say that a Gray code is locally balanced if every ``short'' subword in its transition sequence contains all letters of the alphabet |1, 2,..., n{\textasciitilde}. The minimal length of these subwords is the window width of the code. We show that for each n ≥ 3 there exists a Gray code with window width at most n + 3⌊log n⌋.", issn="1990-4797", -doi="10.1134/S1990478916010099", -url="http://dx.doi.org/10.1134/S1990478916010099" } diff --git a/chaos.tex b/chaos.tex index acf42e3..a82d57c 100644 --- a/chaos.tex +++ b/chaos.tex @@ -1,3 +1,5 @@ + +\subsection{Motivations} Let us us first recall the chaos theoretical context presented in~\cite{bcgr11:ip}. In this article, the space of interest is $\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$ @@ -22,13 +24,13 @@ We have proven~\cite[Theorem 1]{bcgr11:ip} that $\mathcal{H}_f$ is chaotic in $\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$ if and only if $\Gamma(f)$ is strongly connected. -However, the corrolary which would say that $\chi_{\textit{14Secrypt}}$ is chaotic +However, the corollary which would say that $\chi_{\textit{14Secrypt}}$ is chaotic cannot be directly deduced since we do not output all the successive -values of iterating $F_f$. Only a a few of them is concerned and +values of iterating $F_f$. Only a few of them is concerned and any subsequence of a chaotic sequence is not necessarily a chaotic sequence too. This necessitates a rigorous proof, which is the aim of this section. - +Let us firstly recall the theoretical framework in which this research takes place. @@ -38,7 +40,7 @@ This necessitates a rigorous proof, which is the aim of this section. Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f : -\mathcal{X} \rightarrow \mathcal{X}$. +\mathcal{X} \rightarrow \mathcal{X}$~\cite{Devaney}. \begin{definition} The function $f$ is said to be \emph{topologically transitive} if, for any pair of open sets @@ -153,13 +155,12 @@ Let us first introduce $\mathcal{P} \subset \mathds{N}$ a finite nonempty set having the cardinality $\mathsf{p} \in \mathds{N}^\ast$. Intuitively, this is the set of authorized numbers of iterations. Denote by $p_1, p_2, \hdots, p_\mathsf{p}$ the ordered elements of $\mathcal{P}$: $\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$ -and $p_1< p_2< \hdots < p_\mathsf{p}$. In our algorithm, -$\mathsf{p}$ is 1 and $p_1$ is $b$. - +and $p_1< p_2< \hdots < p_\mathsf{p}$. -The Algorithm~\ref{CI Algorithm} -may be seen as $b$ functional composition of $F_f$. -However, it can be generalized with $p_i$, $p_i \in \mathcal{P}$, +In our Algorithm~\ref{CI Algorithm}, +$\mathsf{p}$ is 1 and $p_1$ is $b$. +But this algorithm can be seen as $b$ functional compositions of $F_f$. +Obviously, it can be generalized with $p_i$, $p_i \in \mathcal{P}$, functional compositions of $F_f$. Thus, for any $p_i \in \mathcal{P}$ we introduce the function $F_{f,p_i} : \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^{p_i} \rightarrow \mathds{B}^\mathsf{N}$ defined by @@ -179,10 +180,10 @@ $\mathds{S}_{\mathsf{N},\mathcal{P}}= Each element in this space is a pair where the first element is $\mathsf{N}$-uple in $\Bool^{\mathsf{N}}$, as in the previous space. The second element is a pair $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats})$ of infinite sequences. -The sequence $(v^k)_{k \in \Nats}$ defines how many iterations are executed at time $k$ between two outputs. -The sequence $(u^k)_{k \in \Nats}$ defines which elements is modified. +The sequence $(v^k)_{k \in \Nats}$ defines how many iterations are executed at time $k$ before the next output, +while $(u^k)_{k \in \Nats}$ details which elements are modified. -Let us define the shift function $\Sigma$ for any element of $\mathds{S}_{\mathsf{N},\mathcal{P}}$. +Let us introduce the shift function $\Sigma$ for any element of $\mathds{S}_{\mathsf{N},\mathcal{P}}$. \[ \begin{array}{cccc} @@ -199,17 +200,18 @@ Let us define the shift function $\Sigma$ for any element of $\mathds{S}_{\maths In other words, $\Sigma$ receives two sequences $u$ and $v$, and it operates $v^0$ shifts on the first sequence and a single shift on the second one. -Let +Let us consider \begin{equation} \begin{array}{cccc} G_f :& \mathcal{X}_{\mathsf{N},\mathcal{P}} & \rightarrow & \mathcal{X}_{\mathsf{N},\mathcal{P}}\\ & (e,(u,v)) & \mapsto & \left( F_{f,v^0}\left( e, (u^0, \hdots, u^{v^0-1}\right), \Sigma (u,v) \right) . \end{array} \end{equation} -Then the outputs $(y^0, y^1, \hdots )$ produced by the $\textit{CIPRNG}_f^2(u,v)$ generator -are the first components of the iterations $X^0 = (x^0, (u,v))$ and $\forall n \in \mathds{N}, +Then the outputs $(y^0, y^1, \hdots )$ produced by the $\textit{CIPRNG}_f^2(u,v)$ generator~\cite{wbg10:ip} +are by definition the first components of the iterations $X^0 = (x^0, (u,v))$ and $\forall n \in \mathds{N}, X^{n+1} = G_f(X^n)$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. - +The new obtained generator can be shown as either a post-treatment over generators $u$ and $v$, or a +discrete dynamical system on a set constituted by binary vectors and couple of integer sequences. @@ -233,7 +235,7 @@ between finite sequences $u^0, u^1, \hdots, u^{v^0-1}$ and $\check{u}^0, \check between $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ and $\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc. More precisely, let $p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ and $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$. \begin{itemize} -\item The $p$ first digits of $d(x,\check{x})$ is $|v^0-\check{v}^0|$ written in decimal numeration (and with $p$ digits). +\item The $p$ first digits of $d(x,\check{x})$ is $|v^0-\check{v}^0|$ written in decimal numeration (and with $p$ digits: zeros are added on the left if needed). \item The next $n\times \max{(\mathcal{P})}$ digits aim at measuring how much $u^0, u^1, \hdots, u^{v^0-1}$ differs from $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. The $n$ first digits are $|u^0-\check{u}^0|$. They are followed by $|u^1-\check{u}^1|$ written with $n$ digits, etc. @@ -251,12 +253,20 @@ $\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digi \end{itemize} \end{itemize} - - -\newcommand{\ns}{$\hspace{.1em}$} - +This distance has been defined to capture all aspects of divergences between two sequences generated +by the $\textit{CIPRNG}_f^2$ method, when setting respectively $(u,v)$ and $(\check{u},\check{v})$ as inputted +couples of generators. The integral part measures the bitwise Hamming distance between +the two $\mathsf{N}$-length binary vectors chosen as seeds. The fractional part must decrease +when the number of identical iterations applied by the $\textit{CIPRNG}_f^2$ discrete dynamical system on these seeds, in both cases (that is, when inputting either $(u,v)$ or $(\check{u},\check{v})$), increases. +More precisely, the fractional part will alternately measure the following elements: +\begin{itemize} + \item Do we iterate the same number of times between the next two outputs, when considering either $(u,v)$ or $(\check{u},\check{v})$? + \item Then, do we iterate the same components between the next two outputs of $\textit{CIPRNG}_f^2$ ? + \item etc. +\end{itemize} +Finally, zeros are put to be able to recover what occurred at a given iteration. Such aims are illustrated in the two following examples. \begin{xpl} -Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=2$), and that +Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=3$, $p=\lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1 = 2$, while $n=2$), and that $s=\left\{ \begin{array}{l} u=\underline{6,} ~ \underline{11,5}, ...\\ @@ -271,28 +281,29 @@ $\check{s}=\left\{ \end{array} \right.$. -So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.01\ns00\ns04\ns00\ns00\ns00\ns00\ns00\ns00\ns00\ns00\ns00\ns01\ns10\ns05 ...$ +So +$$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.01~0004000000000000000000~01~1005...$$ Indeed, the $p=2$ first digits are 01, as $|v^0-\check{v}^0|=1$, and we use $p$ digits to code this difference ($\mathcal{P}$ being $\{1,2,11\}$, this difference can be equal to 10). We then take the $v^0=1$ first terms of $u$, each term being coded in $n=2$ digits, that is, 06. As we can iterate at most $\max{(\mathcal{P})}$ times, we must complete this value by some 0's in such a way that the obtained result has $n\times \max{(\mathcal{P})}=22$ digits, that is: 0600000000000000000000. Similarly, the $\check{v}^0=2$ first -terms in $\check{u}$ are represented by 0604000000000000000000, and the absolute value of their -difference is equal to 0004000000000000000000. These digits are concatenated to 01, and +terms in $\check{u}$ are represented by 0604000000000000000000, and the value of their +digit per digit absolute difference is equal to 0004000000000000000000. These digits are concatenated to 01, and we start again with the remainder of the sequences. \end{xpl} \begin{xpl} -Consider now that $\mathsf{N}=9$, and $\mathcal{P}=\{2,7\}$, and that +Consider now that $\mathsf{N}=9$ ($n=1$), $\mathcal{P}=\{2,7\}$ ($\mathsf{p}=2, p=1$), and that $s=\left\{ \begin{array}{l} u=\underline{6,7,} ~ \underline{4,2,} ...\\ v=2,2,... \end{array} -\right.$ +\right.$\\ while $\check{s}=\left\{ \begin{array}{l} @@ -301,8 +312,10 @@ $\check{s}=\left\{ \end{array} \right.$ -So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, as $|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$, -and $|9800000-4200000| = 5600000$. +So: +$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5~2263667~1~5600000...$. +%as $|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$, +%and $|9800000-4200000| = 5600000$. \end{xpl} @@ -342,7 +355,7 @@ too, thus $d$ will also be a distance, being the sum of two distances. \item Obviously, $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})\geqslant 0$, and if $s=\check{s}$, then $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$. Conversely, if $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$, then $\forall k \in \mathds{N}, v^k=\check{v}^k$ due to the -definition of $d$. Then, as digits between positions $p+1$ and $p+n$ are null and correspond to $|u^0-\check{u}^0|$, we can conclude that $u^0=\check{u}^0$. An extension of this result to the whole first $n \times \max{(\mathcal{P})}$ bloc leads to $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$, and by checking all the $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$. +definition of $d$. Then, as digits between positions $p+1$ and $p+n$ are null and correspond to $|u^0-\check{u}^0|$, we can conclude that $u^0=\check{u}^0$. An extension of this result to the whole first $n \times \max{(\mathcal{P})}$ blocs leads to $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$, and by checking all the $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$. \item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ is clearly symmetric ($d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\check{s},s)$). \item The triangle inequality is obtained because the absolute value satisfies it too. @@ -403,7 +416,8 @@ $y=F_{f,p_i} (x, (u_0, \hdots, u_{p_i-1})) $. \end{itemize} It is not hard to see that the graph $\Gamma_{\{1\}}(f)$ is -$\Gamma(f)$. +$\Gamma(f)$ formerly introduced in~\cite{bcgr11:ip} for the $\textit{CIPRNG}_f^1(u)$ generator, +which is indeed $\textit{CIPRNG}_f^2(u,(1)_{n \in \mathds{N}})$. \begin{figure}[ht] \centering @@ -433,10 +447,10 @@ Consider for instance $\mathsf{N}=2$, Let $f_0:\mathds{B}^2 \longrightarrow \mathds{B}^2$ be the negation function, \textit{i.e.}, $f_0(x_1,x_2) = (\overline{x_1}, \overline{x_2})$, and consider $\mathcal{P}=\{2,3\}$. The graphs of iterations are given in -\textsc{Figure~\ref{fig:itg}}. -The \textsc{Figure~\ref{graphe1}} shows what happens when +Figure~\ref{fig:itg}. +The Figure~\ref{graphe1} shows what happens when displaying each iteration result. -On the contrary, the \textsc{Figure~\ref{graphe2}} explicits the behaviors +On the contrary, Figure~\ref{graphe2} illustrates the behaviors when always applying either 2 or 3 modifications before generating results. Notice that here, orientations of arcs are not necessary since the function $f_0$ is equal to its inverse $f_0^{-1}$. @@ -539,9 +553,55 @@ and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is strongly connected. and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected. \end{proof} -The next section recalls a general scheme to produce -functions and a iteration number $b$ -such that $\Gamma_{\{b\}}$ is strongly connected. + +\subsection{Comparison with other well-known generators} + +\begin{table} +\centering + \begin{tabular}{c|ccccccc} + PRNG & LCG & MRG & AWC & SWB & SWC & GFSR & INV\\ + \hline + NIST & 11 & 14 & 15 & 15 & 14 & 14 & 14\\ + DieHARD & 16 & 16 & 15 & 16 &18 & 16 & 16 + \end{tabular} + \caption{Statistical evaluation of known PRNGs: number of succeeded tests} + \label{table:comparisonWithout} +\end{table} + +\begin{table} +\centering + \begin{tabular}{c|ccccccc} + PRNG & LCG & MRG & AWC & SWB & SWC & GFSR & INV\\ + \hline + NIST & 15 & 15 & 15 & 15 & 15 & 15 & 15\\ + DieHARD & 18 & 18 & 18 & 18 & 18 & 18 & 18 + \end{tabular} + \caption{Statistical effects of CIPRNG on the succeeded tests} + \label{table:comparisonWith} +\end{table} +The objective of this section is to evaluate the statistical performance of the +proposed CIPRNG method, by comparing the effects of its application on well-known +but defective generators. We considered during experiments the following PRNGs: +linear congruential generator (LCG), multiple recursive generators (MRG) +add-with-carry (AWC), subtract-with-borrow (SWB), shift-with-carry (SWC) +Generalized Feedback Shift Register (GFSR), and nonlinear inversive generator. +A general overview and a recall of design of these famous generators +can be found, for instance, in the documentation of the TestU01 statistical +battery of tests~\cite{LEcuyerS07}. For each studied generator, we have compared +their scores according to both NIST~\cite{Nist10} and DieHARD~\cite{Marsaglia1996} +statistical batteries of tests, by launching them alone or inside the $\textit{CIPRNG}_f^2(v,v)$ +dynamical system, where $v$ is the considered PRNG set with most usual parameters, +and $f$ is the vectorial negation. + +Obtained results are reproduced in Tables~\ref{table:comparisonWithout} and \ref{table:comparisonWith}. +As can be seen, all these generators considered alone failed to pass either the 15 NIST tests or the +18 DieHARD ones, while both batteries of tests are always passed when applying the $\textit{CIPRNG}_f^2$ +post-treatment. Other results in the same direction, which can be found in~\cite{bfgw11:ip}, illustrate +the fact that operating a provable chaotic post-treatment on defective generators tends to improve +their statistical profile. + +Such post-treatment depending on the properties of the inputted function $f$, we need to recall a general scheme to produce +functions and an iteration number $b$ such that $\Gamma_{\{b\}}$ is strongly connected. %%% Local Variables: diff --git a/conclusion.tex b/conclusion.tex index e49ff17..6a24bc6 100644 --- a/conclusion.tex +++ b/conclusion.tex @@ -1,14 +1,14 @@ This work has assumed a Boolean map $f$ which is embedded into a discrete-time dynamical system $G_f$. This one is supposed to be iterated a fixed number -$p_1$ or $p_2$,\ldots, or $p_{\mathds{p}}$ of +$p_1$ or $p_2$,\ldots, or $p_{\mathds{p}}$ times before its output is considered. This work has first shown that iterations of $G_f$ are chaotic if and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is strongly connected where $\mathcal{P}$ is $\{p_1, \ldots, p_{\mathds{p}}\}$. -It can be deduced that in such a situation a PRNG, which iterates $G_f$ +It can be deduced that in such a situation a PRNG, which iterates $G_f$, satisfies the property of chaos and can be used in simulating chaos -phenomenon. +phenomena. We then have shown that a previously presented approach can be directly applied here to generate function $f$ with strongly connected @@ -21,18 +21,17 @@ into this new $\mathsf{N}$-cube. We have exhibit an efficient method to compute such a balanced Hamiltonian cycle. This method is an algebraic solution of an undeterministic approach~\cite{ZanSup04} and has a low complexity. -According to the author knowledge, this is the first time a full +According to the authors knowledge, this is the first time a full automatic method to provide chaotic PRNGs is given. Practically speaking, this approach preserves the security properties of the embedded PRNG, even if it remains quite cost expensive. -We furthermore have exhibited a upper bound on the number of iterations -that is sufficient to obtain a uniform distribution of the output. -Such a upper bound is quadratic on the number of bits to output. +We furthermore have exhibited an upper bound on the number of iterations +that is sufficient to obtain an uniform distribution of the output. +Such an upper bound is quadratic on the number of bits to output. Experiments have however shown that such a bound is in $\mathsf{N}.\log(\mathsf{N})$ in practice. - Finally, experiments through the NIST battery have shown that the statistical properties are almost established for $\mathsf{N} = 4, 5, 6, 7, 8$ and should be observed for any @@ -44,7 +43,6 @@ the associated iterations. By doing so, relations between desired statistically unbiased behaviors and topological properties will be understood, leading to better choices in iteration functions. - Conditions allowing the reduction of the stopping-time will be investigated too, while other modifications of the hypercube will be regarded in order to enlarge the set of known chaotic diff --git a/elsarticle-harv.bst b/elsarticle-harv.bst new file mode 100644 index 0000000..fb668b8 --- /dev/null +++ b/elsarticle-harv.bst @@ -0,0 +1,1537 @@ +%% +%% Copyright 2007, 2008, 2009 Elsevier Ltd +%% +%% This file is part of the 'Elsarticle Bundle'. +%% --------------------------------------------- +%% +%% It may be distributed under the conditions of the LaTeX Project Public +%% License, either version 1.2 of this license or (at your option) any +%% later version. The latest version of this license is in +%% http://www.latex-project.org/lppl.txt +%% and version 1.2 or later is part of all distributions of LaTeX +%% version 1999/12/01 or later. +%% +%% The list of all files belonging to the 'Elsarticle Bundle' is +%% given in the file `manifest.txt'. +%% + + %%------------------------------------------------------------------- + %% This bibliography style file is intended for texts in ENGLISH + %% This is an author-year citation style bibliography. As such, it is + %% non-standard LaTeX, and requires a special package file + %% to function properly. + %% Such a package is natbib.sty by Patrick W. Daly + %% The form of the \bibitem entries is + %% \bibitem[Jones et al.(1990)]{key}... + %% \bibitem[Jones et al.(1990)Jones, Baker, and Smith]{key}... + %% The essential feature is that the label (the part in brackets) consists + %% of the author names, as they should appear in the citation, with the year + %% in parentheses following. There must be no space before the opening + %% parenthesis! + %% With natbib v5.3, a full list of authors may also follow the year. + %% In natbib.sty, it is possible to define the type of enclosures that is + %% really wanted (brackets or parentheses), but in either case, there must + %% be parentheses in the label. + %% The \cite command functions as follows: + %% \citet{key} ==>> Jones et al. (1990) + %% \citet*{key} ==>> Jones, Baker, and Smith (1990) + %% \citep{key} ==>> (Jones et al., 1990) + %% \citep*{key} ==>> (Jones, Baker, and Smith, 1990) + %% \citep[chap. 2]{key} ==>> (Jones et al., 1990, chap. 2) + %% \citep[e.g.][]{key} ==>> (e.g. Jones et al., 1990) + %% \citep[e.g.][p. 32]{key} ==>> (e.g. Jones et al., p. 32) + %% \citeauthor{key} ==>> Jones et al. + %% \citeauthor*{key} ==>> Jones, Baker, and Smith + %% \citeyear{key} ==>> 1990 + %%--------------------------------------------------------------------- + +ENTRY + { address + author + booktitle + chapter + edition + editor + howpublished + institution + journal + key + month + note + number + organization + pages + publisher + school + series + title + type + url + volume + year + } + {} + { label extra.label sort.label short.list } + +INTEGERS { output.state before.all mid.sentence after.sentence after.block } + +FUNCTION {init.state.consts} +{ #0 'before.all := + #1 'mid.sentence := + #2 'after.sentence := + #3 'after.block := +} + +STRINGS { s t } + +FUNCTION {output.nonnull} +{ 's := + output.state mid.sentence = + { ", " * write$ } + { output.state after.block = + { add.period$ write$ + newline$ + "\newblock " write$ + } + { output.state before.all = + 'write$ + { add.period$ " " * write$ } + if$ + } + if$ + mid.sentence 'output.state := + } + if$ + s +} + +FUNCTION {output} +{ duplicate$ empty$ + 'pop$ + 'output.nonnull + if$ +} + +FUNCTION {output.check} +{ 't := + duplicate$ empty$ + { pop$ "empty " t * " in " * cite$ * warning$ } + 'output.nonnull + if$ +} + +FUNCTION {fin.entry} +{ add.period$ + write$ + newline$ +} + +FUNCTION {new.block} +{ output.state before.all = + 'skip$ + { after.block 'output.state := } + if$ +} + +FUNCTION {new.sentence} +{ output.state after.block = + 'skip$ + { output.state before.all = + 'skip$ + { after.sentence 'output.state := } + if$ + } + if$ +} + +%%SP 2003/07/25 +%% No longer used +FUNCTION {add.blank} +{ " " * before.all 'output.state := +} + +FUNCTION {date.block} +{ + new.sentence +} + +FUNCTION {not} +{ { #0 } + { #1 } + if$ +} + +FUNCTION {and} +{ 'skip$ + { pop$ #0 } + if$ +} + +FUNCTION {or} +{ { pop$ #1 } + 'skip$ + if$ +} + +FUNCTION {new.block.checkb} +{ empty$ + swap$ empty$ + and + 'skip$ + 'new.block + if$ +} + +FUNCTION {field.or.null} +{ duplicate$ empty$ + { pop$ "" } + 'skip$ + if$ +} + +FUNCTION {emphasize} +{ skip$ } + +FUNCTION {capitalize} +{ "u" change.case$ "t" change.case$ } + +FUNCTION {space.word} +{ " " swap$ * " " * } + + %% Here are the language-specific definitions for explicit words. + %% Each function has a name bbl.xxx where xxx is the English word. + %% The language selected here is ENGLISH +FUNCTION {bbl.and} +{ "and"} + +FUNCTION {bbl.etal} +{ "et~al." } + +FUNCTION {bbl.editors} +{ "Eds." } + +FUNCTION {bbl.editor} +{ "Ed." } + +FUNCTION {bbl.edby} +{ "edited by" } + +FUNCTION {bbl.edition} +{ "Edition" } + +FUNCTION {bbl.volume} +{ "Vol." } + +FUNCTION {bbl.of} +{ "of" } + +FUNCTION {bbl.number} +{ "no." } + +FUNCTION {bbl.nr} +{ "no." } + +FUNCTION {bbl.in} +{ "in" } + +FUNCTION {bbl.pages} +{ "pp." } + +FUNCTION {bbl.page} +{ "p." } + +FUNCTION {bbl.chapter} +{ "Ch." } + +FUNCTION {bbl.techrep} +{ "Tech. Rep." } + +FUNCTION {bbl.mthesis} +{ "Master's thesis" } + +FUNCTION {bbl.phdthesis} +{ "Ph.D. thesis" } + +FUNCTION {bbl.first} +{ "1st" } + +FUNCTION {bbl.second} +{ "2nd" } + +FUNCTION {bbl.third} +{ "3rd" } + +FUNCTION {bbl.fourth} +{ "4th" } + +FUNCTION {bbl.fifth} +{ "5th" } + +FUNCTION {bbl.st} +{ "st" } + +FUNCTION {bbl.nd} +{ "nd" } + +FUNCTION {bbl.rd} +{ "rd" } + +FUNCTION {bbl.th} +{ "th" } + +MACRO {jan} {"Jan."} + +MACRO {feb} {"Feb."} + +MACRO {mar} {"Mar."} + +MACRO {apr} {"Apr."} + +MACRO {may} {"May"} + +MACRO {jun} {"Jun."} + +MACRO {jul} {"Jul."} + +MACRO {aug} {"Aug."} + +MACRO {sep} {"Sep."} + +MACRO {oct} {"Oct."} + +MACRO {nov} {"Nov."} + +MACRO {dec} {"Dec."} + +FUNCTION {eng.ord} +{ duplicate$ "1" swap$ * + #-2 #1 substring$ "1" = + { bbl.th * } + { duplicate$ #-1 #1 substring$ + duplicate$ "1" = + { pop$ bbl.st * } + { duplicate$ "2" = + { pop$ bbl.nd * } + { "3" = + { bbl.rd * } + { bbl.th * } + if$ + } + if$ + } + if$ + } + if$ +} + +MACRO {acmcs} {"ACM Comput. Surv."} + +MACRO {acta} {"Acta Inf."} + +MACRO {cacm} {"Commun. ACM"} + +MACRO {ibmjrd} {"IBM J. Res. Dev."} + +MACRO {ibmsj} {"IBM Syst.~J."} + +MACRO {ieeese} {"IEEE Trans. Softw. Eng."} + +MACRO {ieeetc} {"IEEE Trans. Comput."} + +MACRO {ieeetcad} + {"IEEE Trans. Comput.-Aided Design Integrated Circuits"} + +MACRO {ipl} {"Inf. Process. Lett."} + +MACRO {jacm} {"J.~ACM"} + +MACRO {jcss} {"J.~Comput. Syst. Sci."} + +MACRO {scp} {"Sci. Comput. Programming"} + +MACRO {sicomp} {"SIAM J. Comput."} + +MACRO {tocs} {"ACM Trans. Comput. Syst."} + +MACRO {tods} {"ACM Trans. Database Syst."} + +MACRO {tog} {"ACM Trans. Gr."} + +MACRO {toms} {"ACM Trans. Math. Softw."} + +MACRO {toois} {"ACM Trans. Office Inf. Syst."} + +MACRO {toplas} {"ACM Trans. Prog. Lang. Syst."} + +MACRO {tcs} {"Theoretical Comput. Sci."} + +FUNCTION {write.url} +{ url empty$ + { skip$ } + { "\newline\urlprefix\url{" url * "}" * write$ newline$ } + if$ +} + +INTEGERS { nameptr namesleft numnames } + +FUNCTION {format.names} +{ 's := + #1 'nameptr := + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { s nameptr + "{vv~}{ll}{, jj}{, f.}" format.name$ + 't := + nameptr #1 > + { + namesleft #1 > + { ", " * t * } + { + "," * + s nameptr "{ll}" format.name$ duplicate$ "others" = + { 't := } + { pop$ } + if$ + t "others" = + { + " " * bbl.etal * + } + { " " * t * } + if$ + } + if$ + } + 't + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ +} +FUNCTION {format.names.ed} +{ format.names } +FUNCTION {format.key} +{ empty$ + { key field.or.null } + { "" } + if$ +} + +FUNCTION {format.authors} +{ author empty$ + { "" } + { author format.names } + if$ +} + +FUNCTION {format.editors} +{ editor empty$ + { "" } + { editor format.names + editor num.names$ #1 > + { " (" * bbl.editors * ")" * } + { " (" * bbl.editor * ")" * } + if$ + } + if$ +} + +FUNCTION {format.in.editors} +{ editor empty$ + { "" } + { editor format.names.ed + editor num.names$ #1 > + { " (" * bbl.editors * ")" * } + { " (" * bbl.editor * ")" * } + if$ + } + if$ +} + +FUNCTION {format.note} +{ + note empty$ + { "" } + { note #1 #1 substring$ + duplicate$ "{" = + 'skip$ + { output.state mid.sentence = + { "l" } + { "u" } + if$ + change.case$ + } + if$ + note #2 global.max$ substring$ * + } + if$ +} + +FUNCTION {format.title} +{ title empty$ + { "" } + { title "t" change.case$ + } + if$ +} + +FUNCTION {format.full.names} +{'s := + #1 'nameptr := + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { s nameptr + "{vv~}{ll}" format.name$ + 't := + nameptr #1 > + { + namesleft #1 > + { ", " * t * } + { + numnames #2 > + { "," * } + 'skip$ + if$ + s nameptr "{ll}" format.name$ duplicate$ "others" = + { 't := } + { pop$ } + if$ + t "others" = + { + " " * bbl.etal * + } + { bbl.and + space.word * t * + } + if$ + } + if$ + } + 't + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ +} + +FUNCTION {author.editor.key.full} +{ author empty$ + { editor empty$ + { key empty$ + { cite$ #1 #3 substring$ } + 'key + if$ + } + { editor format.full.names } + if$ + } + { author format.full.names } + if$ +} + +FUNCTION {author.key.full} +{ author empty$ + { key empty$ + { cite$ #1 #3 substring$ } + 'key + if$ + } + { author format.full.names } + if$ +} + +FUNCTION {editor.key.full} +{ editor empty$ + { key empty$ + { cite$ #1 #3 substring$ } + 'key + if$ + } + { editor format.full.names } + if$ +} + +FUNCTION {make.full.names} +{ type$ "book" = + type$ "inbook" = + or + 'author.editor.key.full + { type$ "proceedings" = + 'editor.key.full + 'author.key.full + if$ + } + if$ +} + +FUNCTION {output.bibitem} +{ newline$ + "\bibitem[{" write$ + label write$ + ")" make.full.names duplicate$ short.list = + { pop$ } + { * } + if$ + "}]{" * write$ + cite$ write$ + "}" write$ + newline$ + "" + before.all 'output.state := +} + +FUNCTION {n.dashify} +{ + 't := + "" + { t empty$ not } + { t #1 #1 substring$ "-" = + { t #1 #2 substring$ "--" = not + { "--" * + t #2 global.max$ substring$ 't := + } + { { t #1 #1 substring$ "-" = } + { "-" * + t #2 global.max$ substring$ 't := + } + while$ + } + if$ + } + { t #1 #1 substring$ * + t #2 global.max$ substring$ 't := + } + if$ + } + while$ +} + +FUNCTION {word.in} +{ bbl.in capitalize + ":" * + " " * } + +FUNCTION {format.date} +{ year duplicate$ empty$ + { "empty year in " cite$ * "; set to ????" * warning$ + pop$ "????" } + 'skip$ + if$ + month empty$ + 'skip$ + { month + " " * swap$ * + } + if$ + extra.label * + before.all 'output.state := + ", " swap$ * +} + +FUNCTION {format.btitle} +{ title +} + +FUNCTION {tie.or.space.connect} +{ duplicate$ text.length$ #3 < + { "~" } + { " " } + if$ + swap$ * * +} + +FUNCTION {either.or.check} +{ empty$ + 'pop$ + { "can't use both " swap$ * " fields in " * cite$ * warning$ } + if$ +} + +FUNCTION {format.bvolume} +{ volume empty$ + { "" } + { bbl.volume volume tie.or.space.connect + series empty$ + 'skip$ + { bbl.of space.word * series emphasize * } + if$ + "volume and number" number either.or.check + } + if$ +} + +FUNCTION {format.number.series} +{ volume empty$ + { number empty$ + { series field.or.null } + { output.state mid.sentence = + { bbl.number } + { bbl.number capitalize } + if$ + number tie.or.space.connect + series empty$ + { "there's a number but no series in " cite$ * warning$ } + { bbl.in space.word * series * } + if$ + } + if$ + } + { "" } + if$ +} + +FUNCTION {is.num} +{ chr.to.int$ + duplicate$ "0" chr.to.int$ < not + swap$ "9" chr.to.int$ > not and +} + +FUNCTION {extract.num} +{ duplicate$ 't := + "" 's := + { t empty$ not } + { t #1 #1 substring$ + t #2 global.max$ substring$ 't := + duplicate$ is.num + { s swap$ * 's := } + { pop$ "" 't := } + if$ + } + while$ + s empty$ + 'skip$ + { pop$ s } + if$ +} + +FUNCTION {convert.edition} +{ edition extract.num "l" change.case$ 's := + s "first" = s "1" = or + { bbl.first 't := } + { s "second" = s "2" = or + { bbl.second 't := } + { s "third" = s "3" = or + { bbl.third 't := } + { s "fourth" = s "4" = or + { bbl.fourth 't := } + { s "fifth" = s "5" = or + { bbl.fifth 't := } + { s #1 #1 substring$ is.num + { s eng.ord 't := } + { edition 't := } + if$ + } + if$ + } + if$ + } + if$ + } + if$ + } + if$ + t +} + +FUNCTION {format.edition} +{ edition empty$ + { "" } + { output.state mid.sentence = + { convert.edition "l" change.case$ " " * bbl.edition * } + { convert.edition "t" change.case$ " " * bbl.edition * } + if$ + } + if$ +} + +INTEGERS { multiresult } + +FUNCTION {multi.page.check} +{ 't := + #0 'multiresult := + { multiresult not + t empty$ not + and + } + { t #1 #1 substring$ + duplicate$ "-" = + swap$ duplicate$ "," = + swap$ "+" = + or or + { #1 'multiresult := } + { t #2 global.max$ substring$ 't := } + if$ + } + while$ + multiresult +} + +FUNCTION {format.pages} +{ pages empty$ + { "" } + { pages multi.page.check + { bbl.pages pages n.dashify tie.or.space.connect } + { bbl.page pages tie.or.space.connect } + if$ + } + if$ +} + +FUNCTION {format.journal.pages} +{ pages empty$ + 'skip$ + { duplicate$ empty$ + { pop$ format.pages } + { + ", " * + pages n.dashify * + } + if$ + } + if$ +} + +%%SP 2001/01/23 +%% Only used in articles +FUNCTION {format.vol.num.pages} +{ +%%SP 2001/01/23 +%% Add the leading space only if there is a volume + %% volume field.or.null + " " + volume empty$ + { pop$ "" } + { volume * } + if$ + number empty$ + 'skip$ + { + "~(" number * ")" * * + volume empty$ + { "there's a number but no volume in " cite$ * warning$ } + 'skip$ + if$ + } + if$ +} + +FUNCTION {format.chapter.pages} +{ chapter empty$ + { "" } + { type empty$ + { bbl.chapter } + { type "l" change.case$ } + if$ + chapter tie.or.space.connect + } + if$ +} + +FUNCTION {format.in.ed.booktitle} +{ booktitle empty$ + { "" } + { editor empty$ + { word.in booktitle * } + { word.in format.in.editors * ", " * + booktitle * } + if$ + } + if$ +} + +FUNCTION {format.thesis.type} +{ type empty$ + 'skip$ + { pop$ + type "t" change.case$ + } + if$ +} + +FUNCTION {format.tr.number} +{ type empty$ + { bbl.techrep } + 'type + if$ + number empty$ + { "t" change.case$ } + { number tie.or.space.connect } + if$ +} + +FUNCTION {format.article.crossref} +{ + word.in + " \cite{" * crossref * "}" * +} + +FUNCTION {format.book.crossref} +{ volume empty$ + { "empty volume in " cite$ * "'s crossref of " * crossref * warning$ + word.in + } + { bbl.volume capitalize + volume tie.or.space.connect + bbl.of space.word * + } + if$ + " \cite{" * crossref * "}" * +} + +FUNCTION {format.incoll.inproc.crossref} +{ + word.in + " \cite{" * crossref * "}" * +} + +FUNCTION {format.org.or.pub} +{ 't := + "" + address empty$ t empty$ and + 'skip$ + { + t empty$ + { address empty$ + 'skip$ + { address * } + if$ + } + { t * + address empty$ + 'skip$ + { ", " * address * } + if$ + } + if$ + } + if$ +} + +FUNCTION {format.publisher.address} +{ publisher empty$ + { "empty publisher in " cite$ * warning$ + "" + } + { publisher } + if$ + format.org.or.pub +} + +FUNCTION {format.organization.address} +{ organization empty$ + { "" } + { organization } + if$ + format.org.or.pub +} + +FUNCTION {article} +{ output.bibitem + format.authors "author" output.check + author format.key output + format.date "year" output.check + date.block + format.title "title" output.check + new.sentence + crossref missing$ + { journal + "journal" output.check +%%SP 2001/01/23 +%% Add the space in format.vol.num.pages + %% add.blank + before.all 'output.state := + format.vol.num.pages output + } + { format.article.crossref output.nonnull + format.pages output + } + if$ + format.journal.pages + format.note output + fin.entry + write.url +} + +FUNCTION {book} +{ output.bibitem + author empty$ + { format.editors "author and editor" output.check + editor format.key output + } + { format.authors output.nonnull + crossref missing$ + { "author and editor" editor either.or.check } + 'skip$ + if$ + } + if$ + format.date "year" output.check + date.block + format.btitle "title" output.check + crossref missing$ + { format.edition output + new.sentence + format.bvolume output + format.number.series output + new.sentence + format.publisher.address output + } + { + new.sentence + format.book.crossref output.nonnull + } + if$ + format.note output + fin.entry + write.url +} + +FUNCTION {booklet} +{ output.bibitem + format.authors output + author format.key output + format.date "year" output.check + date.block + format.title "title" output.check + new.sentence + howpublished output + address output + format.note output + fin.entry + write.url +} + +FUNCTION {inbook} +{ output.bibitem + author empty$ + { format.editors "author and editor" output.check + editor format.key output + } + { format.authors output.nonnull + crossref missing$ + { "author and editor" editor either.or.check } + 'skip$ + if$ + } + if$ + format.date "year" output.check + date.block + format.btitle "title" output.check + crossref missing$ + { + format.edition output + new.sentence + format.bvolume output + format.number.series output + new.sentence + format.publisher.address output + format.chapter.pages "chapter and pages" output.check + } + { + format.chapter.pages "chapter and pages" output.check + new.sentence + format.book.crossref output.nonnull + } + if$ + format.pages "pages" output.check + format.note output + fin.entry + write.url +} + +FUNCTION {incollection} +{ output.bibitem + format.authors "author" output.check + author format.key output + format.date "year" output.check + date.block + format.title "title" output.check + new.sentence + crossref missing$ + { format.in.ed.booktitle "booktitle" output.check + format.edition output + new.sentence + format.bvolume output + format.number.series output + new.sentence + format.publisher.address output + format.chapter.pages output + } + { format.incoll.inproc.crossref output.nonnull + format.chapter.pages output + } + if$ + format.pages "pages" output.check + format.note output + fin.entry + write.url +} + +FUNCTION {inproceedings} +{ output.bibitem + format.authors "author" output.check + author format.key output + format.date "year" output.check + date.block + format.title "title" output.check + new.sentence + crossref missing$ + { format.in.ed.booktitle "booktitle" output.check + format.edition output + new.sentence + format.bvolume output + format.number.series output + new.sentence + publisher empty$ + { format.organization.address output } + { organization output + format.publisher.address output + } + if$ +%%SP 2001/01/23 +%% format.pages output + } + { format.incoll.inproc.crossref output.nonnull +%%SP 2001/01/23 +%% format.pages output + } + if$ +%%SP 2001/01/23 + format.pages "pages" output.check + format.note output + fin.entry + write.url +} + +FUNCTION {conference} { inproceedings } + +FUNCTION {manual} +{ output.bibitem + format.authors output + author format.key output + format.date "year" output.check + date.block + format.btitle "title" output.check + new.sentence + organization output + address output + format.edition output + format.note output + fin.entry + write.url +} + +FUNCTION {mastersthesis} +{ output.bibitem + format.authors "author" output.check + author format.key output + format.date "year" output.check + date.block + format.title "title" output.check + new.sentence + bbl.mthesis format.thesis.type output.nonnull + school "school" output.check + address output + format.note output + fin.entry + write.url +} + +FUNCTION {misc} +{ output.bibitem + format.authors output + author format.key output + format.date "year" output.check + date.block + format.title output + new.sentence + howpublished output + format.note output + fin.entry + write.url +} + +FUNCTION {phdthesis} +{ output.bibitem + format.authors "author" output.check + author format.key output + format.date "year" output.check + date.block + format.title "title" output.check + new.sentence + bbl.phdthesis format.thesis.type output.nonnull + school "school" output.check + address output + format.note output + fin.entry + write.url +} + +FUNCTION {proceedings} +{ output.bibitem + format.editors output + editor format.key output + format.date "year" output.check + date.block + format.btitle "title" output.check + new.sentence + format.bvolume output + format.number.series output + new.sentence + publisher empty$ + { format.organization.address output } + { organization output + format.publisher.address output + } + if$ + format.note output + fin.entry + write.url +} + +FUNCTION {techreport} +{ output.bibitem + format.authors "author" output.check + author format.key output + format.date "year" output.check + date.block + format.title "title" output.check + new.sentence + format.tr.number output.nonnull + institution "institution" output.check + address output + format.note output + fin.entry + write.url +} + +FUNCTION {unpublished} +{ output.bibitem + format.authors "author" output.check + author format.key output + format.date "year" output.check + date.block + format.title "title" output.check + format.note "note" output.check + fin.entry + write.url +} + +FUNCTION {default.type} { misc } + +READ + +FUNCTION {sortify} +{ purify$ + "l" change.case$ +} + +INTEGERS { len } + +FUNCTION {chop.word} +{ 's := + 'len := + s #1 len substring$ = + { s len #1 + global.max$ substring$ } + 's + if$ +} + +FUNCTION {format.lab.names} +{ 's := + s #1 "{vv~}{ll}" format.name$ + s num.names$ duplicate$ + #2 > + { pop$ + " " * bbl.etal * + } + { #2 < + 'skip$ + { s #2 "{ff }{vv }{ll}{ jj}" format.name$ "others" = + { + " " * bbl.etal * + } + { bbl.and space.word * s #2 "{vv~}{ll}" format.name$ + * } + if$ + } + if$ + } + if$ +} + +FUNCTION {author.key.label} +{ author empty$ + { key empty$ + { cite$ #1 #3 substring$ } + 'key + if$ + } + { author format.lab.names } + if$ +} + +FUNCTION {author.editor.key.label} +{ author empty$ + { editor empty$ + { key empty$ + { cite$ #1 #3 substring$ } + 'key + if$ + } + { editor format.lab.names } + if$ + } + { author format.lab.names } + if$ +} + +FUNCTION {editor.key.label} +{ editor empty$ + { key empty$ + { cite$ #1 #3 substring$ } + 'key + if$ + } + { editor format.lab.names } + if$ +} + +FUNCTION {calc.short.authors} +{ type$ "book" = + type$ "inbook" = + or + 'author.editor.key.label + { type$ "proceedings" = + 'editor.key.label + 'author.key.label + if$ + } + if$ + 'short.list := +} + +FUNCTION {calc.label} +{ calc.short.authors + short.list + "(" + * + year duplicate$ empty$ + { pop$ "????" } + 'skip$ + if$ + * + 'label := +} + +FUNCTION {sort.format.names} +{ 's := + #1 'nameptr := + "" + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { s nameptr + "{vv{ } }{ll{ }}{ f{ }}{ jj{ }}" + format.name$ 't := + nameptr #1 > + { + " " * + namesleft #1 = t "others" = and + { "zzzzz" * } + { t sortify * } + if$ + } + { t sortify * } + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ +} + +FUNCTION {sort.format.title} +{ 't := + "A " #2 + "An " #3 + "The " #4 t chop.word + chop.word + chop.word + sortify + #1 global.max$ substring$ +} + +FUNCTION {author.sort} +{ author empty$ + { key empty$ + { "to sort, need author or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { author sort.format.names } + if$ +} + +FUNCTION {author.editor.sort} +{ author empty$ + { editor empty$ + { key empty$ + { "to sort, need author, editor, or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { editor sort.format.names } + if$ + } + { author sort.format.names } + if$ +} + +FUNCTION {editor.sort} +{ editor empty$ + { key empty$ + { "to sort, need editor or key in " cite$ * warning$ + "" + } + { key sortify } + if$ + } + { editor sort.format.names } + if$ +} + +FUNCTION {presort} +{ calc.label + label sortify + " " + * + type$ "book" = + type$ "inbook" = + or + 'author.editor.sort + { type$ "proceedings" = + 'editor.sort + 'author.sort + if$ + } + if$ + #1 entry.max$ substring$ + 'sort.label := + sort.label + * + " " + * + title field.or.null + sort.format.title + * + #1 entry.max$ substring$ + 'sort.key$ := +} + +ITERATE {presort} + +SORT + +STRINGS { last.label next.extra } + +INTEGERS { last.extra.num number.label } + +FUNCTION {initialize.extra.label.stuff} +{ #0 int.to.chr$ 'last.label := + "" 'next.extra := + #0 'last.extra.num := + #0 'number.label := +} + +FUNCTION {forward.pass} +{ last.label label = + { last.extra.num #1 + 'last.extra.num := + last.extra.num int.to.chr$ 'extra.label := + } + { "a" chr.to.int$ 'last.extra.num := + "" 'extra.label := + label 'last.label := + } + if$ + number.label #1 + 'number.label := +} + +FUNCTION {reverse.pass} +{ next.extra "b" = + { "a" 'extra.label := } + 'skip$ + if$ + extra.label 'next.extra := + extra.label + duplicate$ empty$ + 'skip$ + { "{\natexlab{" swap$ * "}}" * } + if$ + 'extra.label := + label extra.label * 'label := +} + +EXECUTE {initialize.extra.label.stuff} + +ITERATE {forward.pass} + +REVERSE {reverse.pass} + +FUNCTION {bib.sort.order} +{ sort.label + " " + * + year field.or.null sortify + * + " " + * + title field.or.null + sort.format.title + * + #1 entry.max$ substring$ + 'sort.key$ := +} + +ITERATE {bib.sort.order} + +SORT + +FUNCTION {begin.bib} +{ preamble$ empty$ + 'skip$ + { preamble$ write$ newline$ } + if$ + "\begin{thebibliography}{" number.label int.to.str$ * "}" * + write$ newline$ + "\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi" + write$ newline$ + "\expandafter\ifx\csname url\endcsname\relax" + write$ newline$ + " \def\url#1{\texttt{#1}}\fi" + write$ newline$ + "\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi" + write$ newline$ +} + +EXECUTE {begin.bib} + +EXECUTE {init.state.consts} + +ITERATE {call.type$} + +FUNCTION {end.bib} +{ newline$ + "\end{thebibliography}" write$ newline$ +} + +EXECUTE {end.bib} +%% End of customized bst file +%% +%% End of file `elsarticle-harv.bst'. diff --git a/elsarticle-num.bst b/elsarticle-num.bst new file mode 100644 index 0000000..0257b4f --- /dev/null +++ b/elsarticle-num.bst @@ -0,0 +1,1517 @@ +%% +%% Copyright 2007, 2008, 2009 Elsevier Ltd +%% +%% This file is part of the 'Elsarticle Bundle'. +%% --------------------------------------------- +%% +%% It may be distributed under the conditions of the LaTeX Project Public +%% License, either version 1.2 of this license or (at your option) any +%% later version. The latest version of this license is in +%% http://www.latex-project.org/lppl.txt +%% and version 1.2 or later is part of all distributions of LaTeX +%% version 1999/12/01 or later. +%% +%% The list of all files belonging to the 'Elsarticle Bundle' is +%% given in the file `manifest.txt'. +%% +%%% Modification of BibTeX style file elsarticle-num.bst +%%% ... by urlbst, version 0.6 (marked with "% urlbst") +%%% See +%%% Added webpage entry type, and url and lastchecked fields. +%%% Added eprint support. +%%% Added DOI support. +%%% Added hyperref support. +%%% Original headers follow... + +%% +%% This is file `elsarticle-num.bst', +%% generated with the docstrip utility. +%% +%% The original source files were: +%% +%% merlin.mbs (with options: `,seq-no,nm-init,ed-au,dt-end,yr-par,yrp-x,jttl-rm,thtit-a,vnum-sp,volp-blk,jdt-p,pp-last,jnm-x,btit-rm,bt-rm,pub-date,pub-xpar,pre-edn,url,url-nl,edpar,blk-com,in-col,pp,ed,abr,ednx,ord,jabr,and-xcom,xand,em-x,nfss') +%% After docstrip generation some manual changes were made (SP) + +%% ---------------------------------------- + +ENTRY + { address + author + booktitle + chapter + edition + editor + howpublished + institution + journal + key + month + note + number + organization + pages + publisher + school + series + title + type + volume + year + eprint % urlbst + doi % urlbst + url % urlbst + lastchecked % urlbst + } + {} + { label } + +INTEGERS { output.state before.all mid.sentence after.sentence after.block } + +STRINGS { urlintro eprinturl eprintprefix doiprefix doiurl openinlinelink closeinlinelink } % urlbst... +INTEGERS { hrefform inlinelinks makeinlinelink addeprints adddoiresolver } +FUNCTION {init.urlbst.variables} +{ + "Available from: " 'urlintro := % prefix before URL + "http://arxiv.org/abs/" 'eprinturl := % prefix to make URL from eprint ref + "arXiv:" 'eprintprefix := % text prefix printed before eprint ref + "http://dx.doi.org/" 'doiurl := % prefix to make URL from DOI + "doi:" 'doiprefix := % text prefix printed before DOI ref + #1 'addeprints := % 0=no eprints; 1=include eprints + #1 'adddoiresolver := % 0=no DOI resolver; 1=include it + #2 'hrefform := % 0=no crossrefs; 1=hypertex xrefs; 2=hyperref refs + #1 'inlinelinks := % 0=URLs explicit; 1=URLs attached to titles + % the following are internal state variables, not config constants + #0 'makeinlinelink := % state variable managed by setup.inlinelink + "" 'openinlinelink := % ditto + "" 'closeinlinelink := % ditto +} +INTEGERS { + bracket.state + outside.brackets + open.brackets + within.brackets + close.brackets +} +FUNCTION {init.state.consts} +{ #0 'outside.brackets := % urlbst + #1 'open.brackets := + #2 'within.brackets := + #3 'close.brackets := + + #0 'before.all := + #1 'mid.sentence := + #2 'after.sentence := + #3 'after.block := +} + +STRINGS { s t } + +FUNCTION {output.nonnull.original} +{ 's := + output.state mid.sentence = + { ", " * write$ } + { output.state after.block = + { add.period$ write$ + newline$ + "\newblock " write$ + } + { output.state before.all = + 'write$ + { add.period$ " " * write$ } + if$ + } + if$ + mid.sentence 'output.state := + } + if$ + s +} + +FUNCTION {setup.inlinelink} +{ makeinlinelink + { hrefform #1 = % hypertex + { "\special {html: }{" * 'openinlinelink := + "\special {html:}" 'closeinlinelink := + } + { hrefform #2 = % hyperref + { "\href{" url * "}{" * 'openinlinelink := + "}" 'closeinlinelink := + } + 'skip$ + if$ % hrefform #2 = + } + if$ % hrefform #1 = + #0 'makeinlinelink := + } + 'skip$ + if$ % makeinlinelink +} +FUNCTION {add.inlinelink} +{ openinlinelink empty$ + 'skip$ + { openinlinelink swap$ * closeinlinelink * + "" 'openinlinelink := + } + if$ +} +FUNCTION {output.nonnull} +{ % Save the thing we've been asked to output + 's := + % If the bracket-state is close.brackets, then add a close-bracket to + % what is currently at the top of the stack, and set bracket.state + % to outside.brackets + bracket.state close.brackets = + { "]" * + outside.brackets 'bracket.state := + } + 'skip$ + if$ + bracket.state outside.brackets = + { % We're outside all brackets -- this is the normal situation. + % Write out what's currently at the top of the stack, using the + % original output.nonnull function. + s + add.inlinelink + output.nonnull.original % invoke the original output.nonnull + } + { % Still in brackets. Add open-bracket or (continuation) comma, add the + % new text (in s) to the top of the stack, and move to the close-brackets + % state, ready for next time (unless inbrackets resets it). If we come + % into this branch, then output.state is carefully undisturbed. + bracket.state open.brackets = + { " [" * } + { ", " * } % bracket.state will be within.brackets + if$ + s * + close.brackets 'bracket.state := + } + if$ +} + +FUNCTION {inbrackets} +{ bracket.state close.brackets = + { within.brackets 'bracket.state := } % reset the state: not open nor closed + { open.brackets 'bracket.state := } + if$ +} + +FUNCTION {format.lastchecked} +{ lastchecked empty$ + { "" } + { inbrackets "cited " lastchecked * } + if$ +} + +FUNCTION {output} +{ duplicate$ empty$ + 'pop$ + 'output.nonnull + if$ +} + +FUNCTION {output.check} +{ 't := + duplicate$ empty$ + { pop$ "empty " t * " in " * cite$ * warning$ } + 'output.nonnull + if$ +} + +FUNCTION {fin.entry.original} +{ add.period$ + write$ + newline$ +} + +FUNCTION {new.block} +{ output.state before.all = + 'skip$ + { after.block 'output.state := } + if$ +} + +FUNCTION {new.sentence} +{ output.state after.block = + 'skip$ + { output.state before.all = + 'skip$ + { after.sentence 'output.state := } + if$ + } + if$ +} + +FUNCTION {add.blank} +{ " " * before.all 'output.state := +} + +FUNCTION {date.block} +{ + add.blank +} + +FUNCTION {not} +{ { #0 } + { #1 } + if$ +} + +FUNCTION {and} +{ 'skip$ + { pop$ #0 } + if$ +} + +FUNCTION {or} +{ { pop$ #1 } + 'skip$ + if$ +} + +FUNCTION {new.block.checka} +{ empty$ + 'skip$ + 'new.block + if$ +} + +FUNCTION {new.block.checkb} +{ empty$ + swap$ empty$ + and + 'skip$ + 'new.block + if$ +} + +FUNCTION {new.sentence.checka} +{ empty$ + 'skip$ + 'new.sentence + if$ +} + +FUNCTION {new.sentence.checkb} +{ empty$ + swap$ empty$ + and + 'skip$ + 'new.sentence + if$ +} + +FUNCTION {field.or.null} +{ duplicate$ empty$ + { pop$ "" } + 'skip$ + if$ +} + +FUNCTION {emphasize} +{ skip$ } + +FUNCTION {capitalize} +{ "u" change.case$ "t" change.case$ } + +FUNCTION {space.word} +{ " " swap$ * " " * } + + % Here are the language-specific definitions for explicit words. + % Each function has a name bbl.xxx where xxx is the English word. + % The language selected here is ENGLISH +FUNCTION {bbl.and} +{ "and"} + +FUNCTION {bbl.etal} +{ "et~al." } + +FUNCTION {bbl.editors} +{ "Eds." } + +FUNCTION {bbl.editor} +{ "Ed." } + +FUNCTION {bbl.edby} +{ "edited by" } + +FUNCTION {bbl.edition} +{ "Edition" } + +FUNCTION {bbl.volume} +{ "Vol." } + +FUNCTION {bbl.of} +{ "of" } + +FUNCTION {bbl.number} +{ "no." } + +FUNCTION {bbl.nr} +{ "no." } + +FUNCTION {bbl.in} +{ "in" } + +FUNCTION {bbl.pages} +{ "pp." } + +FUNCTION {bbl.page} +{ "p." } + +FUNCTION {bbl.chapter} +{ "Ch." } + +FUNCTION {bbl.techrep} +{ "Tech. Rep." } + +FUNCTION {bbl.mthesis} +{ "Master's thesis" } + +FUNCTION {bbl.phdthesis} +{ "Ph.D. thesis" } + +FUNCTION {bbl.first} +{ "1st" } + +FUNCTION {bbl.second} +{ "2nd" } + +FUNCTION {bbl.third} +{ "3rd" } + +FUNCTION {bbl.fourth} +{ "4th" } + +FUNCTION {bbl.fifth} +{ "5th" } + +FUNCTION {bbl.st} +{ "st" } + +FUNCTION {bbl.nd} +{ "nd" } + +FUNCTION {bbl.rd} +{ "rd" } + +FUNCTION {bbl.th} +{ "th" } + +MACRO {jan} {"Jan."} + +MACRO {feb} {"Feb."} + +MACRO {mar} {"Mar."} + +MACRO {apr} {"Apr."} + +MACRO {may} {"May"} + +MACRO {jun} {"Jun."} + +MACRO {jul} {"Jul."} + +MACRO {aug} {"Aug."} + +MACRO {sep} {"Sep."} + +MACRO {oct} {"Oct."} + +MACRO {nov} {"Nov."} + +MACRO {dec} {"Dec."} + +FUNCTION {eng.ord} +{ duplicate$ "1" swap$ * + #-2 #1 substring$ "1" = + { bbl.th * } + { duplicate$ #-1 #1 substring$ + duplicate$ "1" = + { pop$ bbl.st * } + { duplicate$ "2" = + { pop$ bbl.nd * } + { "3" = + { bbl.rd * } + { bbl.th * } + if$ + } + if$ + } + if$ + } + if$ +} + +MACRO {acmcs} {"ACM Comput. Surv."} + +MACRO {acta} {"Acta Inf."} + +MACRO {cacm} {"Commun. ACM"} + +MACRO {ibmjrd} {"IBM J. Res. Dev."} + +MACRO {ibmsj} {"IBM Syst.~J."} + +MACRO {ieeese} {"IEEE Trans. Softw. Eng."} + +MACRO {ieeetc} {"IEEE Trans. Comput."} + +MACRO {ieeetcad} + {"IEEE Trans. Comput.-Aided Design Integrated Circuits"} + +MACRO {ipl} {"Inf. Process. Lett."} + +MACRO {jacm} {"J.~ACM"} + +MACRO {jcss} {"J.~Comput. Syst. Sci."} + +MACRO {scp} {"Sci. Comput. Programming"} + +MACRO {sicomp} {"SIAM J. Comput."} + +MACRO {tocs} {"ACM Trans. Comput. Syst."} + +MACRO {tods} {"ACM Trans. Database Syst."} + +MACRO {tog} {"ACM Trans. Gr."} + +MACRO {toms} {"ACM Trans. Math. Softw."} + +MACRO {toois} {"ACM Trans. Office Inf. Syst."} + +MACRO {toplas} {"ACM Trans. Prog. Lang. Syst."} + +MACRO {tcs} {"Theoretical Comput. Sci."} + +FUNCTION {write.url} +{ url empty$ + { skip$ } + { "\newline\urlprefix\url{" url * "}" * write$ newline$ } + if$ +} + +INTEGERS { nameptr namesleft numnames } + +FUNCTION {format.names} +{ 's := + #1 'nameptr := + s num.names$ 'numnames := + numnames 'namesleft := + { namesleft #0 > } + { s nameptr + "{f.~}{vv~}{ll}{, jj}" format.name$ + 't := + nameptr #1 > + { + namesleft #1 > + { ", " * t * } + { + "," * + s nameptr "{ll}" format.name$ duplicate$ "others" = + { 't := } + { pop$ } + if$ + t "others" = + { + " " * bbl.etal * + } + { " " * t * } + if$ + } + if$ + } + 't + if$ + nameptr #1 + 'nameptr := + namesleft #1 - 'namesleft := + } + while$ +} +FUNCTION {format.names.ed} +{ format.names } +FUNCTION {format.authors} +{ author empty$ + { "" } + { author format.names } + if$ +} + +FUNCTION {format.editors} +{ editor empty$ + { "" } + { editor format.names + editor num.names$ #1 > + { " (" * bbl.editors * ")" * } + { " (" * bbl.editor * ")" * } + if$ + } + if$ +} + +FUNCTION {format.in.editors} +{ editor empty$ + { "" } + { editor format.names.ed + editor num.names$ #1 > + { " (" * bbl.editors * ")" * } + { " (" * bbl.editor * ")" * } + if$ + } + if$ +} + +FUNCTION {format.note} +{ + note empty$ + { "" } + { note #1 #1 substring$ + duplicate$ "{" = + 'skip$ + { output.state mid.sentence = + { "l" } + { "u" } + if$ + change.case$ + } + if$ + note #2 global.max$ substring$ * + } + if$ +} + +FUNCTION {format.title} +{ title empty$ + { "" } + { title "t" change.case$ + } + if$ +} + +FUNCTION {output.bibitem.original} +{ newline$ + "\bibitem{" write$ + cite$ write$ + "}" write$ + newline$ + "" + before.all 'output.state := +} + +FUNCTION {n.dashify} +{ + 't := + "" + { t empty$ not } + { t #1 #1 substring$ "-" = + { t #1 #2 substring$ "--" = not + { "--" * + t #2 global.max$ substring$ 't := + } + { { t #1 #1 substring$ "-" = } + { "-" * + t #2 global.max$ substring$ 't := + } + while$ + } + if$ + } + { t #1 #1 substring$ * + t #2 global.max$ substring$ 't := + } + if$ + } + while$ +} + +FUNCTION {word.in} +{ bbl.in + ":" * + " " * } + +FUNCTION {format.date} +{ year empty$ + { month empty$ + { "" } + { "there's a month but no year in " cite$ * warning$ + month + } + if$ + } + { month empty$ + 'year + { month " " * year * } + if$ + } + if$ + duplicate$ empty$ + 'skip$ + { + before.all 'output.state := + " (" swap$ * ")" * + } + if$ +} + +FUNCTION{format.year} +{ year duplicate$ empty$ + { "empty year in " cite$ * warning$ pop$ "" } + { "(" swap$ * ")" * } + if$ +} + +FUNCTION {format.btitle} +{ title +} + +FUNCTION {tie.or.space.connect} +{ duplicate$ text.length$ #3 < + { "~" } + { " " } + if$ + swap$ * * +} + +FUNCTION {either.or.check} +{ empty$ + 'pop$ + { "can't use both " swap$ * " fields in " * cite$ * warning$ } + if$ +} + +FUNCTION {format.bvolume} +{ volume empty$ + { "" } + { bbl.volume volume tie.or.space.connect + series empty$ + 'skip$ + { bbl.of space.word * series emphasize * } + if$ + "volume and number" number either.or.check + } + if$ +} + +FUNCTION {format.number.series} +{ volume empty$ + { number empty$ + { series field.or.null } + { output.state mid.sentence = + { bbl.number } + { bbl.number capitalize } + if$ + number tie.or.space.connect + series empty$ + { "there's a number but no series in " cite$ * warning$ } + { bbl.in space.word * series * } + if$ + } + if$ + } + { "" } + if$ +} + +FUNCTION {is.num} +{ chr.to.int$ + duplicate$ "0" chr.to.int$ < not + swap$ "9" chr.to.int$ > not and +} + +FUNCTION {extract.num} +{ duplicate$ 't := + "" 's := + { t empty$ not } + { t #1 #1 substring$ + t #2 global.max$ substring$ 't := + duplicate$ is.num + { s swap$ * 's := } + { pop$ "" 't := } + if$ + } + while$ + s empty$ + 'skip$ + { pop$ s } + if$ +} + +FUNCTION {convert.edition} +{ edition extract.num "l" change.case$ 's := + s "first" = s "1" = or + { bbl.first 't := } + { s "second" = s "2" = or + { bbl.second 't := } + { s "third" = s "3" = or + { bbl.third 't := } + { s "fourth" = s "4" = or + { bbl.fourth 't := } + { s "fifth" = s "5" = or + { bbl.fifth 't := } + { s #1 #1 substring$ is.num + { s eng.ord 't := } + { edition 't := } + if$ + } + if$ + } + if$ + } + if$ + } + if$ + } + if$ + t +} + +FUNCTION {format.edition} +{ edition empty$ + { "" } + { output.state mid.sentence = + { convert.edition "l" change.case$ " " * bbl.edition * } + { convert.edition "t" change.case$ " " * bbl.edition * } + if$ + } + if$ +} + +INTEGERS { multiresult } + +FUNCTION {multi.page.check} +{ 't := + #0 'multiresult := + { multiresult not + t empty$ not + and + } + { t #1 #1 substring$ + duplicate$ "-" = + swap$ duplicate$ "," = + swap$ "+" = + or or + { #1 'multiresult := } + { t #2 global.max$ substring$ 't := } + if$ + } + while$ + multiresult +} + +FUNCTION {format.pages} +{ pages empty$ + { "" } + { pages multi.page.check + { bbl.pages pages n.dashify tie.or.space.connect } + { bbl.page pages tie.or.space.connect } + if$ + } + if$ +} + +FUNCTION {format.journal.pages} +{ pages empty$ + 'skip$ + { duplicate$ empty$ + { pop$ format.pages } + { + " " * + format.year * " " * + pages n.dashify * + } + if$ + } + if$ +} + +FUNCTION {format.vol.num.pages} +{ + % volume field.or.null + " " + volume empty$ + { pop$ "" } + { volume * } + if$ + number empty$ + 'skip$ + { + "~(" number * ")" * * + volume empty$ + { "there's a number but no volume in " cite$ * warning$ } + 'skip$ + if$ + } + if$ +} + +FUNCTION {format.chapter.pages} +{ chapter empty$ + { "" } + { type empty$ + { bbl.chapter } + { type "l" change.case$ } + if$ + chapter tie.or.space.connect + } + if$ +} + +FUNCTION {format.in.ed.booktitle} +{ booktitle empty$ + { "" } + { editor empty$ + { word.in booktitle * } + { word.in format.in.editors * ", " * + booktitle * } + if$ + } + if$ +} + +FUNCTION {empty.misc.check} +{ author empty$ title empty$ howpublished empty$ + month empty$ year empty$ note empty$ + and and and and and + { "all relevant fields are empty in " cite$ * warning$ } + 'skip$ + if$ +} + +FUNCTION {format.thesis.type} +{ type empty$ + 'skip$ + { pop$ + type "t" change.case$ + } + if$ +} + +FUNCTION {format.tr.number} +{ type empty$ + { bbl.techrep } + 'type + if$ + number empty$ + { "t" change.case$ } + { number tie.or.space.connect } + if$ +} + +FUNCTION {format.article.crossref} +{ + key empty$ + { journal empty$ + { "need key or journal for " cite$ * " to crossref " * crossref * + warning$ + "" + } + { word.in journal emphasize * } + if$ + } + { word.in key * " " *} + if$ + " \cite{" * crossref * "}" * +} + +FUNCTION {format.crossref.editor} +{ editor #1 "{vv~}{ll}" format.name$ + editor num.names$ duplicate$ + #2 > + { pop$ + " " * bbl.etal * + } + { #2 < + 'skip$ + { editor #2 "{ff }{vv }{ll}{ jj}" format.name$ "others" = + { + " " * bbl.etal * + } + { bbl.and space.word * editor #2 "{vv~}{ll}" format.name$ + * } + if$ + } + if$ + } + if$ +} + +FUNCTION {format.book.crossref} +{ volume empty$ + { "empty volume in " cite$ * "'s crossref of " * crossref * warning$ + word.in + } + { bbl.volume volume tie.or.space.connect + bbl.of space.word * + } + if$ + editor empty$ + editor field.or.null author field.or.null = + or + { key empty$ + { series empty$ + { "need editor, key, or series for " cite$ * " to crossref " * + crossref * warning$ + "" * + } + { series emphasize * } + if$ + } + { key * } + if$ + } + { format.crossref.editor * } + if$ + " \cite{" * crossref * "}" * +} + +FUNCTION {format.incoll.inproc.crossref} +{ + editor empty$ + editor field.or.null author field.or.null = + or + { key empty$ + { booktitle empty$ + { "need editor, key, or booktitle for " cite$ * " to crossref " * + crossref * warning$ + "" + } + { word.in booktitle * } + if$ + } + { word.in key * " " *} + if$ + } + { word.in format.crossref.editor * " " *} + if$ + " \cite{" * crossref * "}" * +} + +FUNCTION {format.org.or.pub} +{ 't := + "" + year empty$ + { "empty year in " cite$ * warning$ } + 'skip$ + if$ + address empty$ t empty$ and + year empty$ and + 'skip$ + { + t empty$ + { address empty$ + 'skip$ + { address * } + if$ + } + { t * + address empty$ + 'skip$ + { ", " * address * } + if$ + } + if$ + year empty$ + 'skip$ + { t empty$ address empty$ and + 'skip$ + { ", " * } + if$ + year * + } + if$ + } + if$ +} + +FUNCTION {format.publisher.address} +{ publisher empty$ + { "empty publisher in " cite$ * warning$ + "" + } + { publisher } + if$ + format.org.or.pub +} + +FUNCTION {format.organization.address} +{ organization empty$ + { "" } + { organization } + if$ + format.org.or.pub +} + +FUNCTION {make.href.null} +{ + pop$ +} +FUNCTION {make.href.hypertex} +{ + "\special {html: }" * swap$ * + "\special {html:}" * +} +FUNCTION {make.href.hyperref} +{ + "\href {" swap$ * "} {\path{" * swap$ * "}}" * +} +FUNCTION {make.href} +{ hrefform #2 = + 'make.href.hyperref % hrefform = 2 + { hrefform #1 = + 'make.href.hypertex % hrefform = 1 + 'make.href.null % hrefform = 0 (or anything else) + if$ + } + if$ +} + +FUNCTION {format.url} +{ inlinelinks #1 = url empty$ or + { "" } + { hrefform #1 = + { % special case -- add HyperTeX specials + urlintro "\url{" url * "}" * url make.href.hypertex * } + { urlintro "\url{" * url * "}" * } + if$ + } + if$ +} + +FUNCTION {format.eprint} +{ eprint empty$ + { "" } + { eprintprefix eprint * eprinturl eprint * make.href } + if$ +} + +FUNCTION {format.doi} +{ doi empty$ + { "" } + { doiprefix doi * doiurl doi * make.href } + if$ +} + +FUNCTION {output.url} +{ url empty$ + 'skip$ + { new.block + format.url output + format.lastchecked output + } + if$ +} + +FUNCTION {output.web.refs} +{ + new.block + output.url + addeprints eprint empty$ not and + { format.eprint output.nonnull } + 'skip$ + if$ + adddoiresolver doi empty$ not and + { format.doi output.nonnull } + 'skip$ + if$ +} + +FUNCTION {output.bibitem} +{ outside.brackets 'bracket.state := + output.bibitem.original + inlinelinks url empty$ not and + { #1 'makeinlinelink := } + { #0 'makeinlinelink := } + if$ +} + +FUNCTION {fin.entry} +{ output.web.refs % urlbst + makeinlinelink % ooops, it appears we didn't have a title for inlinelink + { setup.inlinelink % add some artificial link text here, as a fallback + "[link]" output.nonnull } + 'skip$ + if$ + bracket.state close.brackets = % urlbst + { "]" * } + 'skip$ + if$ + fin.entry.original +} + +FUNCTION {webpage} +{ output.bibitem + author empty$ + { editor empty$ + 'skip$ % author and editor both optional + { format.editors output.nonnull } + if$ + } + { editor empty$ + { format.authors output.nonnull } + { "can't use both author and editor fields in " cite$ * warning$ } + if$ + } + if$ + new.block + title empty$ 'skip$ 'setup.inlinelink if$ + format.title "title" output.check + inbrackets "online" output + new.block + year empty$ + 'skip$ + { format.date "year" output.check } + if$ + % We don't need to output the URL details ('lastchecked' and 'url'), + % because fin.entry does that for us, using output.web.refs. The only + % reason we would want to put them here is if we were to decide that + % they should go in front of the rather miscellaneous information in 'note'. + new.block + note output + fin.entry +} + +FUNCTION {article} +{ output.bibitem + format.authors "author" output.check + title empty$ 'skip$ 'setup.inlinelink if$ % urlbst + format.title "title" output.check + crossref missing$ + { journal + "journal" output.check + % add.blank + before.all 'output.state := + format.vol.num.pages output + } + { format.article.crossref output.nonnull + format.pages output + } + if$ + format.journal.pages + format.note output + fin.entry + write.url +} + +FUNCTION {book} +{ output.bibitem + author empty$ + { format.editors "author and editor" output.check + } + { format.authors output.nonnull + crossref missing$ + { "author and editor" editor either.or.check } + 'skip$ + if$ + } + if$ + title empty$ 'skip$ 'setup.inlinelink if$ % urlbst + format.btitle "title" output.check + crossref missing$ + { format.edition output + format.bvolume output + format.number.series output + format.publisher.address output + } + { + format.book.crossref output.nonnull + } + if$ + format.note output + fin.entry + write.url +} + +FUNCTION {booklet} +{ output.bibitem + format.authors output + title empty$ 'skip$ 'setup.inlinelink if$ % urlbst + format.title "title" output.check + howpublished output + address output + format.note output + format.date output + fin.entry + write.url +} + +FUNCTION {inbook} +{ output.bibitem + author empty$ + { format.editors "author and editor" output.check + } + { format.authors output.nonnull + crossref missing$ + { "author and editor" editor either.or.check } + 'skip$ + if$ + } + if$ + title empty$ 'skip$ 'setup.inlinelink if$ % urlbst + format.btitle "title" output.check + crossref missing$ + { + format.edition output + format.bvolume output + format.number.series output + format.publisher.address output + format.chapter.pages "chapter and pages" output.check + } + { + format.chapter.pages "chapter and pages" output.check + format.book.crossref output.nonnull + } + if$ + format.pages "pages" output.check + format.note output + fin.entry + write.url +} + +FUNCTION {incollection} +{ output.bibitem + format.authors "author" output.check + title empty$ 'skip$ 'setup.inlinelink if$ % urlbst + format.title "title" output.check + crossref missing$ + { format.in.ed.booktitle "booktitle" output.check + format.edition output + format.bvolume output + format.number.series output + format.publisher.address output + format.chapter.pages output + } + { format.incoll.inproc.crossref output.nonnull + format.chapter.pages output + } + if$ + format.pages "pages" output.check + format.note output + fin.entry + write.url +} + +FUNCTION {inproceedings} +{ output.bibitem + format.authors "author" output.check + title empty$ 'skip$ 'setup.inlinelink if$ % urlbst + format.title "title" output.check + crossref missing$ + { format.in.ed.booktitle "booktitle" output.check + format.edition output + format.bvolume output + format.number.series output + publisher empty$ + { format.organization.address output } + { organization output + format.publisher.address output + } + if$ + } + { format.incoll.inproc.crossref output.nonnull + } + if$ + format.pages "pages" output.check + format.note output + fin.entry + write.url +} + +FUNCTION {conference} { inproceedings } + +FUNCTION {manual} +{ output.bibitem + author empty$ + { organization empty$ + 'skip$ + { organization output.nonnull + address output + } + if$ + } + { format.authors output.nonnull } + if$ + title empty$ 'skip$ 'setup.inlinelink if$ % urlbst + format.btitle "title" output.check + author empty$ + { organization empty$ + { + address output + } + 'skip$ + if$ + } + { + organization output + address output + } + if$ + format.edition output + format.note output + format.date output + fin.entry + write.url +} + +FUNCTION {mastersthesis} +{ output.bibitem + format.authors "author" output.check + title empty$ 'skip$ 'setup.inlinelink if$ % urlbst + format.title "title" output.check + bbl.mthesis format.thesis.type output.nonnull + school "school" output.check + address output + format.note output + format.date "year" output.check + fin.entry + write.url +} + +FUNCTION {misc} +{ output.bibitem + format.authors output + title empty$ 'skip$ 'setup.inlinelink if$ % urlbst + format.title output + howpublished output + format.note output + format.date output + fin.entry + write.url + empty.misc.check +} + +FUNCTION {phdthesis} +{ output.bibitem + format.authors "author" output.check + title empty$ 'skip$ 'setup.inlinelink if$ % urlbst + format.title "title" output.check + bbl.phdthesis format.thesis.type output.nonnull + school "school" output.check + address output + format.note output + format.date "year" output.check + fin.entry + write.url +} + +FUNCTION {proceedings} +{ output.bibitem + editor empty$ + { organization output } + { format.editors output.nonnull } + if$ + title empty$ 'skip$ 'setup.inlinelink if$ % urlbst + format.btitle "title" output.check + format.bvolume output + format.number.series output + editor empty$ + { publisher empty$ + 'skip$ + { + format.publisher.address output + } + if$ + } + { publisher empty$ + { + format.organization.address output } + { + organization output + format.publisher.address output + } + if$ + } + if$ + format.note output + fin.entry + write.url +} + +FUNCTION {techreport} +{ output.bibitem + format.authors "author" output.check + title empty$ 'skip$ 'setup.inlinelink if$ % urlbst + format.title "title" output.check + format.tr.number output.nonnull + institution "institution" output.check + address output + format.note output + format.date "year" output.check + fin.entry + write.url +} + +FUNCTION {unpublished} +{ output.bibitem + format.authors "author" output.check + title empty$ 'skip$ 'setup.inlinelink if$ % urlbst + format.title "title" output.check + format.note "note" output.check + format.date output + fin.entry + write.url +} + +FUNCTION {default.type} { misc } + +READ + +STRINGS { longest.label } + +INTEGERS { number.label longest.label.width } + +FUNCTION {initialize.longest.label} +{ "" 'longest.label := + #1 'number.label := + #0 'longest.label.width := +} + +FUNCTION {longest.label.pass} +{ number.label int.to.str$ 'label := + number.label #1 + 'number.label := + label width$ longest.label.width > + { label 'longest.label := + label width$ 'longest.label.width := + } + 'skip$ + if$ +} + +EXECUTE {initialize.longest.label} + +ITERATE {longest.label.pass} + +FUNCTION {begin.bib} +{ preamble$ empty$ + 'skip$ + { preamble$ write$ newline$ } + if$ + "\begin{thebibliography}{" longest.label * "}" * + write$ newline$ + "\expandafter\ifx\csname url\endcsname\relax" + write$ newline$ + " \def\url#1{\texttt{#1}}\fi" + write$ newline$ + "\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi" + write$ newline$ + "\expandafter\ifx\csname href\endcsname\relax" + write$ newline$ + " \def\href#1#2{#2} \def\path#1{#1}\fi" + write$ newline$ +} + +EXECUTE {begin.bib} + +EXECUTE {init.urlbst.variables} +EXECUTE {init.state.consts} + +ITERATE {call.type$} + +FUNCTION {end.bib} +{ newline$ + "\end{thebibliography}" write$ newline$ +} + +EXECUTE {end.bib} +%% End of customized bst file +%% +%% End of file `elsarticle-num.bst'. diff --git a/elsarticle.cls b/elsarticle.cls new file mode 100644 index 0000000..2596aa6 --- /dev/null +++ b/elsarticle.cls @@ -0,0 +1,774 @@ +%% +%% This is file `elsarticle.cls', +%% generated with the docstrip utility. +%% +%% The original source files were: +%% +%% elsarticle.dtx (with options: `class') +%% +%% Copyright 2007, 2008, 2009 Elsevier Ltd +%% +%% This file is part of the 'Elsarticle Bundle'. +%% ------------------------------------------- +%% +%% It may be distributed under the conditions of the LaTeX Project Public +%% License, either version 1.2 of this license or (at your option) any +%% later version. The latest version of this license is in +%% http://www.latex-project.org/lppl.txt +%% and version 1.2 or later is part of all distributions of LaTeX +%% version 1999/12/01 or later. +%% +%% The list of all files belonging to the 'Elsarticle Bundle' is +%% given in the file `manifest.txt'. +%% +%% +%% $Id: elsarticle.cls,v 1.20 2008-10-13 04:24:12 cvr Exp $ +%% + \def\RCSfile{elsarticle}% + \def\RCSversion{1.2.0}% + \def\RCSdate{2009/09/17}% + \def\@shortjnl{\relax} + \def\@journal{Elsevier Ltd} \def\@company{Elsevier Ltd} + \def\@issn{000-0000} + \def\@shortjid{elsarticle} +\NeedsTeXFormat{LaTeX2e}[1995/12/01] +\ProvidesClass{\@shortjid}[\RCSdate, \RCSversion: \@journal] +\def\ABD{\AtBeginDocument} +\newif\ifpreprint \preprintfalse +\newif\iflongmktitle \longmktitlefalse + +\def\@blstr{1} +\newdimen\@bls +\@bls=\baselineskip + +\def\@finalWarning{% + *****************************************************\MessageBreak + This document is typeset in the CRC style which\MessageBreak + is not suitable for submission.\MessageBreak + \MessageBreak + Please typeset again using 'preprint' option\MessageBreak + for creating PDF suitable for submission.\MessageBreak + ******************************************************\MessageBreak +} + +\DeclareOption{preprint}{\global\preprinttrue + \gdef\@blstr{1}\xdef\jtype{0}% + \AtBeginDocument{\@twosidefalse\@mparswitchfalse}} +\DeclareOption{final}{\gdef\@blstr{1}\global\preprintfalse} +\DeclareOption{review}{\global\preprinttrue\gdef\@blstr{1.5}} +\DeclareOption{authoryear}{\xdef\@biboptions{round,authoryear}} +\DeclareOption{number}{\xdef\@biboptions{numbers}} +\DeclareOption{numbers}{\xdef\@biboptions{numbers}} +\DeclareOption{longtitle}{\global\longmktitletrue} +\DeclareOption{5p}{\xdef\jtype{5}\global\preprintfalse + \ExecuteOptions{twocolumn}} + \def\jtype{0} +\DeclareOption{3p}{\xdef\jtype{3}\global\preprintfalse} +\DeclareOption{1p}{\xdef\jtype{1}\global\preprintfalse + \AtBeginDocument{\@twocolumnfalse}} +\DeclareOption{times}{\IfFileExists{txfonts.sty}% + {\AtEndOfClass{\RequirePackage{txfonts}% + \gdef\ttdefault{cmtt}% + \let\iint\relax + \let\iiint\relax + \let\iiiint\relax + \let\idotsint\relax + \let\openbox\relax}}{\RequirePackage{times}}} +\ExecuteOptions{a4paper,10pt,oneside,onecolumn,number,preprint} +\DeclareOption*{\PassOptionsToClass{\CurrentOption}{article}} +\ProcessOptions +\LoadClass{article} +\RequirePackage{graphicx} +\let\comma\@empty +\let\tnotesep\@empty +\def\title#1{\gdef\@title{#1}} +\let\@title\@empty + +\def\elsLabel#1{\@bsphack\protected@write\@auxout{}% + {\string\Newlabel{#1}{\@currentlabel}}\@esphack} +\def\Newlabel#1#2{\expandafter\xdef\csname X@#1\endcsname{#2}} + +\def\elsRef#1{\@ifundefined{X@#1}{0}{\csname X@#1\endcsname}% +} + +\def\tnotemark[#1]{\textsuperscript{\@for\@@tmark:=#1\do{% + \edef\tnotenum{\@ifundefined{X@\@@tmark}{1}{\elsRef{\@@tmark}}}% + \ifcase\tnotenum\or\ding{73}\or,\ding{73}\ding{73}\fi}}% +} +\let\@tnotemark\@empty + +\let\@tnotes\@empty +\RequirePackage{pifont} +\newcounter{tnote} +\def\tnotetext[#1]#2{\g@addto@macro\@tnotes{% + \refstepcounter{tnote}\elsLabel{#1}% + \def\thefootnote{\ifcase\c@tnote\or\ding{73}\or\ding{73}\ding{73}\fi}% + \footnotetext{#2}}} + +\let\@nonumnotes\@empty +\def\nonumnote#1{\g@addto@macro\@nonumnotes{% + \let\thefootnote\relax\footnotetext{#1}}} + +\newcounter{fnote} +\def\fnmark[#1]{\let\comma\@empty + \def\@fnmark{\@for\@@fnmark:=#1\do{% + \edef\fnotenum{\@ifundefined{X@\@@fnmark}{1}{\elsRef{\@@fnmark}}}% + \unskip\comma\fnotenum\let\comma,}}% +} + +\let\@fnotes\@empty\let\@fnmark\@empty +\def\fntext[#1]#2{\g@addto@macro\@fnotes{% + \refstepcounter{fnote}\elsLabel{#1}% + \def\thefootnote{\thefnote}% + \global\setcounter{footnote}{\thefnote}% + \footnotetext{#2}}} + +\def\cormark[#1]{\edef\cnotenum{\elsRef{#1}}% + \unskip\textsuperscript{\sep\ifcase\cnotenum\or + $\ast$\or$\ast\ast$\fi\hspace{-1pt}}\let\sep=,} + +\let\@cormark\@empty +\let\@cornotes\@empty +\newcounter{cnote} +\def\cortext[#1]#2{\g@addto@macro\@cornotes{% + \refstepcounter{cnote}\elsLabel{#1}% + \def\thefootnote{\ifcase\thecnote\or$\ast$\or + $\ast\ast$\fi}% + \footnotetext{#2}}} + +\let\@corref\@empty +\def\corref#1{\edef\cnotenum{\elsRef{#1}}% + \edef\@corref{\ifcase\cnotenum\or + $\ast$\or$\ast\ast$\fi\hskip-1pt}} + +\def\fnref#1{\fnmark[#1]} +\def\tnoteref#1{\tnotemark[#1]} + +\def\resetTitleCounters{\c@cnote=0 + \c@fnote=0 \c@tnote=0 \c@footnote=0} + +\let\eadsep\@empty +\let\@elseads\@empty +\let\@elsuads\@empty +\let\@cormark\@empty +\def\hashchar{\expandafter\@gobble\string\~} +\def\underscorechar{\expandafter\@gobble\string\_} +\def\lbracechar{\expandafter\@gobble\string\{} +\def\rbracechar{\expandafter\@gobble\string\}} + +\def\ead{\@ifnextchar[{\@uad}{\@ead}} +\gdef\@ead#1{\bgroup\def\_{\string\underscorechar\space}% + \def\{{\string\lbracechar\space}% + \def~{\hashchar\space}% + \def\}{\string\rbracechar\space}% + \edef\tmp{\the\@eadauthor} + \immediate\write\@auxout{\string\emailauthor + {#1}{\expandafter\strip@prefix\meaning\tmp}}% + \egroup +} +\newcounter{ead} +\gdef\emailauthor#1#2{\stepcounter{ead}% + \g@addto@macro\@elseads{\raggedright% + \let\corref\@gobble + \eadsep\texttt{#1} (#2)\def\eadsep{\unskip,\space}}% +} +\gdef\@uad[#1]#2{\bgroup + \def~{\string\hashchar\space}% + \def\_{\string\underscorechar\space}% + \edef\tmp{\the\@eadauthor} + \immediate\write\@auxout{\string\urlauthor + {#2}{\expandafter\strip@prefix\meaning\tmp}}% + \egroup +} +\def\urlauthor#1#2{\g@addto@macro\@elsuads{\let\corref\@gobble% + \raggedright\eadsep\texttt{#1}\space(#2)% + \def\eadsep{\unskip,\space}}% +} + +\def\elsauthors{} +\def\pprinttitle{} +\let\authorsep\@empty +\let\sep\@empty +\newcounter{author} +\def\author{\@ifnextchar[{\@@author}{\@author}} + +\newtoks\@eadauthor +\def\@@author[#1]#2{\g@addto@macro\elsauthors{% + \def\baselinestretch{1}% + \authorsep#2\unskip\textsuperscript{%#1% + \@for\@@affmark:=#1\do{% + \edef\affnum{\@ifundefined{X@\@@affmark}{1}{\elsRef{\@@affmark}}}% + \unskip\sep\affnum\let\sep=,}% + \ifx\@fnmark\@empty\else\unskip\sep\@fnmark\let\sep=,\fi + \ifx\@corref\@empty\else\unskip\sep\@corref\let\sep=,\fi + }% + \def\authorsep{\unskip,\space}% + \global\let\sep\@empty\global\let\@corref\@empty + \global\let\@fnmark\@empty}% + \@eadauthor={#2} +} + +\def\@author#1{\g@addto@macro\elsauthors{\normalsize% + \def\baselinestretch{1}% + \upshape\authorsep#1\unskip\textsuperscript{% + \ifx\@fnmark\@empty\else\unskip\sep\@fnmark\let\sep=,\fi + \ifx\@corref\@empty\else\unskip\sep\@corref\let\sep=,\fi + }% + \def\authorsep{\unskip,\space}% + \global\let\@fnmark\@empty + \global\let\sep\@empty}% + \@eadauthor={#1} +} + +\def\elsaddress{} +\def\addsep{\par\vskip6pt} +\def\address{\@ifnextchar[{\@@address}{\@address}} + +\def\@alph#1{% + \ifcase#1\or a\or b\or c\or d\or e\or f\or g\or h\or i\or j\or k\or + l\or m\or n\or o\or p\or q\or r\or s\or t\or u\or v\or w\or x\or + y\or z% + \or aa\or ab\or ac\or ad\or ae\or af\or ag\or ah\or ai\or aj\or + ak\or al\or am\or an\or ao\or ap\or aq\or ar\or as\or at\or au\or + av\or aw\or ax\or ay\or az% + \or ba\or bb\or bc\or bd\or be\or bf\or bg\or bh\or bi\or bj\or + bk\or bl\or bm\or bn\or bo\or bp\or bq\or br\or bs\or bt\or bu\or + bv\or bw\or bx\or by\or bz% + \or ca\or cb\or cc\or cd\or ce\or cf\or cg\or ch\or ci\or cj\or + ck\or cl\or cm\or cn\or co\or cp\or cq\or cr\or cs\or ct\or cu\or + cv\or cw\or cx\or cy\or cz% + \or da\or db\or dc\or dd\or de\or df\or dg\or dh\or di\or dj\or + dk\or dl\or dm\or dn\or do\or dp\or dq\or dr\or ds\or dt\or du\or + dv\or dw\or dx\or dy\or dz% + \or ea\or eb\or ec\or ed\or ee\or ef\or eg\or eh\or ei\or ej\or + ek\or el\or em\or en\or eo\or ep\or eq\or er\or es\or et\or eu\or + ev\or ew\or ex\or ey\or ez% + \or fa\or fb\or fc\or fd\or fe\or ff\or fg\or fh\or fi\or fj\or + fk\or fl\or fm\or fn\or fo\or fp\or fq\or fr\or fs\or ft\or fu\or + fv\or fw\or fx\or fy\or fz% + \or ga\or gb\or gc\or gd\or ge\or gf\or gg\or gh\or gi\or gj\or + gk\or gl\or gm\or gn\or go\or gp\or gq\or gr\or gs\or gt\or gu\or + gv\or gw\or gx\or gy\or gz% + \else\@ctrerr\fi} + +\newcounter{affn} +\renewcommand\theaffn{\alph{affn}} + +\long\def\@@address[#1]#2{\g@addto@macro\elsaddress{% + \def\baselinestretch{1}% + \refstepcounter{affn} + \xdef\@currentlabel{\theaffn} + \elsLabel{#1}% + \textsuperscript{\theaffn}#2\par}} + +\long\def\@address#1{\g@addto@macro\elsauthors{% + \def\baselinestretch{1}% + \addsep\footnotesize\itshape#1\def\addsep{\par\vskip6pt}% + \def\authorsep{\par\vskip8pt}}} + +\newbox\absbox +\renewenvironment{abstract}{\global\setbox\absbox=\vbox\bgroup + \hsize=\textwidth\def\baselinestretch{1}% + \noindent\unskip\textbf{Abstract} + \par\medskip\noindent\unskip\ignorespaces} + {\egroup} + +\newbox\keybox +\def\keyword{% + \def\sep{\unskip, }% + \def\MSC{\@ifnextchar[{\@MSC}{\@MSC[2000]}} + \def\@MSC[##1]{\par\leavevmode\hbox {\it ##1~MSC:\space}}% + \def\PACS{\par\leavevmode\hbox {\it PACS:\space}}% + \def\JEL{\par\leavevmode\hbox {\it JEL:\space}}% + \global\setbox\keybox=\vbox\bgroup\hsize=\textwidth + \normalsize\normalfont\def\baselinestretch{1} + \parskip\z@ + \noindent\textit{Keywords: } + \raggedright % Keywords are not justified. + \ignorespaces} +\def\endkeyword{\par \egroup} + +\newdimen\Columnwidth +\Columnwidth=\columnwidth + +\def\printFirstPageNotes{% + \iflongmktitle + \let\columnwidth=\textwidth\fi + \ifx\@tnotes\@empty\else\@tnotes\fi + \ifx\@nonumnotes\@empty\else\@nonumnotes\fi + \ifx\@cornotes\@empty\else\@cornotes\fi + \ifx\@elseads\@empty\relax\else + \let\thefootnote\relax + \footnotetext{\ifnum\theead=1\relax + \textit{Email address:\space}\else + \textit{Email addresses:\space}\fi + \@elseads}\fi + \ifx\@elsuads\@empty\relax\else + \let\thefootnote\relax + \footnotetext{\textit{URL:\space}% + \@elsuads}\fi + \ifx\@fnotes\@empty\else\@fnotes\fi + \iflongmktitle\if@twocolumn + \let\columnwidth=\Columnwidth\fi\fi +} + +\long\def\pprintMaketitle{\clearpage + \iflongmktitle\if@twocolumn\let\columnwidth=\textwidth\fi\fi + \resetTitleCounters + \def\baselinestretch{1}% + \printFirstPageNotes + \begin{center}% + \thispagestyle{pprintTitle}% + \def\baselinestretch{1}% + \Large\@title\par\vskip18pt + \normalsize\elsauthors\par\vskip10pt + \footnotesize\itshape\elsaddress\par\vskip36pt + \hrule\vskip12pt + \ifvoid\absbox\else\unvbox\absbox\par\vskip10pt\fi + \ifvoid\keybox\else\unvbox\keybox\par\vskip10pt\fi + \hrule\vskip12pt + \end{center}% + \gdef\thefootnote{\arabic{footnote}}% + } + +\def\printWarning{% + \mbox{}\par\vfill\par\bgroup + \fboxsep12pt\fboxrule1pt + \hspace*{.18\textwidth} + \fcolorbox{gray50}{gray10}{\box\warnbox} + \egroup\par\vfill\thispagestyle{empty} + \setcounter{page}{0} + \clearpage} + +\long\def\finalMaketitle{% + \resetTitleCounters + \def\baselinestretch{1}% + \MaketitleBox + \thispagestyle{pprintTitle}% + \gdef\thefootnote{\arabic{footnote}}% + } + +\long\def\MaketitleBox{% + \resetTitleCounters + \def\baselinestretch{1}% + \begin{center}% + \def\baselinestretch{1}% + \Large\@title\par\vskip18pt + \normalsize\elsauthors\par\vskip10pt + \footnotesize\itshape\elsaddress\par\vskip36pt + \hrule\vskip12pt + \ifvoid\absbox\else\unvbox\absbox\par\vskip10pt\fi + \ifvoid\keybox\else\unvbox\keybox\par\vskip10pt\fi + \hrule\vskip12pt + \end{center}% + } + +\def\FNtext#1{\par\bgroup\footnotesize#1\egroup} +\newdimen\space@left +\def\alarm#1{\typeout{******************************}% + \typeout{#1}% + \typeout{******************************}% +} +\long\def\getSpaceLeft{%\global\@twocolumnfalse% + \global\setbox0=\vbox{\hsize=\textwidth\MaketitleBox}% + \global\setbox1=\vbox{\hsize=\textwidth + \let\footnotetext\FNtext + \printFirstPageNotes}% + \xdef\noteheight{\the\ht1}% + \xdef\titleheight{\the\ht0}% + \@tempdima=\vsize + \advance\@tempdima-\noteheight + \advance\@tempdima-1\baselineskip +} + + \skip\footins=24pt + +\newbox\els@boxa +\newbox\els@boxb + +\ifpreprint + \def\maketitle{\pprintMaketitle} + \else + \ifnum\jtype=1 + \def\maketitle{% + \iflongmktitle\getSpaceLeft + \global\setbox\els@boxa=\vsplit0 to \@tempdima + \box\els@boxa\par\resetTitleCounters + \thispagestyle{pprintTitle}% + \printFirstPageNotes + \box0% + \else + \finalMaketitle\printFirstPageNotes + \fi + \gdef\thefootnote{\arabic{footnote}}}% + \else + \ifnum\jtype=5 + \def\maketitle{% + \iflongmktitle\getSpaceLeft + \global\setbox\els@boxa=\vsplit0 to \@tempdima + \box\els@boxa\par\resetTitleCounters + \thispagestyle{pprintTitle}% + \printFirstPageNotes + \twocolumn[\box0]%\printFirstPageNotes + \else + \twocolumn[\finalMaketitle]\printFirstPageNotes + \fi + \gdef\thefootnote{\arabic{footnote}}} + \else + \if@twocolumn + \def\maketitle{% + \iflongmktitle\getSpaceLeft + \global\setbox\els@boxa=\vsplit0 to \@tempdima + \box\els@boxa\par\resetTitleCounters + \thispagestyle{pprintTitle}% + \printFirstPageNotes + \twocolumn[\box0]% + \else + \twocolumn[\finalMaketitle]\printFirstPageNotes + \fi + \gdef\thefootnote{\arabic{footnote}}}% + \else + \def\maketitle{% + \iflongmktitle\getSpaceLeft + \global\setbox\els@boxa=\vsplit0 to \@tempdima + \box\els@boxa\par\resetTitleCounters + \thispagestyle{pprintTitle}% + \printFirstPageNotes + \box0% + \else + \finalMaketitle\printFirstPageNotes + \fi + \gdef\thefootnote{\arabic{footnote}}}% + \fi + \fi + \fi +\fi +\def\ps@pprintTitle{% + \let\@oddhead\@empty + \let\@evenhead\@empty + \def\@oddfoot{\footnotesize\itshape + Preprint submitted to \ifx\@journal\@empty Elsevier + \else\@journal\fi\hfill\today}% + \let\@evenfoot\@oddfoot} +\def\@seccntDot{.} +\def\@seccntformat#1{\csname the#1\endcsname\@seccntDot\hskip 0.5em} + +\renewcommand\section{\@startsection {section}{1}{\z@}% + {18\p@ \@plus 6\p@ \@minus 3\p@}% + {9\p@ \@plus 6\p@ \@minus 3\p@}% + {\normalsize\bfseries\boldmath}} +\renewcommand\subsection{\@startsection{subsection}{2}{\z@}% + {12\p@ \@plus 6\p@ \@minus 3\p@}% + {3\p@ \@plus 6\p@ \@minus 3\p@}% + {\normalfont\normalsize\itshape}} +\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}% + {12\p@ \@plus 6\p@ \@minus 3\p@}% + {\p@}% + {\normalfont\normalsize\itshape}} + +\def\paragraph{\secdef{\els@aparagraph}{\els@bparagraph}} +\def\els@aparagraph[#1]#2{\elsparagraph[#1]{#2.}} +\def\els@bparagraph#1{\elsparagraph*{#1.}} + +\newcommand\elsparagraph{\@startsection{paragraph}{4}{0\z@}% + {10\p@ \@plus 6\p@ \@minus 3\p@}% + {-6\p@}% + {\normalfont\itshape}} +\newdimen\leftMargin +\leftMargin=2em +\newtoks\@enLab %\newtoks\@enfont +\def\@enQmark{?} +\def\@enLabel#1#2{% + \edef\@enThe{\noexpand#1{\@enumctr}}% + \@enLab\expandafter{\the\@enLab\csname the\@enumctr\endcsname}% + \@enloop} +\def\@enSpace{\afterassignment\@enSp@ce\let\@tempa= } +\def\@enSp@ce{\@enLab\expandafter{\the\@enLab\space}\@enloop} +\def\@enGroup#1{\@enLab\expandafter{\the\@enLab{#1}}\@enloop} +\def\@enOther#1{\@enLab\expandafter{\the\@enLab#1}\@enloop} +\def\@enloop{\futurelet\@entemp\@enloop@} +\def\@enloop@{% + \ifx A\@entemp \def\@tempa{\@enLabel\Alph }\else + \ifx a\@entemp \def\@tempa{\@enLabel\alph }\else + \ifx i\@entemp \def\@tempa{\@enLabel\roman }\else + \ifx I\@entemp \def\@tempa{\@enLabel\Roman }\else + \ifx 1\@entemp \def\@tempa{\@enLabel\arabic}\else + \ifx \@sptoken\@entemp \let\@tempa\@enSpace \else + \ifx \bgroup\@entemp \let\@tempa\@enGroup \else + \ifx \@enum@\@entemp \let\@tempa\@gobble \else + \let\@tempa\@enOther + \fi\fi\fi\fi\fi\fi\fi\fi + \@tempa} +\newlength{\@sep} \newlength{\@@sep} +\setlength{\@sep}{.5\baselineskip plus.2\baselineskip + minus.2\baselineskip} +\setlength{\@@sep}{.1\baselineskip plus.01\baselineskip + minus.05\baselineskip} +\providecommand{\sfbc}{\rmfamily\upshape} +\providecommand{\sfn}{\rmfamily\upshape} +\def\@enfont{\ifnum \@enumdepth >1\let\@nxt\sfn \else\let\@nxt\sfbc \fi\@nxt} +\def\enumerate{% + \ifnum \@enumdepth >3 \@toodeep\else + \advance\@enumdepth \@ne + \edef\@enumctr{enum\romannumeral\the\@enumdepth}\fi + \@ifnextchar[{\@@enum@}{\@enum@}} +\def\@@enum@[#1]{% + \@enLab{}\let\@enThe\@enQmark + \@enloop#1\@enum@ + \ifx\@enThe\@enQmark\@warning{The counter will not be printed.% + ^^J\space\@spaces\@spaces\@spaces The label is: \the\@enLab}\fi + \expandafter\edef\csname label\@enumctr\endcsname{\the\@enLab}% + \expandafter\let\csname the\@enumctr\endcsname\@enThe + \csname c@\@enumctr\endcsname7 + \expandafter\settowidth + \csname leftmargin\romannumeral\@enumdepth\endcsname + {\the\@enLab\hskip\labelsep}% + \@enum@} +\def\@enum@{\list{{\@enfont\csname label\@enumctr\endcsname}}% + {\usecounter{\@enumctr}\def\makelabel##1{\hss\llap{##1}}% + \ifnum \@enumdepth>1\setlength{\topsep}{\@@sep}\else + \setlength{\topsep}{\@sep}\fi + \ifnum \@enumdepth>1\setlength{\itemsep}{0pt plus1pt minus1pt}% + \else \setlength{\itemsep}{\@@sep}\fi + %\setlength\leftmargin{\leftMargin}%%%{1.8em} + \setlength{\parsep}{0pt plus1pt minus1pt}% + \setlength{\parskip}{0pt plus1pt minus1pt} + }} + +\def\endenumerate{\par\ifnum \@enumdepth >1\addvspace{\@@sep}\else + \addvspace{\@sep}\fi \endlist} + +\def\sitem{\@noitemargtrue\@item[\@itemlabel *]} + +\def\itemize{\@ifnextchar[{\@Itemize}{\@Itemize[]}} + +\def\@Itemize[#1]{\def\next{#1}% + \ifnum \@itemdepth >\thr@@\@toodeep\else + \advance\@itemdepth\@ne + \ifx\next\@empty\else\expandafter\def\csname + labelitem\romannumeral\the\@itemdepth\endcsname{#1}\fi% + \edef\@itemitem{labelitem\romannumeral\the\@itemdepth}% + \expandafter\list\csname\@itemitem\endcsname + {\def\makelabel##1{\hss\llap{##1}}}% + \fi} +\def\newdefinition#1{% + \@ifnextchar[{\@odfn{#1}}{\@ndfn{#1}}}%] +\def\@ndfn#1#2{% + \@ifnextchar[{\@xndfn{#1}{#2}}{\@yndfn{#1}{#2}}} +\def\@xndfn#1#2[#3]{% + \expandafter\@ifdefinable\csname #1\endcsname + {\@definecounter{#1}\@newctr{#1}[#3]% + \expandafter\xdef\csname the#1\endcsname{% + \expandafter\noexpand\csname the#3\endcsname \@dfncountersep + \@dfncounter{#1}}% + \global\@namedef{#1}{\@dfn{#1}{#2}}% + \global\@namedef{end#1}{\@enddefinition}}} +\def\@yndfn#1#2{% + \expandafter\@ifdefinable\csname #1\endcsname + {\@definecounter{#1}% + \expandafter\xdef\csname the#1\endcsname{\@dfncounter{#1}}% + \global\@namedef{#1}{\@dfn{#1}{#2}}% + \global\@namedef{end#1}{\@enddefinition}}} +\def\@odfn#1[#2]#3{% + \@ifundefined{c@#2}{\@nocounterr{#2}}% + {\expandafter\@ifdefinable\csname #1\endcsname + {\global\@namedef{the#1}{\@nameuse{the#2}} + \global\@namedef{#1}{\@dfn{#2}{#3}}% + \global\@namedef{end#1}{\@enddefinition}}}} +\def\@dfn#1#2{% + \refstepcounter{#1}% + \@ifnextchar[{\@ydfn{#1}{#2}}{\@xdfn{#1}{#2}}} +\def\@xdfn#1#2{% + \@begindefinition{#2}{\csname the#1\endcsname}\ignorespaces} +\def\@ydfn#1#2[#3]{% + \@opargbegindefinition{#2}{\csname the#1\endcsname}{#3}\ignorespaces} +\def\@dfncounter#1{\noexpand\arabic{#1}} +\def\@dfncountersep{.} +\def\@begindefinition#1#2{\trivlist + \item[\hskip\labelsep{\bfseries #1\ #2.}]\upshape} +\def\@opargbegindefinition#1#2#3{\trivlist + \item[\hskip\labelsep{\bfseries #1\ #2\ (#3).}]\upshape} +\def\@enddefinition{\endtrivlist} + +\def\@begintheorem#1#2{\trivlist + \let\baselinestretch\@blstr + \item[\hskip \labelsep{\bfseries #1\ #2.}]\itshape} +\def\@opargbegintheorem#1#2#3{\trivlist + \let\baselinestretch\@blstr + \item[\hskip \labelsep{\bfseries #1\ #2\ (#3).}]\itshape} + +\def\newproof#1{% + \@ifnextchar[{\@oprf{#1}}{\@nprf{#1}}} +\def\@nprf#1#2{% + \@ifnextchar[{\@xnprf{#1}{#2}}{\@ynprf{#1}{#2}}} +\def\@xnprf#1#2[#3]{% + \expandafter\@ifdefinable\csname #1\endcsname + {\@definecounter{#1}\@newctr{#1}[#3]% + \expandafter\xdef\csname the#1\endcsname{% + \expandafter\noexpand\csname the#3\endcsname \@prfcountersep + \@prfcounter{#1}}% + \global\@namedef{#1}{\@prf{#1}{#2}}% + \global\@namedef{end#1}{\@endproof}}} +\def\@ynprf#1#2{% + \expandafter\@ifdefinable\csname #1\endcsname + {\@definecounter{#1}% + \expandafter\xdef\csname the#1\endcsname{\@prfcounter{#1}}% + \global\@namedef{#1}{\@prf{#1}{#2}}% + \global\@namedef{end#1}{\@endproof}}} +\def\@oprf#1[#2]#3{% + \@ifundefined{c@#2}{\@nocounterr{#2}}% + {\expandafter\@ifdefinable\csname #1\endcsname + {\global\@namedef{the#1}{\@nameuse{the#2}}% + \global\@namedef{#1}{\@prf{#2}{#3}}% + \global\@namedef{end#1}{\@endproof}}}} +\def\@prf#1#2{% + \refstepcounter{#1}% + \@ifnextchar[{\@yprf{#1}{#2}}{\@xprf{#1}{#2}}} +\def\@xprf#1#2{% + \@beginproof{#2}{\csname the#1\endcsname}\ignorespaces} +\def\@yprf#1#2[#3]{% + \@opargbeginproof{#2}{\csname the#1\endcsname}{#3}\ignorespaces} +\def\@prfcounter#1{\noexpand\arabic{#1}} +\def\@prfcountersep{.} +\def\@beginproof#1#2{\trivlist\let\baselinestretch\@blstr + \item[\hskip \labelsep{\scshape #1.}]\rmfamily} +\def\@opargbeginproof#1#2#3{\trivlist\let\baselinestretch\@blstr + \item[\hskip \labelsep{\scshape #1\ (#3).}]\rmfamily} +\def\@endproof{\endtrivlist} +\newcommand*{\qed}{\hbox{}\hfill$\Box$} + +\@ifundefined{@biboptions}{\xdef\@biboptions{numbers}}{} +\InputIfFileExists{\jobname.spl}{}{} +\RequirePackage[\@biboptions]{natbib} + +\newwrite\splwrite +\immediate\openout\splwrite=\jobname.spl +\def\biboptions#1{\def\next{#1}\immediate\write\splwrite{% + \string\g@addto@macro\string\@biboptions{% + ,\expandafter\strip@prefix\meaning\next}}} + +\let\baselinestretch=\@blstr + +\ifnum\jtype=1 + \RequirePackage{geometry} + \geometry{twoside, + paperwidth=210mm, + paperheight=297mm, + textheight=562pt, + textwidth=384pt, + centering, + headheight=50pt, + headsep=12pt, + footskip=12pt, + footnotesep=24pt plus 2pt minus 12pt, + } + \global\let\bibfont=\footnotesize + \global\bibsep=0pt + \if@twocolumn\global\@twocolumnfalse\fi +\else\ifnum\jtype=3 + \RequirePackage{geometry} + \geometry{twoside, + paperwidth=210mm, + paperheight=297mm, + textheight=622pt, + textwidth=468pt, + centering, + headheight=50pt, + headsep=12pt, + footskip=18pt, + footnotesep=24pt plus 2pt minus 12pt, + columnsep=2pc + } + \global\let\bibfont=\footnotesize + \global\bibsep=0pt + \if@twocolumn\input{fleqn.clo}\fi +\else\ifnum\jtype=5 + \RequirePackage{geometry} + \geometry{twoside, + paperwidth=210mm, + paperheight=297mm, + textheight=682pt, + textwidth=522pt, + centering, + headheight=50pt, + headsep=12pt, + footskip=18pt, + footnotesep=24pt plus 2pt minus 12pt, + columnsep=18pt + }% + \global\let\bibfont=\footnotesize + \global\bibsep=0pt + \input{fleqn.clo} + \global\@twocolumntrue +%% +%% End of option '5p' +%% +\fi\fi\fi +\def\journal#1{\gdef\@journal{#1}} + \let\@journal\@empty +\newenvironment{frontmatter}{}{\maketitle} + +\long\def\@makecaption#1#2{% + \vskip\abovecaptionskip\footnotesize + \sbox\@tempboxa{#1: #2}% + \ifdim \wd\@tempboxa >\hsize + #1: #2\par + \else + \global \@minipagefalse + \hb@xt@\hsize{\hfil\box\@tempboxa\hfil}% + \fi + \vskip\belowcaptionskip} + +\AtBeginDocument{\@ifpackageloaded{hyperref} + {\def\@linkcolor{blue} + \def\@anchorcolor{blue} + \def\@citecolor{blue} + \def\@filecolor{blue} + \def\@urlcolor{blue} + \def\@menucolor{blue} + \def\@pagecolor{blue} +\begingroup + \@makeother\`% + \@makeother\=% + \edef\x{% + \edef\noexpand\x{% + \endgroup + \noexpand\toks@{% + \catcode 96=\noexpand\the\catcode`\noexpand\`\relax + \catcode 61=\noexpand\the\catcode`\noexpand\=\relax + }% + }% + \noexpand\x + }% +\x +\@makeother\` +\@makeother\= +}{}} +%% +\renewcommand\appendix{\par + \setcounter{section}{0}% + \setcounter{subsection}{0}% + \setcounter{equation}{0} + \gdef\thefigure{\@Alph\c@section.\arabic{figure}}% + \gdef\thetable{\@Alph\c@section.\arabic{table}}% + \gdef\thesection{\appendixname\@Alph\c@section}% + \@addtoreset{equation}{section}% + \gdef\theequation{\@Alph\c@section.\arabic{equation}}% +} +\def\appendixname{Appendix } + +%% Added for work with amsrefs.sty + +\@ifpackageloaded{amsrefs}% + {} + {\let\bibsection\relax% + \AtBeginDocument{\def\cites@b#1#2,#3{% + \begingroup[% + \toks@{\InnerCite{#2}#1}% + \ifx\@empty#3\@xp\@gobble\fi + \cites@c#3% +}}} +%% +\endinput +%% +%% End of file `elsarticle.cls'. diff --git a/generating.tex b/generating.tex index 0837fda..377c811 100644 --- a/generating.tex +++ b/generating.tex @@ -3,9 +3,7 @@ It has been shown~\cite[Theorem 4]{bcgr11:ip} that if its iteration graph $\Gamma(f)$ is strongly connected, then the output of $\chi_{\textit{14Secrypt}}$ follows a law that tends to the uniform distribution -if and only if its Markov matrix is a doubly stochastic matrix. - - +if and only if its Markov matrix is a doubly stochastic one. In~\cite[Section 4]{DBLP:conf/secrypt/CouchotHGWB14}, we have presented a general scheme which generates function with strongly connected iteration graph $\Gamma(f)$ and @@ -19,7 +17,7 @@ is removed, an edge $(x,x)$ is added. For instance, the iteration graph $\Gamma(f^*)$ (given in Figure~\ref{fig:iteration:f*}) is the $3$-cube in which the Hamiltonian cycle -$000,100,101,001,011,111,110,010,000$ +$000,100,101,001,011,111,$ $110,010,000$ has been removed. \end{xpl} @@ -31,7 +29,7 @@ has the awaited property with regard to the connectivity. \begin{thrm} The iteration graph $\Gamma(f)$ issued from the ${\mathsf{N}}$-cube where an Hamiltonian -cycle is removed is strongly connected. +cycle is removed, is strongly connected. \end{thrm} Moreover, if all the transitions have the same probability ($\frac{1}{n}$), @@ -64,13 +62,13 @@ Thus, there exists $b$ such that there is an arc between any $x$ and $y$. 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 +Many approaches have been proposed as a way to build such codes, for instance the Reflected Binary Code. In this one and for a $\mathsf{N}$-length cycle, one of the bits is exactly switched $2^{\mathsf{N}-1}$ times whereas the others bits are modified at most $\left\lfloor \dfrac{2^{\mathsf{N-1}}}{\mathsf{N}-1} \right\rfloor$ times. It is clear that the function that is built from such a code would -not provide a uniform output. +not provide an uniform output. The next section presents how to build balanced Hamiltonian cycles in the $\mathsf{N}$-cube with the objective to embed them into the diff --git a/hamilton.tex b/hamilton.tex index 3c64cf6..32888bd 100644 --- a/hamilton.tex +++ b/hamilton.tex @@ -5,7 +5,7 @@ For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on balanced Gray codes. In the transition sequence of these codes, the number of transitions of each element must differ at most by 2. -This uniformity is a global property on the cycle, \textit{i.e.} +This uniformity is a global property on the cycle, \textit{i.e.}, a property that is established while traversing the whole cycle. On the opposite side, when the objective is to follow a subpart of the Gray code and to switch each element approximately the @@ -15,13 +15,13 @@ For instance, the locally balanced property is studied in~\cite{Bykov2016} and an algorithm that establishes locally balanced Gray codes is given. The current context is to provide a function -$f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing a Hamiltonian +$f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing an Hamiltonian cycle in the $\mathsf{N}$-cube. Such a function is going to be iterated -$b$ times to produce a pseudo random number, -\textit{i.e.} a vertex in the +$b$ times to produce a pseudorandom 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 provide an uniform output distribution. To reduce the number of iterations, it can be claimed that the provided Gray code should ideally possess both balanced and locally balanced properties. @@ -46,8 +46,8 @@ This work have been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96} 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 rigorous presentation of this one -have mainly allowed them to prove two properties. +algorithm. Their rigorous presentation of this one +has mainly allowed them to prove two properties. The former states that if $\mathsf{N}$ is a 2-power, a balanced Gray code is always totally balanced. The latter states that for every $\mathsf{N}$ there @@ -119,14 +119,13 @@ Its transition sequence is $S=3,1,3,2,3,1,3,2$ and its transition count function $\textit{TC}_3(1)= \textit{TC}_3(2)=2$ and $\textit{TC}_3(3)=4$. Such a Gray code is balanced. Let now -$L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011,$ $0001, 0101,$ -$0100, 1100, 1101, 1001, 1011, 1010, 1000$ -be a cyclic Gray code. Since $S=2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4$, $\textit{TC}_4$ is equal to 4 everywhere, this code +$L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011,$ $0001, 0101,0100,$ $1100, 1101, 1001, 1011, 1010, 1000$ +be a cyclic Gray code. Since $S=2,3,4,1,4,$ $3,2,3,1,4,1,3,2,1,2,4$, $\textit{TC}_4$ is equal to 4 everywhere, this code is thus totally balanced. On the contrary, for the standard $4$-bits Gray code -$L^{\textit{st}}=0000,0001,0011,0010,0110,0111,0101,0100,1100,$ -$1101,1111,1110,1010,1011,1001,1000$, +$L^{\textit{st}}=0000,0001,0011,$ +$0010,0110,0111,0101,0100,1100,1101,1111,1110,1010,1011,1001,1000$, we have $\textit{TC}_4(1)=8$ $\textit{TC}_4(2)=4$ $\textit{TC}_4(3)=\textit{TC}_4(4)=2$ and the code is neither balanced nor totally balanced. \end{xpl} @@ -147,13 +146,13 @@ for any $i$, $1 \le i \le \mathsf{N}$. 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.} +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 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$. Thus again the algorithm successively produces $U= 1,2,1$, $V = 3$, $W= 2, 1, 1,3$, and $W' = 1,2,1,3$. Finally, $S_3$ is $1,2,1,3,1,2,1,3$ which obviously verifies the theorem. - For the initial case where $\mathsf{N}=4$, \textit{i.e.} $\mathsf{N-2}=2$ + For the initial case where $\mathsf{N}=4$, \textit{i.e.}, $\mathsf{N-2}=2$ we successively have: $S_1=1,2,1,2$, $l=4$, $u_0,u_1,u_2 = \emptyset,\emptyset,\emptyset$, and $v=\emptyset$. Thus again the algorithm successively produces @@ -188,11 +187,11 @@ c_{\mathsf{N}} &= &\mathsf{N} - d_{\mathsf{N}} \] 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 +Let us first prove 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.} +the quotient and the remainder in the Euclidean division +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 @@ -202,7 +201,7 @@ 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}$ +be the occurrence 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. @@ -240,7 +239,7 @@ 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. +This latter constraint is obviously established if the system has a solution. We thus have the following system. @@ -299,7 +298,7 @@ a_{\mathsf{N}} - 2(a_{\mathsf{N}-2}+2) \\ 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$. +its derivative is strictly positive 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. @@ -321,7 +320,7 @@ for any $\mathsf{N} \ge 8$ and the proof is established. 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. +Notice that all such choices lead to an Hamiltonian path. diff --git a/intro.tex b/intro.tex index e55151c..83b0a5a 100644 --- a/intro.tex +++ b/intro.tex @@ -35,7 +35,7 @@ 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{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 @@ -71,12 +71,12 @@ a doubly stochastic Markov matrix. 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.}, +For instance, if this 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. +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. @@ -89,7 +89,7 @@ suite is evaluated. This article, which -is an extension of~\cite{DBLP:conf/secrypt/CouchotHGWB14} +is an extension of~\cite{DBLP:conf/secrypt/CouchotHGWB14}, is organized as follows. The next section is devoted to preliminaries, basic notations, and terminologies regarding Boolean map iterations. Then, in @@ -100,14 +100,13 @@ 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 +implements this scheme and proves that it always produces a solution. +This is the second major contribution. +Then, Section~\ref{sec:hypercube} defines the theoretical framework to study +the mixing-time, \textit{i.e.}, time until reaching an 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 +of elements. Experiments show that the bound is in practice largely much +lower. This is the third major contribution. 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 diff --git a/main.bbl b/main.bbl index 9cc3880..66a9167 100644 --- a/main.bbl +++ b/main.bbl @@ -1,147 +1,117 @@ -% Generated by IEEEtran.bst, version: 1.14 (2015/08/26) \begin{thebibliography}{10} -\providecommand{\url}[1]{#1} -\csname url@samestyle\endcsname -\providecommand{\newblock}{\relax} -\providecommand{\bibinfo}[2]{#2} -\providecommand{\BIBentrySTDinterwordspacing}{\spaceskip=0pt\relax} -\providecommand{\BIBentryALTinterwordstretchfactor}{4} -\providecommand{\BIBentryALTinterwordspacing}{\spaceskip=\fontdimen2\font plus -\BIBentryALTinterwordstretchfactor\fontdimen3\font minus - \fontdimen4\font\relax} -\providecommand{\BIBforeignlanguage}[2]{{% -\expandafter\ifx\csname l@#1\endcsname\relax -\typeout{** WARNING: IEEEtran.bst: No hyphenation pattern has been}% -\typeout{** loaded for the language `#1'. Using the pattern for}% -\typeout{** the default language instead.}% -\else -\language=\csname l@#1\endcsname -\fi -#2}} -\providecommand{\BIBdecl}{\relax} -\BIBdecl +\expandafter\ifx\csname url\endcsname\relax + \def\url#1{\texttt{#1}}\fi +\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi +\expandafter\ifx\csname href\endcsname\relax + \def\href#1#2{#2} \def\path#1{#1}\fi \bibitem{915396} -T.~Stojanovski, J.~Pihl, and L.~Kocarev, ``Chaos-based random number - generators. part ii: practical realization,'' \emph{Circuits and Systems I: - Fundamental Theory and Applications, IEEE Transactions on}, vol.~48, no.~3, - pp. 382--385, Mar 2001. +T.~Stojanovski, J.~Pihl, L.~Kocarev, Chaos-based random number generators. part + ii: practical realization, Circuits and Systems I: Fundamental Theory and + Applications, IEEE Transactions on 48~(3) (2001) 382--385. \bibitem{915385} -T.~Stojanovski and L.~Kocarev, ``Chaos-based random number generators-part i: - analysis [cryptography],'' \emph{Circuits and Systems I: Fundamental Theory - and Applications, IEEE Transactions on}, vol.~48, no.~3, pp. 281--288, Mar - 2001. +T.~Stojanovski, L.~Kocarev, Chaos-based random number generators-part i: + analysis [cryptography], Circuits and Systems I: Fundamental Theory and + Applications, IEEE Transactions on 48~(3) (2001) 281--288. \bibitem{5376454} -L.~Cao, L.~Min, and H.~Zang, ``A chaos-based pseudorandom number generator and - performance analysis,'' in \emph{Computational Intelligence and Security, - 2009. CIS '09. International Conference on}, vol.~1.\hskip 1em plus 0.5em - minus 0.4em\relax IEEE, Dec 2009, pp. 494--498. +L.~Cao, L.~Min, H.~Zang, A chaos-based pseudorandom number generator and + performance analysis, in: Computational Intelligence and Security, 2009. CIS + '09. International Conference on, Vol.~1, IEEE, 2009, pp. 494--498. \bibitem{Marsaglia1996} -G.~Marsaglia, ``Diehard: a battery of tests of randomness,'' - \emph{http://stat.fsu.edu/~geo/diehard.html}, 1996. +G.~Marsaglia, Diehard: a battery of tests of randomness, + http://stat.fsu.edu/~geo/diehard.html. \bibitem{Nist10} -E.~Barker and A.~Roginsky, ``Draft {N}{I}{S}{T} special publication 800-131 +E.~Barker, A.~Roginsky, Draft {N}{I}{S}{T} special publication 800-131 recommendation for the transitioning of cryptographic algorithms and key - sizes,'' 2010. + sizes (2010). \bibitem{LEcuyerS07} -\BIBentryALTinterwordspacing -P.~L'Ecuyer and R.~J. Simard, ``Test{U01}: {A} {C} library for empirical - testing of random number generators,'' \emph{ACM Trans. Math. Softw}, - vol.~33, no.~4, 2007. [Online]. Available: - \url{http://doi.acm.org/10.1145/1268776.1268777} -\BIBentrySTDinterwordspacing +P.~L'Ecuyer, R.~J. Simard, Test{U01}: {A} {C} library for empirical testing of + random number generators, ACM Trans. Math. Softw 33~(4). \bibitem{Devaney} -R.~L. Devaney, \emph{An Introduction to Chaotic Dynamical Systems}, - 2nd~ed.\hskip 1em plus 0.5em minus 0.4em\relax Redwood City, CA: - Addison-Wesley, 1989. +R.~L. Devaney, An Introduction to Chaotic Dynamical Systems, 2nd Edition, + Addison-Wesley, Redwood City, CA, 1989. \bibitem{guyeuxTaiwan10} -C.~Guyeux, Q.~Wang, and J.~Bahi, ``Improving random number generators by - chaotic iterations application in data hiding,'' in \emph{Computer - Application and System Modeling (ICCASM), 2010 International Conference on}, - vol.~13.\hskip 1em plus 0.5em minus 0.4em\relax IEEE, Oct 2010, pp. +C.~Guyeux, Q.~Wang, J.~Bahi, Improving random number generators by chaotic + iterations application in data hiding, in: Computer Application and System + Modeling (ICCASM), 2010 International Conference on, Vol.~13, IEEE, 2010, pp. V13--643--V13--647. \bibitem{bcgr11:ip} -\BIBentryALTinterwordspacing -J.~Bahi, J.-F. Couchot, C.~Guyeux, and A.~Richard, ``On the link between - strongly connected iteration graphs and chaotic boolean discrete-time - dynamical systems,'' in \emph{FCT'11, 18th Int. Symp. on Fundamentals of - Computation Theory}, ser. LNCS, vol. 6914, Oslo, Norway, Aug. 2011, pp. - 126--137. [Online]. Available: - \url{http://dx.doi.org/10.1007/978-3-642-22953-4_11} -\BIBentrySTDinterwordspacing +J.~Bahi, J.-F. Couchot, C.~Guyeux, A.~Richard, On the link between strongly + connected iteration graphs and chaotic boolean discrete-time dynamical + systems, in: FCT'11, 18th Int. Symp. on Fundamentals of Computation Theory, + Vol. 6914 of LNCS, Oslo, Norway, 2011, pp. 126--137. \bibitem{wbg10ip} -\BIBentryALTinterwordspacing -Q.~Wang, J.~Bahi, C.~Guyeux, and X.~Fang, ``Randomness quality of {CI} chaotic - generators. application to internet security,'' in \emph{INTERNET'2010. The - 2nd Int. Conf. on Evolving Internet}.\hskip 1em plus 0.5em minus 0.4em\relax - Valencia, Spain: IEEE Computer Society Press, Sep. 2010, pp. 125--130, best - Paper award. [Online]. Available: - \url{http://doi.ieeecomputersociety.org/10.1109/INTERNET.2010.30} -\BIBentrySTDinterwordspacing +Q.~Wang, J.~Bahi, C.~Guyeux, X.~Fang, Randomness quality of {CI} chaotic + generators. application to internet security, in: INTERNET'2010. The 2nd Int. + Conf. on Evolving Internet, IEEE Computer Society Press, Valencia, Spain, + 2010, pp. 125--130, best Paper award. \bibitem{DBLP:conf/secrypt/CouchotHGWB14} -J.~Couchot, P.~H{\'{e}}am, C.~Guyeux, Q.~Wang, and J.~M. Bahi, ``Pseudorandom - number generators with balanced gray codes,'' in \emph{{SECRYPT} 2014 - - Proceedings of the 11th International Conference on Security and - Cryptography, Vienna, Austria, 28-30 August, 2014}, M.~S. Obaidat, - A.~Holzinger, and P.~Samarati, Eds.\hskip 1em plus 0.5em minus 0.4em\relax +J.~Couchot, P.~H{\'{e}}am, C.~Guyeux, Q.~Wang, J.~M. Bahi, Pseudorandom number + generators with balanced gray codes, in: M.~S. Obaidat, A.~Holzinger, + P.~Samarati (Eds.), {SECRYPT} 2014 - Proceedings of the 11th International + Conference on Security and Cryptography, Vienna, Austria, 28-30 August, 2014, SciTePress, 2014, pp. 469--475. \bibitem{Banks92} -J.~Banks, J.~Brooks, G.~Cairns, and P.~Stacey, ``On {D}evaney's definition of - chaos,'' \emph{Amer. Math. Monthly}, vol.~99, pp. 332--334, 1992. +J.~Banks, J.~Brooks, G.~Cairns, P.~Stacey, On {D}evaney's definition of chaos, + Amer. Math. Monthly 99 (1992) 332--334. + +\bibitem{wbg10:ip} +Q.~Wang, J.~Bahi, C.~Guyeux, X.~Fang, Randomness quality of {CI} chaotic + generators. application to internet security, in: INTERNET'2010. The 2nd Int. + Conf. on Evolving Internet, IEEE Computer Society Press, Valencia, Spain, + 2010, pp. 125--130, best Paper award. + +\bibitem{bfgw11:ip} +J.~Bahi, X.~Fang, C.~Guyeux, Q.~Wang, On the design of a family of {CI} + pseudo-random number generators, in: WICOM'11, 7th Int. IEEE Conf. on + Wireless Communications, Networking and Mobile Computing, Wuhan, China, 2011, + pp. 1--4. \bibitem{Robinson:1981:CS} -\BIBentryALTinterwordspacing -J.~P. Robinson and M.~Cohn, ``Counting sequences,'' \emph{IEEE Trans. Comput.}, - vol.~30, no.~1, pp. 17--23, Jan. 1981. [Online]. Available: - \url{http://dl.acm.org/citation.cfm?id=1963620.1963622} -\BIBentrySTDinterwordspacing +J.~P. Robinson, M.~Cohn, + \href{http://dl.acm.org/citation.cfm?id=1963620.1963622}{Counting sequences}, + IEEE Trans. Comput. 30~(1) (1981) 17--23. +\newline\urlprefix\url{http://dl.acm.org/citation.cfm?id=1963620.1963622} \bibitem{DBLP:journals/combinatorics/BhatS96} -\BIBentryALTinterwordspacing -G.~S. Bhat and C.~D. Savage, ``Balanced gray codes,'' \emph{Electr. J. Comb.}, - vol.~3, no.~1, 1996. [Online]. Available: - \url{http://www.combinatorics.org/Volume_3/Abstracts/v3i1r25.html} -\BIBentrySTDinterwordspacing +G.~S. Bhat, C.~D. Savage, + \href{http://www.combinatorics.org/Volume_3/Abstracts/v3i1r25.html}{Balanced + gray codes}, Electr. J. Comb. 3~(1). +\newline\urlprefix\url{http://www.combinatorics.org/Volume_3/Abstracts/v3i1r25.html} \bibitem{ZanSup04} -I.~Suparta and A.~v. Zanten, ``Totally balanced and exponentially balanced gray - codes,'' \emph{Discrete Analysis and Operation Research (Russia)}, vol.~11, - no.~4, pp. 81--98, 2004. +I.~Suparta, A.~v. Zanten, Totally balanced and exponentially balanced gray + codes, Discrete Analysis and Operation Research (Russia) 11~(4) (2004) + 81--98. \bibitem{Bykov2016} -\BIBentryALTinterwordspacing -I.~S. Bykov, ``On locally balanced gray codes,'' \emph{Journal of Applied and - Industrial Mathematics}, vol.~10, no.~1, pp. 78--85, 2016. [Online]. - Available: \url{http://dx.doi.org/10.1134/S1990478916010099} -\BIBentrySTDinterwordspacing +I.~S. Bykov, On locally balanced gray codes, Journal of Applied and Industrial + Mathematics 10~(1) (2016) 78--85. \bibitem{LevinPeresWilmer2006} -\BIBentryALTinterwordspacing -D.~A. Levin, Y.~Peres, and E.~L. Wilmer, \emph{{Markov chains and mixing - times}}.\hskip 1em plus 0.5em minus 0.4em\relax American Mathematical - Society, 2006. [Online]. Available: - \url{http://scholar.google.com/scholar.bib?q=info:3wf9IU94tyMJ:scholar.google.com/&output=citation&hl=en&as_sdt=2000&ct=citation&cd=0} -\BIBentrySTDinterwordspacing +D.~A. Levin, Y.~Peres, E.~L. Wilmer, + \href{http://scholar.google.com/scholar.bib?q=info:3wf9IU94tyMJ:scholar.google.com/&output=citation&hl=en&as_sdt=2000&ct=citation&cd=0}{{Markov + chains and mixing times}}, American Mathematical Society, 2006. +\newline\urlprefix\url{http://scholar.google.com/scholar.bib?q=info:3wf9IU94tyMJ:scholar.google.com/&output=citation&hl=en&as_sdt=2000&ct=citation&cd=0} \bibitem{proba} -M.~Mitzenmacher and E.~Upfal, \emph{Probability and Computing}.\hskip 1em plus - 0.5em minus 0.4em\relax Cambridge University Press, 2005. +M.~Mitzenmacher, E.~Upfal, Probability and Computing, Cambridge University + Press, 2005. \bibitem{matsumoto1998mersenne} -M.~Matsumoto and T.~Nishimura, ``Mersenne twister: a 623-dimensionally - equidistributed uniform pseudo-random number generator,'' \emph{ACM - Transactions on Modeling and Computer Simulation (TOMACS)}, vol.~8, no.~1, - pp. 3--30, 1998. +M.~Matsumoto, T.~Nishimura, Mersenne twister: a 623-dimensionally + equidistributed uniform pseudo-random number generator, ACM Transactions on + Modeling and Computer Simulation (TOMACS) 8~(1) (1998) 3--30. \end{thebibliography} diff --git a/main.pdf b/main.pdf index d8fbf55..6a0c48c 100644 Binary files a/main.pdf and b/main.pdf differ diff --git a/main.tex b/main.tex index 0460847..d8445bf 100644 --- a/main.tex +++ b/main.tex @@ -1,61 +1,5 @@ -%% bare_jrnl.tex -%% V1.4b -%% 2015/08/26 -%% by Michael Shell -%% see http://www.michaelshell.org/ -%% for current contact information. -%% -%% This is a skeleton file demonstrating the use of IEEEtran.cls -%% (requires IEEEtran.cls version 1.8b or later) with an IEEE -%% journal paper. -%% -%% Support sites: -%% http://www.michaelshell.org/tex/ieeetran/ -%% http://www.ctan.org/pkg/ieeetran -%% and -%% http://www.ieee.org/ - -%%************************************************************************* -%% Legal Notice: -%% This code is offered as-is without any warranty either expressed or -%% implied; without even the implied warranty of MERCHANTABILITY or -%% FITNESS FOR A PARTICULAR PURPOSE! -%% User assumes all risk. -%% In no event shall the IEEE or any contributor to this code be liable for -%% any damages or losses, including, but not limited to, incidental, -%% consequential, or any other damages, resulting from the use or misuse -%% of any information contained here. -%% -%% All comments are the opinions of their respective authors and are not -%% necessarily endorsed by the IEEE. -%% -%% This work is distributed under the LaTeX Project Public License (LPPL) -%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used, -%% distributed and modified. A copy of the LPPL, version 1.3, is included -%% in the base LaTeX documentation of all distributions of LaTeX released -%% 2003/12/01 or later. -%% Retain all contribution notices and credits. -%% ** Modified files should be clearly indicated as such, including ** -%% ** renaming them and changing author support contact information. ** -%%************************************************************************* - - -% *** Authors should verify (and, if needed, correct) their LaTeX system *** -% *** with the testflow diagnostic prior to trusting their LaTeX platform *** -% *** with production work. The IEEE's font choices and paper sizes can *** -% *** trigger bugs that do not appear when using other class files. *** *** -% The testflow support page is at: -% http://www.michaelshell.org/tex/testflow/ - - - -\documentclass[journal]{IEEEtran} -% -% If IEEEtran.cls has not been installed into the LaTeX system files, -% manually specify the path to it like: -% \documentclass[journal]{../sty/IEEEtran} - +\documentclass[preprint,review,12pt]{elsarticle} \usepackage{graphicx} \usepackage{caption} @@ -196,246 +140,6 @@ -% *** GRAPHICS RELATED PACKAGES *** -% -\ifCLASSINFOpdf - % \usepackage[pdftex]{graphicx} - % declare the path(s) where your graphic files are - % \graphicspath{{../pdf/}{../jpeg/}} - % and their extensions so you won't have to specify these with - % every instance of \includegraphics - % \DeclareGraphicsExtensions{.pdf,.jpeg,.png} -\else - % or other class option (dvipsone, dvipdf, if not using dvips). graphicx - % will default to the driver specified in the system graphics.cfg if no - % driver is specified. - % \usepackage[dvips]{graphicx} - % declare the path(s) where your graphic files are - % \graphicspath{{../eps/}} - % and their extensions so you won't have to specify these with - % every instance of \includegraphics - % \DeclareGraphicsExtensions{.eps} -\fi -% graphicx was written by David Carlisle and Sebastian Rahtz. It is -% required if you want graphics, photos, etc. graphicx.sty is already -% installed on most LaTeX systems. The latest version and documentation -% can be obtained at: -% http://www.ctan.org/pkg/graphicx -% Another good source of documentation is "Using Imported Graphics in -% LaTeX2e" by Keith Reckdahl which can be found at: -% http://www.ctan.org/pkg/epslatex -% -% latex, and pdflatex in dvi mode, support graphics in encapsulated -% postscript (.eps) format. pdflatex in pdf mode supports graphics -% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure -% that all non-photo figures use a vector format (.eps, .pdf, .mps) and -% not a bitmapped formats (.jpeg, .png). The IEEE frowns on bitmapped formats -% which can result in "jaggedy"/blurry rendering of lines and letters as -% well as large increases in file sizes. -% -% You can find documentation about the pdfTeX application at: -% http://www.tug.org/applications/pdftex - - - - - -% *** MATH PACKAGES *** -% -%\usepackage{amsmath} -% A popular package from the American Mathematical Society that provides -% many useful and powerful commands for dealing with mathematics. -% -% Note that the amsmath package sets \interdisplaylinepenalty to 10000 -% thus preventing page breaks from occurring within multiline equations. Use: -%\interdisplaylinepenalty=2500 -% after loading amsmath to restore such page breaks as IEEEtran.cls normally -% does. amsmath.sty is already installed on most LaTeX systems. The latest -% version and documentation can be obtained at: -% http://www.ctan.org/pkg/amsmath - - - - - -% *** SPECIALIZED LIST PACKAGES *** -% -%\usepackage{algorithmic} -% algorithmic.sty was written by Peter Williams and Rogerio Brito. -% This package provides an algorithmic environment fo describing algorithms. -% You can use the algorithmic environment in-text or within a figure -% environment to provide for a floating algorithm. Do NOT use the algorithm -% floating environment provided by algorithm.sty (by the same authors) or -% algorithm2e.sty (by Christophe Fiorio) as the IEEE does not use dedicated -% algorithm float types and packages that provide these will not provide -% correct IEEE style captions. The latest version and documentation of -% algorithmic.sty can be obtained at: -% http://www.ctan.org/pkg/algorithms -% Also of interest may be the (relatively newer and more customizable) -% algorithmicx.sty package by Szasz Janos: -% http://www.ctan.org/pkg/algorithmicx - - - - -% *** ALIGNMENT PACKAGES *** -% -%\usepackage{array} -% Frank Mittelbach's and David Carlisle's array.sty patches and improves -% the standard LaTeX2e array and tabular environments to provide better -% appearance and additional user controls. As the default LaTeX2e table -% generation code is lacking to the point of almost being broken with -% respect to the quality of the end results, all users are strongly -% advised to use an enhanced (at the very least that provided by array.sty) -% set of table tools. array.sty is already installed on most systems. The -% latest version and documentation can be obtained at: -% http://www.ctan.org/pkg/array - - -% IEEEtran contains the IEEEeqnarray family of commands that can be used to -% generate multiline equations as well as matrices, tables, etc., of high -% quality. - - - - -% *** SUBFIGURE PACKAGES *** -%\ifCLASSOPTIONcompsoc -% \usepackage[caption=false,font=normalsize,labelfont=sf,textfont=sf]{subfig} -%\else -% \usepackage[caption=false,font=footnotesize]{subfig} -%\fi -% subfig.sty, written by Steven Douglas Cochran, is the modern replacement -% for subfigure.sty, the latter of which is no longer maintained and is -% incompatible with some LaTeX packages including fixltx2e. However, -% subfig.sty requires and automatically loads Axel Sommerfeldt's caption.sty -% which will override IEEEtran.cls' handling of captions and this will result -% in non-IEEE style figure/table captions. To prevent this problem, be sure -% and invoke subfig.sty's "caption=false" package option (available since -% subfig.sty version 1.3, 2005/06/28) as this is will preserve IEEEtran.cls -% handling of captions. -% Note that the Computer Society format requires a larger sans serif font -% than the serif footnote size font used in traditional IEEE formatting -% and thus the need to invoke different subfig.sty package options depending -% on whether compsoc mode has been enabled. -% -% The latest version and documentation of subfig.sty can be obtained at: -% http://www.ctan.org/pkg/subfig - - - - -% *** FLOAT PACKAGES *** -% -%\usepackage{fixltx2e} -% fixltx2e, the successor to the earlier fix2col.sty, was written by -% Frank Mittelbach and David Carlisle. This package corrects a few problems -% in the LaTeX2e kernel, the most notable of which is that in current -% LaTeX2e releases, the ordering of single and double column floats is not -% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a -% single column figure to be placed prior to an earlier double column -% figure. -% Be aware that LaTeX2e kernels dated 2015 and later have fixltx2e.sty's -% corrections already built into the system in which case a warning will -% be issued if an attempt is made to load fixltx2e.sty as it is no longer -% needed. -% The latest version and documentation can be found at: -% http://www.ctan.org/pkg/fixltx2e - - -%\usepackage{stfloats} -% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e -% the ability to do double column floats at the bottom of the page as well -% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in -% LaTeX2e). It also provides a command: -%\fnbelowfloat -% to enable the placement of footnotes below bottom floats (the standard -% LaTeX2e kernel puts them above bottom floats). This is an invasive package -% which rewrites many portions of the LaTeX2e float routines. It may not work -% with other packages that modify the LaTeX2e float routines. The latest -% version and documentation can be obtained at: -% http://www.ctan.org/pkg/stfloats -% Do not use the stfloats baselinefloat ability as the IEEE does not allow -% \baselineskip to stretch. Authors submitting work to the IEEE should note -% that the IEEE rarely uses double column equations and that authors should try -% to avoid such use. Do not be tempted to use the cuted.sty or midfloat.sty -% packages (also by Sigitas Tolusis) as the IEEE does not format its papers in -% such ways. -% Do not attempt to use stfloats with fixltx2e as they are incompatible. -% Instead, use Morten Hogholm'a dblfloatfix which combines the features -% of both fixltx2e and stfloats: -% -% \usepackage{dblfloatfix} -% The latest version can be found at: -% http://www.ctan.org/pkg/dblfloatfix - - - - -%\ifCLASSOPTIONcaptionsoff -% \usepackage[nomarkers]{endfloat} -% \let\MYoriglatexcaption\caption -% \renewcommand{\caption}[2][\relax]{\MYoriglatexcaption[#2]{#2}} -%\fi -% endfloat.sty was written by James Darrell McCauley, Jeff Goldberg and -% Axel Sommerfeldt. This package may be useful when used in conjunction with -% IEEEtran.cls' captionsoff option. Some IEEE journals/societies require that -% submissions have lists of figures/tables at the end of the paper and that -% figures/tables without any captions are placed on a page by themselves at -% the end of the document. If needed, the draftcls IEEEtran class option or -% \CLASSINPUTbaselinestretch interface can be used to increase the line -% spacing as well. Be sure and use the nomarkers option of endfloat to -% prevent endfloat from "marking" where the figures would have been placed -% in the text. The two hack lines of code above are a slight modification of -% that suggested by in the endfloat docs (section 8.4.1) to ensure that -% the full captions always appear in the list of figures/tables - even if -% the user used the short optional argument of \caption[]{}. -% IEEE papers do not typically make use of \caption[]'s optional argument, -% so this should not be an issue. A similar trick can be used to disable -% captions of packages such as subfig.sty that lack options to turn off -% the subcaptions: -% For subfig.sty: -% \let\MYorigsubfloat\subfloat -% \renewcommand{\subfloat}[2][\relax]{\MYorigsubfloat[]{#2}} -% However, the above trick will not work if both optional arguments of -% the \subfloat command are used. Furthermore, there needs to be a -% description of each subfigure *somewhere* and endfloat does not add -% subfigure captions to its list of figures. Thus, the best approach is to -% avoid the use of subfigure captions (many IEEE journals avoid them anyway) -% and instead reference/explain all the subfigures within the main caption. -% The latest version of endfloat.sty and its documentation can obtained at: -% http://www.ctan.org/pkg/endfloat -% -% The IEEEtran \ifCLASSOPTIONcaptionsoff conditional can also be used -% later in the document, say, to conditionally put the References on a -% page by themselves. - - - - -% *** PDF, URL AND HYPERLINK PACKAGES *** -% -%\usepackage{url} -% url.sty was written by Donald Arseneau. It provides better support for -% handling and breaking URLs. url.sty is already installed on most LaTeX -% systems. The latest version and documentation can be obtained at: -% http://www.ctan.org/pkg/url -% Basically, \url{my_url_here}. - - - - -% *** Do not adjust lengths that control margins, column widths, etc. *** -% *** Do not use packages that alter fonts (such as pslatex). *** -% There should be no need to do such things with IEEEtran.cls V1.6 and later. -% (Unless specifically asked to do so by the journal or conference you plan -% to submit to, of course. ) - - -% correct bad hyphenation here -\hyphenation{op-tical net-works semi-conduc-tor} - - \begin{document} % % paper title @@ -458,9 +162,12 @@ % a separate \thanks must be used for each paragraph as LaTeX2e's \thanks % was not built to handle multiple paragraphs % -\author{Sylvain Contassot-Vivier, Jean-François Couchot, Christophe Guyeux, Pierre-Cyrille Heam -\thanks{LORIA, Université de Lorraine, Nancy, France} -\thanks{FEMTO-ST Institute, University of Franche-Comté, Belfort, France}} +\author[label1]{Sylvain Contassot-Vivier} +\author[label2]{Jean-François Couchot} +\author[label2]{Christophe Guyeux} +\author[label2]{Pierre-Cyrille Heam} +\address[label1]{LORIA, Université de Lorraine, Nancy, France} +\address[label2]{FEMTO-ST Institute, University of Franche-Comté, Belfort, France} @@ -493,9 +200,6 @@ -% The paper headers -\markboth{Journal of \LaTeX\ Class Files,~Vol.~14, No.~8, August~2015}% -{Shell \MakeLowercase{\textit{et al.}}: Bare Demo of IEEEtran.cls for IEEE Journals} % The only time the second header will appear is for the odd numbered pages % after the title page when using the twoside option. % @@ -522,7 +226,7 @@ % make the title area -\maketitle +%\maketitle % As a general rule, do not put math, special symbols or citations % in the abstract or keywords. @@ -539,9 +243,8 @@ % \end{abstract} \begin{abstract} - Designing a pseudorandom number generator (PRNG) is a hard and complex task. -Many recent works have consider chaotic functions as the basis of built +Many recent works have considered chaotic functions as the basis of built PRNGs: the quality of the output would be an obvious consequence of some chaos properties. @@ -549,10 +252,10 @@ However, there is no direct reasoning that goes from chaotic functions to uniform distribution of the output. Moreover, it is not clear that embedding such kind of functions into a PRNG allows to get a chaotic output, which could be required for simulating -some chaotic behaviours. +some chaotic behaviors. In a previous work, some of the authors have proposed the idea of walking -into a $\mathsf{N}$-cube where a balanced Hamiltonian cycle have been +into a $\mathsf{N}$-cube where a balanced Hamiltonian cycle has been removed as the basis of a chaotic PRNG. In this article, all the difficult issues observed in the previous work have been tackled. The chaotic behavior of the whole PRNG is proven. The construction of the balanced Hamiltonian @@ -560,8 +263,6 @@ cycle is theoretically and practically solved. An upper bound of the expected length of the walk to obtain a uniform distribution is calculated. Finally practical experiments show that the generators successfully pass the classical statistical tests. - - \end{abstract} @@ -585,7 +286,7 @@ classical statistical tests. % % For peerreview papers, this IEEEtran command inserts a page break and % creates the second title. It will be ignored for other modes. -\IEEEpeerreviewmaketitle +\maketitle \section{Introduction} @@ -617,7 +318,15 @@ classical statistical tests. %\acknowledgements{...} -\bibliographystyle{IEEEtran} +\section*{Acknowledgements} +This work is partially funded by the Labex ACTION program (contract ANR-11-LABX-01-01). +Computations presented in this article were realised on the supercomputing +facilities provided by the M\'esocentre de calcul de Franche-Comt\'e. + + + + +\bibliographystyle{elsarticle-num} \bibliography{biblio} @@ -796,9 +505,6 @@ classical statistical tests. % Can use something like this to put references on a page % by themselves when using endfloat and the captionsoff option. -\ifCLASSOPTIONcaptionsoff - \newpage -\fi @@ -876,5 +582,3 @@ classical statistical tests. % that's all folks \end{document} - - diff --git a/preliminaries.tex b/preliminaries.tex index d86df57..35d48a1 100644 --- a/preliminaries.tex +++ b/preliminaries.tex @@ -97,8 +97,8 @@ return $x$\; Based on this setup, we can study the chaos properties of these -function. -This is the aims of the next section. +functions. +This is the aim of the next section. %%% Local Variables: diff --git a/prng.tex b/prng.tex index 4dbeea7..8925e51 100644 --- a/prng.tex +++ b/prng.tex @@ -187,7 +187,7 @@ on $\chi_{\textit{16HamG}}$ using different functions, namely $\textcircled{a}$,\ldots, $\textcircled{e}$. In this algorithm implementation, the embedded PRNG \textit{Random} is the default Python PRNG, \textit{i.e.}, -the Mersenne Twister Algorithm~\cite{matsumoto1998mersenne}. +the Mersenne Twister algorithm~\cite{matsumoto1998mersenne}. Implementations for $\mathsf{N}=4, \dots, 8$ of this algorithm is evaluated through the NIST test suite and results are given in columns $\textit{MT}_4$, \ldots, $\textit{MT}_8$. @@ -198,55 +198,57 @@ We first can see in Table \ref{The passing rate} that all the rates are greater than 97/100, \textit{i.e.}, all the generators achieve to pass the NIST battery of tests. It can be noticed that adding chaos properties for Mersenne Twister -algorithm does not reduce its security aginst this statistical tests. +algorithm does not reduce its security against this statistical tests. \begin{table*} -\renewcommand{\arraystretch}{1.3} +\renewcommand{\arraystretch}{1.1} \begin{center} \begin{tiny} \setlength{\tabcolsep}{2pt} - -% \begin{tabular}{|l|l|l|l|l|l|} -% \hline -% Method &$\textcircled{a}$& $\textcircled{b}$ & $\textcircled{c}$ & $\textcircled{d}$ & $\textcircled{e}$ \\ \hline\hline -% Frequency (Monobit)& 0.851 (0.98)& 0.719 (0.99)& 0.699 (0.99)& 0.514 (1.0)& 0.798 (0.99)\\ \hline -% Frequency (Monobit)& 0.851 (0.98)& 0.719 (0.99)& 0.699 (0.99)& 0.514 (1.0)& 0.798 (0.99)\\ \hline -% Frequency within a Block& 0.262 (0.98)& 0.699 (0.98)& 0.867 (0.99)& 0.145 (1.0)& 0.455 (0.99)\\ \hline -% Cumulative Sums (Cusum) *& 0.301 (0.98)& 0.521 (0.99)& 0.688 (0.99)& 0.888 (1.0)& 0.598 (1.0)\\ \hline -% Runs& 0.224 (0.97)& 0.383 (0.97)& 0.108 (0.96)& 0.213 (0.99)& 0.616 (0.99)\\ \hline -% Longest Run of 1s & 0.383 (1.0)& 0.474 (1.0)& 0.983 (0.99)& 0.699 (0.98)& 0.897 (0.96)\\ \hline -% Binary Matrix Rank& 0.213 (1.0)& 0.867 (0.99)& 0.494 (0.98)& 0.162 (0.99)& 0.924 (0.99)\\ \hline -% Disc. Fourier Transf. (Spect.)& 0.474 (1.0)& 0.739 (0.99)& 0.012 (1.0)& 0.678 (0.98)& 0.437 (0.99)\\ \hline -% Unoverlapping Templ. Match.*& 0.505 (0.990)& 0.521 (0.990)& 0.510 (0.989)& 0.511 (0.990)& 0.499 (0.990)\\ \hline -% Overlapping Temp. Match.& 0.574 (0.98)& 0.304 (0.99)& 0.437 (0.97)& 0.759 (0.98)& 0.275 (0.99)\\ \hline -% Maurer's Universal Statistical& 0.759 (0.96)& 0.699 (0.97)& 0.191 (0.98)& 0.699 (1.0)& 0.798 (0.97)\\ \hline -% Approximate Entropy (m=10)& 0.759 (0.99)& 0.162 (0.99)& 0.867 (0.99)& 0.534 (1.0)& 0.616 (0.99)\\ \hline -% Random Excursions *& 0.666 (0.994)& 0.410 (0.962)& 0.287 (0.998)& 0.365 (0.994)& 0.480 (0.985)\\ \hline -% Random Excursions Variant *& 0.337 (0.988)& 0.519 (0.984)& 0.549 (0.994)& 0.225 (0.995)& 0.533 (0.993)\\ \hline -% Serial* (m=10)& 0.630 (0.99)& 0.529 (0.99)& 0.460 (0.99)& 0.302 (0.995)& 0.360 (0.985)\\ \hline -% Linear Complexity& 0.719 (1.0)& 0.739 (0.99)& 0.759 (0.98)& 0.122 (0.97)& 0.514 (0.99)\\ \hline -\begin{tabular}{|l|r|r|r|r|r||r|r|r|r|r|} +\begin{tabular}{|l|r|r|r|r|r|} \hline Test & $\textit{MT}_4$ & $\textit{MT}_5$& $\textit{MT}_6$& $\textit{MT}_7$& $\textit{MT}_8$ + \\ \hline +Frequency (Monobit)& 0.924 (1.0)& 0.678 (0.98)& 0.102 (0.97)& 0.213 (0.98)& 0.719 (0.99) \\ \hline +Frequency within a Block& 0.514 (1.0)& 0.419 (0.98)& 0.129 (0.98)& 0.275 (0.99)& 0.455 (0.99)\\ \hline +Cumulative Sums (Cusum) *& 0.668 (1.0)& 0.568 (0.99)& 0.881 (0.98)& 0.529 (0.98)& 0.657 (0.995)\\ \hline +Runs& 0.494 (0.99)& 0.595 (0.97)& 0.071 (0.97)& 0.017 (1.0)& 0.834 (1.0)\\ \hline +Longest Run of Ones in a Block& 0.366 (0.99)& 0.554 (1.0)& 0.042 (0.99)& 0.051 (0.99)& 0.897 (0.97)\\ \hline +Binary Matrix Rank& 0.275 (0.98)& 0.494 (0.99)& 0.719 (1.0)& 0.334 (0.98)& 0.637 (0.99)\\ \hline +Discrete Fourier Transform (Spectral)& 0.122 (0.98)& 0.108 (0.99)& 0.108 (1.0)& 0.514 (0.99)& 0.534 (0.98)\\ \hline +Non-overlapping Template Matching*& 0.483 (0.990)& 0.507 (0.990)& 0.520 (0.988)& 0.494 (0.988)& 0.515 (0.989)\\ \hline +Overlapping Template Matching& 0.595 (0.99)& 0.759 (1.0)& 0.637 (1.0)& 0.554 (0.99)& 0.236 (1.0)\\ \hline +Maurer's "Universal Statistical"& 0.202 (0.99)& 0.000 (0.99)& 0.514 (0.98)& 0.883 (0.97)& 0.366 (0.99)\\ \hline +Approximate Entropy (m=10)& 0.616 (0.99)& 0.145 (0.99)& 0.455 (0.99)& 0.262 (0.97)& 0.494 (1.0)\\ \hline +Random Excursions *& 0.275 (1.0)& 0.495 (0.975)& 0.465 (0.979)& 0.452 (0.991)& 0.260 (0.989)\\ \hline +Random Excursions Variant *& 0.382 (0.995)& 0.400 (0.994)& 0.417 (0.984)& 0.456 (0.991)& 0.389 (0.991)\\ \hline +Serial* (m=10)& 0.629 (0.99)& 0.963 (0.99)& 0.366 (0.995)& 0.537 (0.985)& 0.253 (0.995)\\ \hline +Linear Complexity& 0.494 (0.99)& 0.514 (0.98)& 0.145 (1.0)& 0.657 (0.98)& 0.145 (0.99)\\ \hline +\end{tabular} + +\begin{tabular}{|l|r|r|r|r|r|} + \hline +Test &$\textcircled{a}$& $\textcircled{b}$ & $\textcircled{c}$ & $\textcircled{d}$ & $\textcircled{e}$ \\ \hline -Frequency (Monobit)& 0.924 (1.0)& 0.678 (0.98)& 0.102 (0.97)& 0.213 (0.98)& 0.719 (0.99)& 0.129 (1.0)& 0.181 (1.0)& 0.637 (0.99)& 0.935 (1.0)& 0.978 (1.0)\\ \hline -Frequency within a Block& 0.514 (1.0)& 0.419 (0.98)& 0.129 (0.98)& 0.275 (0.99)& 0.455 (0.99)& 0.275 (1.0)& 0.534 (0.98)& 0.066 (1.0)& 0.719 (1.0)& 0.366 (1.0)\\ \hline -Cumulative Sums (Cusum) *& 0.668 (1.0)& 0.568 (0.99)& 0.881 (0.98)& 0.529 (0.98)& 0.657 (0.995)& 0.695 (1.0)& 0.540 (1.0)& 0.514 (0.985)& 0.773 (0.995)& 0.506 (0.99)\\ \hline -Runs& 0.494 (0.99)& 0.595 (0.97)& 0.071 (0.97)& 0.017 (1.0)& 0.834 (1.0)& 0.897 (0.99)& 0.051 (1.0)& 0.102 (0.98)& 0.616 (0.99)& 0.191 (1.0)\\ \hline -Longest Run of Ones in a Block& 0.366 (0.99)& 0.554 (1.0)& 0.042 (0.99)& 0.051 (0.99)& 0.897 (0.97)& 0.851 (1.0)& 0.595 (0.99)& 0.419 (0.98)& 0.616 (0.98)& 0.897 (1.0)\\ \hline -Binary Matrix Rank& 0.275 (0.98)& 0.494 (0.99)& 0.719 (1.0)& 0.334 (0.98)& 0.637 (0.99)& 0.419 (1.0)& 0.946 (0.99)& 0.319 (0.99)& 0.739 (0.97)& 0.366 (1.0)\\ \hline -Discrete Fourier Transform (Spectral)& 0.122 (0.98)& 0.108 (0.99)& 0.108 (1.0)& 0.514 (0.99)& 0.534 (0.98)& 0.867 (1.0)& 0.514 (1.0)& 0.145 (1.0)& 0.224 (0.99)& 0.304 (1.0)\\ \hline -Non-overlapping Template Matching*& 0.483 (0.990)& 0.507 (0.990)& 0.520 (0.988)& 0.494 (0.988)& 0.515 (0.989)& 0.542 (0.990)& 0.512 (0.989)& 0.505 (0.990)& 0.494 (0.989)& 0.493 (0.991)\\ \hline -Overlapping Template Matching& 0.595 (0.99)& 0.759 (1.0)& 0.637 (1.0)& 0.554 (0.99)& 0.236 (1.0)& 0.275 (0.99)& 0.080 (0.99)& 0.574 (0.98)& 0.798 (0.99)& 0.834 (0.99)\\ \hline -Maurer's "Universal Statistical"& 0.202 (0.99)& 0.000 (0.99)& 0.514 (0.98)& 0.883 (0.97)& 0.366 (0.99)& 0.383 (0.99)& 0.991 (0.98)& 0.851 (1.0)& 0.595 (0.98)& 0.514 (1.0)\\ \hline -Approximate Entropy (m=10)& 0.616 (0.99)& 0.145 (0.99)& 0.455 (0.99)& 0.262 (0.97)& 0.494 (1.0)& 0.935 (1.0)& 0.719 (1.0)& 0.883 (1.0)& 0.719 (0.97)& 0.366 (0.99)\\ \hline -Random Excursions *& 0.275 (1.0)& 0.495 (0.975)& 0.465 (0.979)& 0.452 (0.991)& 0.260 (0.989)& 0.396 (0.991)& 0.217 (0.989)& 0.445 (0.975)& 0.743 (0.993)& 0.380 (0.990)\\ \hline -Random Excursions Variant *& 0.382 (0.995)& 0.400 (0.994)& 0.417 (0.984)& 0.456 (0.991)& 0.389 (0.991)& 0.486 (0.997)& 0.373 (0.981)& 0.415 (0.994)& 0.424 (0.991)& 0.380 (0.991)\\ \hline -Serial* (m=10)& 0.629 (0.99)& 0.963 (0.99)& 0.366 (0.995)& 0.537 (0.985)& 0.253 (0.995)& 0.350 (1.0)& 0.678 (0.995)& 0.287 (0.995)& 0.740 (0.99)& 0.301 (0.98)\\ \hline -Linear Complexity& 0.494 (0.99)& 0.514 (0.98)& 0.145 (1.0)& 0.657 (0.98)& 0.145 (0.99)& 0.455 (0.99)& 0.867 (1.0)& 0.401 (0.99)& 0.191 (0.97)& 0.699 (1.0)\\ \hline +Frequency (Monobit)&0.129 (1.0)& 0.181 (1.0)& 0.637 (0.99)& 0.935 (1.0)& 0.978 (1.0)\\ \hline +Frequency within a Block& 0.275 (1.0)& 0.534 (0.98)& 0.066 (1.0)& 0.719 (1.0)& 0.366 (1.0)\\ \hline +Cumulative Sums (Cusum) *& 0.695 (1.0)& 0.540 (1.0)& 0.514 (0.985)& 0.773 (0.995)& 0.506 (0.99)\\ \hline +Runs& 0.897 (0.99)& 0.051 (1.0)& 0.102 (0.98)& 0.616 (0.99)& 0.191 (1.0)\\ \hline +Longest Run of Ones in a Block& 0.851 (1.0)& 0.595 (0.99)& 0.419 (0.98)& 0.616 (0.98)& 0.897 (1.0)\\ \hline +Binary Matrix Rank& 0.419 (1.0)& 0.946 (0.99)& 0.319 (0.99)& 0.739 (0.97)& 0.366 (1.0)\\ \hline +Discrete Fourier Transform (Spectral)& 0.867 (1.0)& 0.514 (1.0)& 0.145 (1.0)& 0.224 (0.99)& 0.304 (1.0)\\ \hline +Non-overlapping Template Matching*& 0.542 (0.990)& 0.512 (0.989)& 0.505 (0.990)& 0.494 (0.989)& 0.493 (0.991)\\ \hline +Overlapping Template Matching& 0.275 (0.99)& 0.080 (0.99)& 0.574 (0.98)& 0.798 (0.99)& 0.834 (0.99)\\ \hline +Maurer's "Universal Statistical"& 0.383 (0.99)& 0.991 (0.98)& 0.851 (1.0)& 0.595 (0.98)& 0.514 (1.0)\\ \hline +Approximate Entropy (m=10)& 0.935 (1.0)& 0.719 (1.0)& 0.883 (1.0)& 0.719 (0.97)& 0.366 (0.99)\\ \hline +Random Excursions *& 0.396 (0.991)& 0.217 (0.989)& 0.445 (0.975)& 0.743 (0.993)& 0.380 (0.990)\\ \hline +Random Excursions Variant *& 0.486 (0.997)& 0.373 (0.981)& 0.415 (0.994)& 0.424 (0.991)& 0.380 (0.991)\\ \hline +Serial* (m=10)&0.350 (1.0)& 0.678 (0.995)& 0.287 (0.995)& 0.740 (0.99)& 0.301 (0.98)\\ \hline +Linear Complexity& 0.455 (0.99)& 0.867 (1.0)& 0.401 (0.99)& 0.191 (0.97)& 0.699 (1.0)\\ \hline \end{tabular} + \end{tiny} \end{center} \caption{NIST SP 800-22 test results ($\mathbb{P}_T$)} diff --git a/review.txt b/review.txt index ad465f7..7ae80d2 100644 --- a/review.txt +++ b/review.txt @@ -1,62 +1,17 @@ -Review 1 - -The author first prove the chaotic behaviour of a family of pseudorandom -number generators (PRNG) introduced in a previous work by the same authors. -These PRNGs are based on iterating continuous functions on a discrete domain. - The paper first recalls Devaney’s definition of chaos and presents the proof of -the main results. Next, the authors study the stopping time, i.e. the time until -a uniform distribut -ion is reached. Finally, they evaluate the PRNG against the -NIST suite. -Review 1 - The paper is globally well organized and many examples are provided to help the understanding. Unfortunately, it does not always make it easy to read. Some definition are quite hard to understand, as for example the metric defined in section 3.3. ---> CG +--> We have added a paragraph of explanations and detailed more precisely the two examples. The overall presentation might be greatly improved. Another concern is the lack of comparison with other existing methods. Such a comparison should be provided. ---> CG - - -For theses reasons, I do not recommend acceptance of this contribution in -its current sate. - - -Review 2: - -Some concerns must be noted on the practical side. It is unclear how the algorithm improves the randomness properties, as the results of the randomness test suite is not compared to that of the input PRNG. If that had been a perfect RNG, only 8 bits would have been enough to generate 8 bits, in this case we need 582 bits according to Table 1. This difference has to be justified. - ---> JFC (fait) - -The removal of the Hamiltonian cycle adds an interesting twist to the N-cube, but the importance of this complication is not emphasized properly. - ---> JFC (fait) - -It would be also interesting to see the comparison of the theoretical and simulated bounds on tau. - ---> JFC (Fait) - +--> A subsection of comparison with well known generators has been added to the document (end of Section III). What is more, there are some basic mathematical errors that should not appear in such a paper. On page 6-7, a metric is defined. For the terms u, first per digit absolute difference is introduced, which then suddenly switches to absolute difference of the whole numbers! E.g., for 915 and 277, the first would give |9-2|, |1-7|, |7-5| = 7 6 2, while the other one is |972-277| = 695, which is just not the same. ---> CG - - -Also, in the proof of Lemma 5.3., bitwise uniform randomness is shown (already questionably), which is not sufficient for having a stationary distribution overall. Take for example X such that it is (0,0,...,0) or (1,1,...1) with probability 0.5 each. This is bitwise uniformly random, but is clearly not uniform on the whole cube. - ---> PCH (fait) - - -The level of English is borderline acceptable, it should be checked more carefully. For example, it is unclear why examples are "running". In the middle of page we find "With all this material" for which "Based on this setup" or something similar would be more appropriate; bottom of page 10 says "Basically, let consider" instead of "Basically, let us consider", and so on. - ---> JFC (fait) - - -Based on all these observations the reviewer considers the paper not to be acceptable in the current form. +--> It is right, sorry for the mistake. Article has been updated. diff --git a/stopping.tex b/stopping.tex index 539d653..142da7f 100644 --- a/stopping.tex +++ b/stopping.tex @@ -10,7 +10,7 @@ interpreted as Markov chains. \begin{xpl} Let us consider for instance the graph $\Gamma(f)$ defined -in \textsc{Figure~\ref{fig:iteration:f*}.} and +in Figure~\ref{fig:iteration:f*} and the probability function $p$ defined on the set of edges as follows: $$ p(e) \left\{ @@ -39,13 +39,13 @@ P=\dfrac{1}{6} \left( A specific random walk in this modified hypercube is first -introduced (See section~\ref{sub:stop:formal}). We further +introduced (see Section~\ref{sub:stop:formal}). We further study this random walk in a theoretical way to provide an upper bound of fair sequences -(See section~\ref{sub:stop:bound}). -We finally complete these study with experimental +(see Section~\ref{sub:stop:bound}). +We finally complete this study with experimental results that reduce this bound (Sec.~\ref{sub:stop:exp}). -Notice that for a general references on Markov chains +For a general reference on Markov chains, see~\cite{LevinPeresWilmer2006}, and particularly Chapter~5 on stopping times. @@ -76,7 +76,7 @@ $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ %% \textit{i.e.}, is the time until the matrix $X$ of a Markov chain %% is $\epsilon$-close to a stationary distribution. -Intutively speaking, $t_{\rm mix}(\varepsilon)$ is the time/steps required +Intuitively speaking, $t_{\rm mix}(\varepsilon)$ is the time/steps required to be sure to be $\varepsilon$-close to the stationary distribution, wherever the chain starts. @@ -138,7 +138,7 @@ ${\mathsf{N}}$-cube. Let $h$ be a function from $\Bool^{\mathsf{N}}$ into $\llbracket 1, {\mathsf{N}} \rrbracket$. Intuitively speaking $h$ aims at memorizing for each node $X \in \Bool^{\mathsf{N}}$ which edge is removed in the Hamiltonian cycle, -\textit{i.e.} which bit in $\llbracket 1, {\mathsf{N}} \rrbracket$ +\textit{i.e.}, which bit in $\llbracket 1, {\mathsf{N}} \rrbracket$ cannot be switched. @@ -208,7 +208,7 @@ $$ An integer $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ is said {\it fair} at time $t$ if there exists $0\leq j t)\leq \frac{E[\tau]}{t}$. With $t_n=32N^2+16N\ln (N+1)$, one obtains: $\P_X(\tau > t_n)\leq \frac{1}{4}$. -Therefore, using the defintion of $t_{\rm mix)}$ and +Therefore, using the definition of $t_{\rm mix}$ and Theorem~\ref{thm-sst}, it follows that $t_{\rm mix}\leq 32N^2+16N\ln (N+1)=O(N^2)$. @@ -377,19 +377,19 @@ are more regular and more binding than this constraint. Moreover, the bound is obtained using the coarse Markov Inequality. For the classical (lazzy) random walk the $\mathsf{N}$-cube, without removing any -Hamiltonian cylce, the mixing time is in $\Theta(N\ln N)$. +Hamiltonian cycle, the mixing time is in $\Theta(N\ln N)$. We conjecture that in our context, the mixing time is also in $\Theta(N\ln N)$. -In this later context, we claim that the upper bound for the stopping time +In this latter context, we claim that the upper bound for the stopping time should be reduced. This fact is studied in the next section. \subsection{Practical Evaluation of Stopping Times}\label{sub:stop:exp} Let be given a function $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ and an initial seed $x^0$. -The pseudo code given in algorithm~\ref{algo:stop} returns the smallest +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. @@ -414,19 +414,19 @@ $\textit{fair}\leftarrow\emptyset$\; } \Return{$\textit{nbit}$}\; %\end{scriptsize} -\caption{Pseudo Code of stoping time calculus } +\caption{Pseudo Code of stopping time computation} \label{algo:stop} \end{algorithm} Practically speaking, for each number $\mathsf{N}$, $ 3 \le \mathsf{N} \le 16$, -10 functions have been generated 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 Figure~\ref{fig:stopping:moy} +10 functions have been generated 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. Figure~\ref{fig:stopping:moy} summarizes these results. In this one, a circle represents the approximation of $E[\ts]$ for a given $\mathsf{N}$. The line is the graph of the function $x \mapsto 2x\ln(2x+8)$. It can firstly be observed that the approximation is largely -smaller than the upper bound given in theorem~\ref{prop:stop}. +smaller than the upper bound given in Theorem~\ref{prop:stop}. It can be further deduced that the conjecture of the previous section is realistic according the graph of $x \mapsto 2x\ln(2x+8)$.