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{\danger}{!!}
  39 \newcommand{\ANNOT}[1]{
  40   ~\linebreak
  41   \centerline{
  42     {\Huge{$\Rightarrow$}}
  43     \large\fcolorbox{black}{bleuclair}{
  44       \begin{minipage}[h]{.8\linewidth}
  45         #1
  46       \end{minipage}
  47     }
  48     {\Huge{$\Leftarrow$}}
  49   }
  50 }
  51
  52
  53
  54 \newcommand {\tv}[1] {\lVert #1 \rVert_{\rm TV}}
  55 \def \top {1.8}
  56 \def \topt {2.3}
  57 \def \P {\mathbb{P}}
  58 \def \ov {\overline}
  59 \def \ts {\tau_{\rm stop}}
  60
  61
  62 \newtheorem*{xpl}{Running Example}
  63
  64 \newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}}
  65 %\newcommand{\ie}{\textit{i.e.}}
  66 \newcommand{\Nats}[0]{\ensuremath{\mathbb{N}}}
  67 \newcommand{\R}[0]{\ensuremath{\mathbb{R}}}
  68 \newcommand{\Z}[0]{\ensuremath{\mathbb{Z}}}
  69 \newcommand{\Bool}[0]{\ensuremath{\mathds{B}}}
  70 \newcommand{\rel}[0]{\ensuremath{{\mathcal{R}}}}
  71 \newcommand{\Gall}[0]{\ensuremath{\mathcal{G}}}
  72
  73
  74 \newcommand{\JFC}[1]{\begin{color}{green}\textit{#1}\end{color}}
  75 \newcommand{\CG}[1]{\begin{color}{blue}\textit{}\end{color}}
  76 \newcommand{\og}[0]{``}
  77 \newcommand{\fg}[1]{''}
  78
  79
  80
  81
  82
  83
  84 \title{Random Walk in a N-cube Without Hamiltonian Cycle
  85   to Chaotic Pseudorandom Number Generation: Theoretical and Practical
  86   Considerations}
  87
  88 \begin{document}
  89
  90 \author{Sylvain Contassot-Vivier, Jean-François Couchot, Christophe Guyeux, Pierre-Cyrille Heam}
  91 \address{LORIA, Université de Lorraine, Nancy, France\\
  92 FEMTO-ST Institute, University of Franche-Comté, Belfort, France}
  93
  94 \keywords{Pseudorandom Number Generator, Theory of Chaos, Markov Matrice, Hamiltonian Path,  Stopping Time, Statistical Test}
  95
  96 \subjclass{34C28, 37A25,11K45}
  97
  98 \begin{abstract}
  99 This paper is dedicated to the design of chaotic random generators
 100 and extends previous works proposed by some of the authors.
 101 We propose a theoretical framework proving both the chaotic properties and
 102 that the limit distribution is uniform.
 103 A theoretical bound on the stationary time is given and
 104 practical experiments show that the generators successfully pass
 105 the classical statistical tests.
 106 \end{abstract}
 107
 108 \maketitle
 109
 110 \section{Introduction}
 111 \input{intro}
 112
 113 \section{Preliminaries}\label{sec:preliminaries}
 114 \input{preliminaries}
 115
 116 \section{Proof Of Chaos}\label{sec:proofOfChaos}
 117 \input{chaos}
 118
 119 \section{Functions with Strongly Connected $\Gamma_{\{b\}}(f)$}\label{sec:SCCfunc}
 120 \input{generating}
 121
 122 \section{Balanced Hamiltonian Cycle}\label{sec:hamilton}
 123 \input{hamilton}
 124
 125
 126 \section{Stopping Time}\label{sec:hypercube}
 127 \input{stopping}
 128
 129 \section{Experiments}\label{sec:prng}
 130 \input{prng}
 131
 132
 133
 134 \section{Conclusion}
 135 \input{conclusion}
 136
 137 %\acknowledgements{...}
 138
 139 \bibliographystyle{alpha}
 140 \bibliography{biblio}
 141
 142 \end{document}
 143
 144 %%% Local Variables:
 145 %%% mode: latex
 146 %%% ispell-dictionary: "american"
 147 %%% mode: flyspell
 148 %%% End: