X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/6c611637ef05c993351fece7ff89ee10a2090031..refs/heads/master:/main.tex?ds=sidebyside diff --git a/main.tex b/main.tex index 6225751..01df881 100644 --- a/main.tex +++ b/main.tex @@ -1,77 +1,22 @@ -%% 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{ws-ijbc} \usepackage{graphicx} -\usepackage{caption} -\usepackage{subcaption} +%\usepackage{amsthm} +%\usepackage{subcaption} +\usepackage{subfigure} \usepackage{dsfont} \usepackage{stmaryrd} %\usepackage[font=footnotesize]{subfig} \usepackage{ifthen} \usepackage{color} +%\usepackage{subfigure} \usepackage{algorithm2e} \usepackage{epstopdf} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage[english]{babel} -\usepackage{amsmath,amssymb,amsthm,latexsym,eufrak,euscript} +%\usepackage{amsmath,amssymb,amsthm,latexsym,eufrak,euscript} \usepackage{pstricks,pst-node,pst-coil} @@ -115,9 +60,10 @@ \def \ts {\tau_{\rm stop}} -\newtheorem*{xpl}{Running Example} +%\newtheorem*{xpl}{Running Example} +\newenvironment{xpl}[1][Running Example]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}} -\newtheorem{definition}{Definition} +%\newtheorem{definition}{Definition} \newtheorem{prpstn}{Proposition} \newtheorem{thrm}{Theorem} \newtheorem{crllr}{Corollary} @@ -196,246 +142,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 +164,21 @@ % 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{Sylvain Contassot-Vivier} +\address{LORIA, Université de Lorraine, Nancy, France\\ +sylvain.contassotvivier@loria.fr} + +\author{Jean-François Couchot} +\address{FEMTO-ST Institute, CNRS, Univ. Bourgogne Franche-Comté (UBFC), France\\ +jean-francois.couchot@univ-fcomte.fr} + +\author{Christophe Guyeux} +\address{FEMTO-ST Institute, CNRS, Univ. Bourgogne Franche-Comté (UBFC), France\\ +christophe.guyeux@univ-fcomte.fr} + +\author{Pierre-Cyrille Heam} +\address{FEMTO-ST Institute, CNRS, Univ. Bourgogne Franche-Comté (UBFC), France\\ +pierre-cyrille.heam@univ-fcomte.fr} @@ -493,9 +211,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 +237,7 @@ % make the title area -\maketitle +%\maketitle % As a general rule, do not put math, special symbols or citations % in the abstract or keywords. @@ -538,34 +253,6 @@ % the classical statistical tests. % \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 -PRNGs: -the quality of the output would be an obvious consequence of some chaos -properties. -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. - -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 -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 -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} - - - % Note that keywords are not normally used for peerreview papers. % \begin{IEEEkeywords} @@ -585,7 +272,35 @@ 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 + +\begin{abstract} + Designing a pseudorandom number generator (PRNG) is a +difficult and complex task. Many recent works have considered chaotic +functions as the basis of built PRNGs: the quality of the output would +indeed +be an obvious consequence of some chaos properties. However, there is +no direct reasoning that goes from chaotic functions to uniform +distribution of the output. +Moreover, +embedding such kind of functions into a PRNG does not necessarily +allow to get a chaotic output, +which could be required for simulating 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 +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 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} + + +\keywords{Pseudorandom Numbers Generator, Chaotic iterations, Random Walk} \section{Introduction} @@ -594,7 +309,7 @@ classical statistical tests. \section{Preliminaries}\label{sec:preliminaries} \input{preliminaries} -\section{Proof Of Chaos}\label{sec:proofOfChaos} +\section{Proof of Chaos}\label{sec:proofOfChaos} \input{chaos} \section{Functions with Strongly Connected $\Gamma_{\{b\}}(f)$}\label{sec:SCCfunc} @@ -617,7 +332,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{ws-ijbc} \bibliography{biblio} @@ -796,9 +519,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 +596,3 @@ classical statistical tests. % that's all folks \end{document} - -