main.tex

   1 \documentclass{ita}
   2 \usepackage{graphicx}
   3 \usepackage{caption}
   4 \usepackage{subcaption}
   5
   6 \usepackage{dsfont}
   7 \usepackage{stmaryrd}
   8 %\usepackage[font=footnotesize]{subfig}
   9 \usepackage{ifthen}
  10 \usepackage{color}
  11 \usepackage{algorithm2e}
  12 \usepackage{epstopdf}
  13 %\usepackage{ntheorem}
  14
  15 \usepackage[utf8]{inputenc}
  16 \usepackage[T1]{fontenc}
  17 \usepackage[english]{babel}
  18 \usepackage{amsmath,amssymb,latexsym,eufrak,euscript}
  19 \usepackage{pstricks,pst-node,pst-coil}
  20
  21
  22 \usepackage{url,tikz}
  23 \usepackage{pgflibrarysnakes}
  24
  25 \usepackage{multicol}
  26
  27 \usetikzlibrary{arrows}
  28 \usetikzlibrary{automata}
  29 \usetikzlibrary{snakes}
  30 \usetikzlibrary{shapes}
  31
  32
  33 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  34 % Définitions personnelles
  35 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  36
  37 \definecolor{bleuclair}{rgb}{0.75,0.75,1.0}
  38 \newcommand{\ANNOT}[1]{
  39   ~\linebreak
  40   \centerline{
  41     {\Huge{\danger}}
  42     \large\fcolorbox{black}{bleuclair}{
  43       \begin{minipage}[h]{.8\linewidth}
  44         #1
  45       \end{minipage}
  46     }
  47     {\Huge{\danger}}
  48   }
  49 }
  50
  51
  52
  53 \newcommand {\tv}[1] {\lVert #1 \rVert_{\rm TV}}
  54 \def \top {1.8}
  55 \def \topt {2.3}
  56 \def \P {\mathbb{P}}
  57 \def \ov {\overline}
  58 \def \ts {\tau_{\rm stop}}
  59
  60
  61 \newtheorem*{xpl}{Running Example}
  62
  63 \newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}}
  64 %\newcommand{\ie}{\textit{i.e.}}
  65 \newcommand{\Nats}[0]{\ensuremath{\mathbb{N}}}
  66 \newcommand{\R}[0]{\ensuremath{\mathbb{R}}}
  67 \newcommand{\Z}[0]{\ensuremath{\mathbb{Z}}}
  68 \newcommand{\Bool}[0]{\ensuremath{\mathds{B}}}
  69 \newcommand{\rel}[0]{\ensuremath{{\mathcal{R}}}}
  70 \newcommand{\Gall}[0]{\ensuremath{\mathcal{G}}}
  71
  72
  73 \newcommand{\JFC}[1]{\begin{color}{green}\textit{#1}\end{color}}
  74 \newcommand{\CG}[1]{\begin{color}{blue}\textit{}\end{color}}
  75 \newcommand{\og}[0]{``}
  76 \newcommand{\fg}[1]{''}
  77
  78
  79
  80
  81
  82
  83 \title{Random Walk in a N-cube Without Hamiltonian Cycle
  84   to Chaotic Pseudorandom Number Generation: Theoretical and Practical
  85   Considerations}
  86
  87 \begin{document}
  88
  89 \author{Sylvain Contassot-Vivier, Jean-François Couchot, Christophe Guyeux, Pierre-Cyrille Heam}
  90 \address{LORIA, Université de Lorraine, Nancy, France\\
  91 FEMTO-ST Institute, University of Franche-Comté, Belfort, France}
  92
  93 \keywords{Pseudorandom Number Generator, Theory of Chaos, Markov Matrice, Hamiltonian Path,  Stopping Time, Statistical Test}
  94
  95 \subjclass{34C28, 37A25,11K45}
  96
  97 \begin{abstract}
  98 This paper is dedicated to the design of chaotic random generators
  99 and extends previous works proposed by some of the authors.
 100 We propose a theoretical framework proving both the chaotic properties and
 101 that the limit distribution is uniform.
 102 A theoretical bound on the stationary time is given and
 103 practical experiments show that the generators successfully pass
 104 the classical statistical tests.
 105 \end{abstract}
 106
 107 \maketitle
 108
 109 \section{Introduction}
 110 \input{intro}
 111
 112 \section{Preliminaries}\label{sec:preliminaries}
 113 \input{preliminaries}
 114
 115 \section{Proof Of Chaos}\label{sec:proofOfChaos}
 116 \input{chaos}
 117
 118 \section{Functions with Strongly Connected $\Gamma_{\{b\}}(f)$}\label{sec:SCCfunc}
 119 \input{generating}
 120
 121 \section{Balanced Hamiltonian Cycle}\label{sec:hamilton}
 122 \input{hamilton}
 123
 124
 125 \section{Mixing Time}\label{sec:hypercube}
 126 \input{stopping}
 127
 128 \section{Experiments}\label{sec:prng}
 129 \input{prng}
 130
 131
 132
 133 \section{Conclusion}
 134 \input{conclusion}
 135
 136 %\acknowledgements{...}
 137
 138 \bibliographystyle{alpha}
 139 \bibliography{biblio}
 140
 141 \end{document}
 142
 143 %%% Local Variables:
 144 %%% mode: latex
 145 %%% ispell-dictionary: "american"
 146 %%% mode: flyspell
 147 %%% End: