X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/31468b39be240f447015be22c252d515b2dcfdac..1991bb9a2fa344a1bc72ce3222b43bec10ff2f34:/main.tex?ds=inline diff --git a/main.tex b/main.tex index 4a5ede1..01df881 100644 --- a/main.tex +++ b/main.tex @@ -1,21 +1,22 @@ -\documentclass{ita} + +\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{ntheorem} - \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage[english]{babel} -\usepackage{amsmath,amssymb,latexsym,eufrak,euscript} +%\usepackage{amsmath,amssymb,amsthm,latexsym,eufrak,euscript} \usepackage{pstricks,pst-node,pst-coil} @@ -59,7 +60,16 @@ \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{prpstn}{Proposition} +\newtheorem{thrm}{Theorem} +\newtheorem{crllr}{Corollary} +\newtheorem{lmm}{Lemma} + + \newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}} %\newcommand{\ie}{\textit{i.e.}} @@ -81,31 +91,217 @@ + +% Some very useful LaTeX packages include: +% (uncomment the ones you want to load) + + +% *** MISC UTILITY PACKAGES *** +% +%\usepackage{ifpdf} +% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional +% compilation based on whether the output is pdf or dvi. +% usage: +% \ifpdf +% % pdf code +% \else +% % dvi code +% \fi +% The latest version of ifpdf.sty can be obtained from: +% http://www.ctan.org/pkg/ifpdf +% Also, note that IEEEtran.cls V1.7 and later provides a builtin +% \ifCLASSINFOpdf conditional that works the same way. +% When switching from latex to pdflatex and vice-versa, the compiler may +% have to be run twice to clear warning/error messages. + + + + + + +% *** CITATION PACKAGES *** +% +%\usepackage{cite} +% cite.sty was written by Donald Arseneau +% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package +% \cite{} output to follow that of the IEEE. Loading the cite package will +% result in citation numbers being automatically sorted and properly +% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using +% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's +% \cite will automatically add leading space, if needed. Use cite.sty's +% noadjust option (cite.sty V3.8 and later) if you want to turn this off +% such as if a citation ever needs to be enclosed in parenthesis. +% cite.sty is already installed on most LaTeX systems. Be sure and use +% version 5.0 (2009-03-20) and later if using hyperref.sty. +% The latest version can be obtained at: +% http://www.ctan.org/pkg/cite +% The documentation is contained in the cite.sty file itself. + + + + + + +\begin{document} +% +% paper title +% Titles are generally capitalized except for words such as a, an, and, as, +% at, but, by, for, in, nor, of, on, or, the, to and up, which are usually +% not capitalized unless they are the first or last word of the title. +% Linebreaks \\ can be used within to get better formatting as desired. +% Do not put math or special symbols in the title. \title{Random Walk in a N-cube Without Hamiltonian Cycle to Chaotic Pseudorandom Number Generation: Theoretical and Practical Considerations} -\begin{document} - -\author{Sylvain Contassot-Vivier, Jean-François Couchot, Christophe Guyeux, Pierre-Cyrille Heam} +% +% +% author names and IEEE memberships +% note positions of commas and nonbreaking spaces ( ~ ) LaTeX will not break +% a structure at a ~ so this keeps an author's name from being broken across +% two lines. +% use \thanks{} to gain access to the first footnote area +% a separate \thanks must be used for each paragraph as LaTeX2e's \thanks +% was not built to handle multiple paragraphs +% +\author{Sylvain Contassot-Vivier} \address{LORIA, Université de Lorraine, Nancy, France\\ -FEMTO-ST Institute, University of Franche-Comté, Belfort, 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} + + + +% \author{Michael~Shell,~\IEEEmembership{Member,~IEEE,} +% John~Doe,~\IEEEmembership{Fellow,~OSA,} +% and~Jane~Doe,~\IEEEmembership{Life~Fellow,~IEEE}% <-this % stops a space +% \thanks{M. Shell was with the Department +% of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, +% GA, 30332 USA e-mail: (see http://www.michaelshell.org/contact.html).}% <-this % stops a space +% \thanks{J. Doe and J. Doe are with Anonymous University.}% <-this % stops a space +% \thanks{Manuscript received April 19, 2005; revised August 26, 2015.}} + +% note the % following the last \IEEEmembership and also \thanks - +% these prevent an unwanted space from occurring between the last author name +% and the end of the author line. i.e., if you had this: +% +% \author{....lastname \thanks{...} \thanks{...} } +% ^------------^------------^----Do not want these spaces! +% +% a space would be appended to the last name and could cause every name on that +% line to be shifted left slightly. This is one of those "LaTeX things". For +% instance, "\textbf{A} \textbf{B}" will typeset as "A B" not "AB". To get +% "AB" then you have to do: "\textbf{A}\textbf{B}" +% \thanks is no different in this regard, so shield the last } of each \thanks +% that ends a line with a % and do not let a space in before the next \thanks. +% Spaces after \IEEEmembership other than the last one are OK (and needed) as +% you are supposed to have spaces between the names. For what it is worth, +% this is a minor point as most people would not even notice if the said evil +% space somehow managed to creep in. + + + +% The only time the second header will appear is for the odd numbered pages +% after the title page when using the twoside option. +% +% *** Note that you probably will NOT want to include the author's *** +% *** name in the headers of peer review papers. *** +% You can use \ifCLASSOPTIONpeerreview for conditional compilation here if +% you desire. + + + + +% If you want to put a publisher's ID mark on the page you can do it like +% this: +%\IEEEpubid{0000--0000/00\$00.00~\copyright~2015 IEEE} +% Remember, if you use this you must call \IEEEpubidadjcol in the second +% column for its text to clear the IEEEpubid mark. + + -\keywords{Pseudorandom Number Generator, Theory of Chaos, Markov Matrice, Hamiltonian Path, Stopping Time, Statistical Test} +% use for special paper notices +%\IEEEspecialpapernotice{(Invited Paper)} -\subjclass{34C28, 37A25,11K45} + + + +% make the title area +%\maketitle + +% As a general rule, do not put math, special symbols or citations +% in the abstract or keywords. + + +% \begin{abstract} +% This paper is dedicated to the design of chaotic random generators +% and extends previous works proposed by some of the authors. +% We propose a theoretical framework proving both the chaotic properties and +% that the limit distribution is uniform. +% A theoretical bound on the stationary time is given and +% 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} +% IEEE, IEEEtran, journal, \LaTeX, paper, template. +% \end{IEEEkeywords} + + + + + + +% For peer review papers, you can put extra information on the cover +% page as needed: +% \ifCLASSOPTIONpeerreview +% \begin{center} \bfseries EDICS Category: 3-BBND \end{center} +% \fi +% +% For peerreview papers, this IEEEtran command inserts a page break and +% creates the second title. It will be ignored for other modes. +\maketitle \begin{abstract} -This paper is dedicated to the design of chaotic random generators -and extends previous works proposed by some of the authors. -We propose a theoretical framework proving both the chaotic properties and -that the limit distribution is uniform. -A theoretical bound on the stationary time is given and -practical experiments show that the generators successfully pass -the classical statistical tests. + 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} -\maketitle + +\keywords{Pseudorandom Numbers Generator, Chaotic iterations, Random Walk} + \section{Introduction} \input{intro} @@ -113,7 +309,7 @@ the 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} @@ -123,7 +319,7 @@ the classical statistical tests. \input{hamilton} -\section{Stopping Time}\label{sec:hypercube} +\section{Mixing Time}\label{sec:hypercube} \input{stopping} \section{Experiments}\label{sec:prng} @@ -136,13 +332,267 @@ the classical statistical tests. %\acknowledgements{...} -\bibliographystyle{alpha} +\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} -\end{document} -%%% Local Variables: -%%% mode: latex -%%% ispell-dictionary: "american" -%%% mode: flyspell -%%% End: +%\section{Introduction} +% The very first letter is a 2 line initial drop letter followed +% by the rest of the first word in caps. +% +% form to use if the first word consists of a single letter: +% \IEEEPARstart{A}{demo} file is .... +% +% form to use if you need the single drop letter followed by +% normal text (unknown if ever used by the IEEE): +% \IEEEPARstart{A}{}demo file is .... +% +% Some journals put the first two words in caps: +% \IEEEPARstart{T}{his demo} file is .... +% +% Here we have the typical use of a "T" for an initial drop letter +% and "HIS" in caps to complete the first word. +% \IEEEPARstart{T}{his} demo file is intended to serve as a ``starter file'' +% for IEEE journal papers produced under \LaTeX\ using +% IEEEtran.cls version 1.8b and later. +% % You must have at least 2 lines in the paragraph with the drop letter +% % (should never be an issue) +% I wish you the best of success. + +% \hfill mds + +% \hfill August 26, 2015 + +% \subsection{Subsection Heading Here} +% Subsection text here. + +% % needed in second column of first page if using \IEEEpubid +% %\IEEEpubidadjcol + +% \subsubsection{Subsubsection Heading Here} +% Subsubsection text here. + + +% % An example of a floating figure using the graphicx package. +% % Note that \label must occur AFTER (or within) \caption. +% % For figures, \caption should occur after the \includegraphics. +% % Note that IEEEtran v1.7 and later has special internal code that +% % is designed to preserve the operation of \label within \caption +% % even when the captionsoff option is in effect. However, because +% % of issues like this, it may be the safest practice to put all your +% % \label just after \caption rather than within \caption{}. +% % +% % Reminder: the "draftcls" or "draftclsnofoot", not "draft", class +% % option should be used if it is desired that the figures are to be +% % displayed while in draft mode. +% % +% %\begin{figure}[!t] +% %\centering +% %\includegraphics[width=2.5in]{myfigure} +% % where an .eps filename suffix will be assumed under latex, +% % and a .pdf suffix will be assumed for pdflatex; or what has been declared +% % via \DeclareGraphicsExtensions. +% %\caption{Simulation results for the network.} +% %\label{fig_sim} +% %\end{figure} + +% % Note that the IEEE typically puts floats only at the top, even when this +% % results in a large percentage of a column being occupied by floats. + + +% % An example of a double column floating figure using two subfigures. +% % (The subfig.sty package must be loaded for this to work.) +% % The subfigure \label commands are set within each subfloat command, +% % and the \label for the overall figure must come after \caption. +% % \hfil is used as a separator to get equal spacing. +% % Watch out that the combined width of all the subfigures on a +% % line do not exceed the text width or a line break will occur. +% % +% %\begin{figure*}[!t] +% %\centering +% %\subfloat[Case I]{\includegraphics[width=2.5in]{box}% +% %\label{fig_first_case}} +% %\hfil +% %\subfloat[Case II]{\includegraphics[width=2.5in]{box}% +% %\label{fig_second_case}} +% %\caption{Simulation results for the network.} +% %\label{fig_sim} +% %\end{figure*} +% % +% % Note that often IEEE papers with subfigures do not employ subfigure +% % captions (using the optional argument to \subfloat[]), but instead will +% % reference/describe all of them (a), (b), etc., within the main caption. +% % Be aware that for subfig.sty to generate the (a), (b), etc., subfigure +% % labels, the optional argument to \subfloat must be present. If a +% % subcaption is not desired, just leave its contents blank, +% % e.g., \subfloat[]. + + +% % An example of a floating table. Note that, for IEEE style tables, the +% % \caption command should come BEFORE the table and, given that table +% % captions serve much like titles, are usually capitalized except for words +% % such as a, an, and, as, at, but, by, for, in, nor, of, on, or, the, to +% % and up, which are usually not capitalized unless they are the first or +% % last word of the caption. Table text will default to \footnotesize as +% % the IEEE normally uses this smaller font for tables. +% % The \label must come after \caption as always. +% % +% %\begin{table}[!t] +% %% increase table row spacing, adjust to taste +% %\renewcommand{\arraystretch}{1.3} +% % if using array.sty, it might be a good idea to tweak the value of +% % \extrarowheight as needed to properly center the text within the cells +% %\caption{An Example of a Table} +% %\label{table_example} +% %\centering +% %% Some packages, such as MDW tools, offer better commands for making tables +% %% than the plain LaTeX2e tabular which is used here. +% %\begin{tabular}{|c||c|} +% %\hline +% %One & Two\\ +% %\hline +% %Three & Four\\ +% %\hline +% %\end{tabular} +% %\end{table} + + +% % Note that the IEEE does not put floats in the very first column +% % - or typically anywhere on the first page for that matter. Also, +% % in-text middle ("here") positioning is typically not used, but it +% % is allowed and encouraged for Computer Society conferences (but +% % not Computer Society journals). Most IEEE journals/conferences use +% % top floats exclusively. +% % Note that, LaTeX2e, unlike IEEE journals/conferences, places +% % footnotes above bottom floats. This can be corrected via the +% % \fnbelowfloat command of the stfloats package. + + + + +% \section{Conclusion} +% The conclusion goes here. + + + + + +% % if have a single appendix: +% %\appendix[Proof of the Zonklar Equations] +% % or +% %\appendix % for no appendix heading +% % do not use \section anymore after \appendix, only \section* +% % is possibly needed + +% % use appendices with more than one appendix +% % then use \section to start each appendix +% % you must declare a \section before using any +% % \subsection or using \label (\appendices by itself +% % starts a section numbered zero.) +% % + + +% \appendices +% \section{Proof of the First Zonklar Equation} +% Appendix one text goes here. + +% % you can choose not to have a title for an appendix +% % if you want by leaving the argument blank +% \section{} +% Appendix two text goes here. + + +% % use section* for acknowledgment +% \section*{Acknowledgment} + + +% The authors would like to thank... + + +% Can use something like this to put references on a page +% by themselves when using endfloat and the captionsoff option. + + + +% trigger a \newpage just before the given reference +% number - used to balance the columns on the last page +% adjust value as needed - may need to be readjusted if +% the document is modified later +%\IEEEtriggeratref{8} +% The "triggered" command can be changed if desired: +%\IEEEtriggercmd{\enlargethispage{-5in}} + +% references section + +% can use a bibliography generated by BibTeX as a .bbl file +% BibTeX documentation can be easily obtained at: +% http://mirror.ctan.org/biblio/bibtex/contrib/doc/ +% The IEEEtran BibTeX style support page is at: +% http://www.michaelshell.org/tex/ieeetran/bibtex/ +%\bibliographystyle{IEEEtran} +% argument is your BibTeX string definitions and bibliography database(s) +%\bibliography{IEEEabrv,../bib/paper} +% +% manually copy in the resultant .bbl file +% set second argument of \begin to the number of references +% (used to reserve space for the reference number labels box) +% \begin{thebibliography}{1} + +% \bibitem{IEEEhowto:kopka} +% H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus +% 0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999. + +% \end{thebibliography} + +% biography section +% +% If you have an EPS/PDF photo (graphicx package needed) extra braces are +% needed around the contents of the optional argument to biography to prevent +% the LaTeX parser from getting confused when it sees the complicated +% \includegraphics command within an optional argument. (You could create +% your own custom macro containing the \includegraphics command to make things +% simpler here.) +%\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell} +% or if you just want to reserve a space for a photo: + +% \begin{IEEEbiography}{Michael Shell} +% Biography text here. +% \end{IEEEbiography} + +% % if you will not have a photo at all: +% \begin{IEEEbiographynophoto}{John Doe} +% Biography text here. +% \end{IEEEbiographynophoto} + +% % insert where needed to balance the two columns on the last page with +% % biographies +% %\newpage + +% \begin{IEEEbiographynophoto}{Jane Doe} +% Biography text here. +% \end{IEEEbiographynophoto} + +% You can push biographies down or up by placing +% a \vfill before or after them. The appropriate +% use of \vfill depends on what kind of text is +% on the last page and whether or not the columns +% are being equalized. + +%\vfill + +% Can be used to pull up biographies so that the bottom of the last one +% is flush with the other column. +%\enlargethispage{-5in} + + + +% that's all folks +\end{document}