X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/3fc31015143d2bab7226a54390f3e1c5eba8f4d5..151dc81946eee7c7fb5fbc327ada099f2af6a2c3:/main.tex diff --git a/main.tex b/main.tex index d8445bf..01df881 100644 --- a/main.tex +++ b/main.tex @@ -1,21 +1,22 @@ -\documentclass[preprint,review,12pt]{elsarticle} - +\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} @@ -59,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} @@ -162,12 +164,21 @@ % a separate \thanks must be used for each paragraph as LaTeX2e's \thanks % was not built to handle multiple paragraphs % -\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} +\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} @@ -242,31 +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 considered 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 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} - - - % Note that keywords are not normally used for peerreview papers. % \begin{IEEEkeywords} @@ -288,6 +274,34 @@ classical statistical tests. % creates the second title. It will be ignored for other modes. \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} \input{intro} @@ -295,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} @@ -326,7 +340,7 @@ facilities provided by the M\'esocentre de calcul de Franche-Comt\'e. -\bibliographystyle{elsarticle-num} +\bibliographystyle{ws-ijbc} \bibliography{biblio}