]> AND Private Git Repository - rairo15.git/commitdiff
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
fin reprise preuve chaos
authorcouchot <jf.couchot@gmail.com>
Wed, 11 Mar 2015 21:00:57 +0000 (22:00 +0100)
committercouchot <jf.couchot@gmail.com>
Wed, 11 Mar 2015 21:00:57 +0000 (22:00 +0100)
biblio.bib
chaos.tex
intro.tex
main.tex
markov.bib [deleted file]
preliminaries.tex
prng.tex
stopping.tex

index bba6bf037afba836d25096a28b979183ff204272..30bdba6476faabfe675ba568becdbc79ac0a5969 100644 (file)
 
 @Article{CB01,
   author =      {S.~Contassot-Vivier and J.M.~Bahi},
 
 @Article{CB01,
   author =      {S.~Contassot-Vivier and J.M.~Bahi},
-  title =       {Convergence dans les systèmes booléens asynchrones et application aux
-  réseaux de Hopfield},
-  journal =     {Calculateurs Parallèles},
+  title =       {Convergence dans les systèmes booléens asynchrones et application aux
+  réseaux de Hopfield},
+  journal =     {Calculateurs Parallèles},
   year =        {2001},
   OPTkey =      {},
   volume =      {13},
   year =        {2001},
   OPTkey =      {},
   volume =      {13},
 
 @Article{Rob78,
   author =      {F.~Robert},
 
 @Article{Rob78,
   author =      {F.~Robert},
-  title =       {Th\'{e}or\`{e}me de Perron-Frobenius et Stein-Rosenberg booléens},
+  title =       {Th\'{e}or\`{e}me de Perron-Frobenius et Stein-Rosenberg booléens},
   journal =     {Linear Algebra and Its Applications},
   year =        {1978},
   OPTkey =      {},
   journal =     {Linear Algebra and Its Applications},
   year =        {1978},
   OPTkey =      {},
 }
 
 @Article{GFSP85,
 }
 
 @Article{GFSP85,
-  author =      {E.~Golès and F.~Fogelman-Soulie and D.~Pellegrin},
+  author =      {E.~Golès and F.~Fogelman-Soulie and D.~Pellegrin},
   title =       {Decreasing energy functions as a tool for studying threshold networks},
   journal =     {Disc. Appl. Math.},
   year =        {1985},
   title =       {Decreasing energy functions as a tool for studying threshold networks},
   journal =     {Disc. Appl. Math.},
   year =        {1985},
 
 @PhdThesis{Pel86,
   author =       {D.~Pellegrin},
 
 @PhdThesis{Pel86,
   author =       {D.~Pellegrin},
-  title =        {Algorithmique discrète et réseaux d'automates},
+  title =        {Algorithmique discrète et réseaux d'automates},
   school =       {Grenoble},
   year =         {1986},
   OPTkey =       {},
   school =       {Grenoble},
   year =         {1986},
   OPTkey =       {},
@@ -556,9 +556,9 @@ inhal = {no},
 domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
 equipe = {and},
 classement = {COM},
 domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
 equipe = {and},
 classement = {COM},
-author = {Couchot, Jean-Fran\c{c}ois and Héam, Pierre-Cyrille and Guyeux, Christophe and Wang, Qianxue and Bahi, Jacques},
+author = {Couchot, Jean-Fran\c{c}ois and Héam, Pierre-Cyrille and Guyeux, Christophe and Wang, Qianxue and Bahi, Jacques},
 title = {Traversing a n-cube without Balanced Hamiltonian Cycle to Generate Pseudorandom Numbers},
 title = {Traversing a n-cube without Balanced Hamiltonian Cycle to Generate Pseudorandom Numbers},
-howpublished = {15-th Mons Theoretical Computer Science Days (15e Journées Montoises d'Informatique Théorique), Nancy, France},
+howpublished = {15-th Mons Theoretical Computer Science Days (15e Journées Montoises d'Informatique Théorique), Nancy, France},
 day = 23,
 month = sep,
 year = 2014,
 day = 23,
 month = sep,
 year = 2014,
@@ -569,19 +569,6 @@ year = 2014,
 % Markov.bib
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 % Markov.bib
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
-@inproceedings{chgw14oip,
-   author              = {Jean-François Couchot and 
-                          Pierre-Cyrille Héam and 
-                          Christophe Guyeux and 
-                          Qianxue Wang and 
-                          Jacques M. Bahi},
-   title               = {Pseudorandom Number Generators with Balanced Gray Codes.},
-   booktitle           = {SECRYPT},
-   year                = {2014},
-   pages               = {469-475},
-   address = {Vienna, Austria},
-   publisher = {Springer}
-}
 
 
 @Article{rwfg,
 
 
 @Article{rwfg,
@@ -720,23 +707,6 @@ address = {Luxembourg, Luxembourg},
 month = jun,
 year = 2011}
 
 month = jun,
 year = 2011}
 
-@incollection{bcgr11ip,
-year={2011},
-isbn={978-3-642-22952-7},
-booktitle={Fundamentals of Computation Theory},
-volume={6914},
-series={Lecture Notes in Computer Science},
-editor={Owe, Olaf and Steffen, Martin and Telle, JanArne},
-doi={10.1007/978-3-642-22953-4_11},
-title={On the Link between Strongly Connected Iteration Graphs and Chaotic Boolean Discrete-Time Dynamical Systems},
-url={http://dx.doi.org/10.1007/978-3-642-22953-4_11},
-publisher={Springer Berlin Heidelberg},
-keywords={Boolean network; discrete-time dynamical system; topological chaos},
-author={Bahi, Jacques M. and Couchot, Jean-Francois and Guyeux, Christophe and Richard, Adrien},
-pages={126-137},
-language={English},
-address={Berlin}
-}
 
 @INPROCEEDINGS{bg10aip,
   author = {Bahi, Jacques and Guyeux, Christophe},
 
 @INPROCEEDINGS{bg10aip,
   author = {Bahi, Jacques and Guyeux, Christophe},
@@ -759,7 +729,7 @@ address={Berlin}
 
 @ARTICLE{DBLPjournalsAbs-1112-5239,
   author = {Jacques M. Bahi and Rapha{\"e}l Couturier and Christophe Guyeux and
 
 @ARTICLE{DBLPjournalsAbs-1112-5239,
   author = {Jacques M. Bahi and Rapha{\"e}l Couturier and Christophe Guyeux and
-       Pierre-Cyrille H{é}am},
+       Pierre-Cyrille H{é}am},
   title = {Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom
        Numbers on GPU},
   journal = {CoRR},
   title = {Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom
        Numbers on GPU},
   journal = {CoRR},
@@ -816,7 +786,7 @@ address={Berlin}
   title = {Discrete Iterations, a Metric Study},
   publisher = {Springer-Verlag},
   year = {1986},
   title = {Discrete Iterations, a Metric Study},
   publisher = {Springer-Verlag},
   year = {1986},
-  author = {François Robert},
+  author = {François Robert},
   volume = {6},
   series = {Series in Computational Mathematics}
 }
   volume = {6},
   series = {Series in Computational Mathematics}
 }
@@ -905,22 +875,6 @@ year = 2013,
 
 
 
 
 
 
-@INPROCEEDINGS{cghwb14ip,
-  author = {Couchot, Jean-Fran\c{c}ois and Guyeux, Christophe and Heam, 
-Pierre-Cyrille, and Wang, Qianxue and Bahi, Jacques},
-  title = {Pseudorandom Number Generators with Balanced Gray Codes},
-  booktitle = {SECRYPT 2014, the 11th International Conference on Security and Cryptography},
-  year = {2014},
-  pages = {***--***},
-  address = {Vienna, Austria},
-  month = aug,
-  classement = {ACTI},
-  doi = {10.1007/978-3-642-22953-4_11},
-  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
-  equipe = {and},
-  inhal = {no},
-}
-
 @Article{ZanSup04,
   author =       {Suparta, IN and Zanten, AJ van},
   title =        {Totally balanced and exponentially balanced Gray codes},
 @Article{ZanSup04,
   author =       {Suparta, IN and Zanten, AJ van},
   title =        {Totally balanced and exponentially balanced Gray codes},
index 74d07cf30515e46e915f9256785bc849c05dd706..91b8717f107e292c4928b2a63fd622494c312bcf 100644 (file)
--- a/chaos.tex
+++ b/chaos.tex
@@ -1,19 +1,39 @@
+Let us us first recall the chaos theoretical context presented 
+in~\cite{bcgr11:ip}. In this article, the space of interest 
+is $\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$ 
+and the iteration function $\mathcal{H}_f$ is  
+the map from 
+$\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$ 
+to itself defined by
+\[
+\mathcal{H}_f(x,s)=(F_f(x,s_0),\sigma(s)).
+\] 
+In this definition, 
+$\sigma: \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} \longrightarrow
+ \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} 
+$
+ is a shift operation on sequences (\textit{i.e.}, a function that removes the 
+first element of the sequence) formally defined with
+$$
+\sigma((u^k)_{k \in \Nats}) =  (u^{k+1})_{k \in \Nats}. 
+$$
 
 
+We have proven~\cite[Theorem 1]{bcgr11:ip} that   
+$\mathcal{H}_f$ is chaotic in 
+$\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$
+if and only if $\Gamma(f)$ is strongly connected.
+However, the corrolary which would say that $\chi_{\textit{14Secrypt}}$ is chaotic 
+cannot be directly deduced since we do not output all the successive
+values of iterating $F_f$. Only a a few of them is concerned and 
+any subsequence of a chaotic sequence  is   not  necessarily  
+a   chaotic  sequence  too.
+This necessitates a rigorous proof, which is the aim of this section.
 
 
-\subsection{Notations and terminologies}\label{sec:notations}
 
 
 
 
-Denote by $\mathds{B}$ the Boolean set, by $\mathds{N}^\ast$ the set
-of natural integers $\{1,2,3, \hdots \}$, and by $\mathds{N}=\mathds{N}^\ast \cup \{0\}$.
-For $a,b \in \mathds{N}, a \leqslant b$, $\llbracket a, b \rrbracket$ means the set
-$\{a, a+1, \hdots , b\}$ of integers belonging between $a$ and $b$.
-For any finite set $X$, $|X|$ denotes its cardinality.
-The $n-$th of a sequence $v$ of vectors is $v^n$ while its $i-$th component is $v_i^n$, 
-so $v=\left(v^n\right)_{n \in \mathds{N}}$. 
-Finally, $\overline{x}$ stands for the negation of the Boolean $x$, while $\lfloor y \rfloor$ is
-the largest integer lower than $y$.
 
 
-\subsubsection{Devaney's Chaotic Dynamical Systems}
+
+\subsection{Devaney's Chaotic Dynamical Systems}
 \label{subsec:Devaney}
 
 
 \label{subsec:Devaney}
 
 
@@ -62,93 +82,106 @@ sensitive dependence on initial conditions (this property was formerly an
 element of the definition of chaos). 
 
 
 element of the definition of chaos). 
 
 
-\subsubsection{Introducing the \textit{CIPRNG} categories of chaotic iterations based pseudorandom number generators}
+\subsection{A Metric Space for PRNG Iterations}
+
+% Define by $\mathcal{S}_X$ the set of sequences whose elements belong in $X \subset \mathds{N}, X \neq \varnothing$,
+% that is, $\mathcal{S}_X = \mathcal{X}^\mathds{N}$.
+% Let $\mathsf{N} \in \mathds{N}^\ast$, $f:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$, and
+% $\mathcal{P} \subset \mathds{N}^\ast$ a non empty and finite set of integers.
+
+% Any couple $(u,v) \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$ defines
+% a ``chaotic iterations based'' pseudorandom number generator, which is denoted by  $\textit{CIPRNG}_f^2(u,v)$~\cite{wbg10:ip}. It is 
+% defined as follows:
+% \begin{equation}
+% \label{CIPRNGver2}
+% \left\{
+% \begin{array}{l}
+%  x^0 \in \mathds{B}^\mathsf{N}\\
+%  \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket, x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if  }~ i=u^n \\ x_i^n & \text{else} \end{array} \right.\\
+%  \forall n \in \mathds{N}, y^n = x^{v^n} .
+% \end{array}
+% \right.
+% \end{equation}
+% The outputted sequence produced by this generator is $\left(y^n\right)_{n \in \mathds{N}}$. 
+% Remark that, given a sequence $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ called a ``chaotic strategy'',
+% the following way to iterate: 
+% $$x^0 \in \mathds{B}^\mathsf{N}, \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket,  x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if  }~ i=S^n \\ x_i^n & \text{else} \end{array} \right. ,$$
+% is referred in the discrete mathematics literature as ``chaotic iterations''~\cite{Robert} (a terminology which has
+% \emph{a priori} no relation with the mathematical theory of chaos recalled previously), which
+% explains the name provided to these categories of pseudorandom number generators.
+
+
+% The formerly proposed $\textit{CIPRNG}_f^1(u)$~\cite{bgw09:ip,guyeuxTaiwan10} is equal to \linebreak $\textit{CIPRNG}_f^2\left(u,\left(1\right)_{n\in \mathds{N}}\right)$, where $\left(1\right)_{n\in \mathds{N}}$ is the sequence that is 
+% uniformly equal to 1. 
+% It has been proven as chaotic for the vectorial Boolean negation $f_0:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$, 
+% $(x_1, \hdots , x_\mathsf{N}) \longmapsto (\overline{x_1}, \hdots, \overline{x_\mathsf{N}})$ in \cite{bgw09:ip} 
+% and for a larger set of well-chosen iteration functions in~\cite{bcgr11:ip} but,
+% as only one bit is modified at each iteration, this generator is not able to pass any reasonable statistical tests.
+
+% The $\textit{XOR~CIPRNG}(S)$, for its part~\cite{DBLP:journals/corr/abs-1112-5239}, is defined as follows: $x^0 \in \mathds{B}^\mathsf{N}$, and $\forall n \in \mathds{N}, x^{n+1} = x^n \oplus S^n$
+% where $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ and $\oplus$ stands for the bitwise \emph{exclusive or} (xor) operation
+% between the binary decomposition of $x^n$ and $S^n$. This is indeed a $CIPRNG_{f_0}^2 (u,v)$ generator:
+% %, for 
+% %$u,v \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$: 
+% for any given $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$, $v^n$ is the number
+% of 1's in the binary decomposition of $S^n$ while $u^{v^n}, u^{v^n+1}, \hdots , u^{v^{n+1}-1}$
+% are the positions of these ones.
+% The $\textit{XOR~CIPRNG}$ has been proven chaotic and it is able to pass all the most stringent statistical 
+% batteries of tests~\cite{DBLP:journals/corr/abs-1112-5239}, namely: DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, and TestU01~\cite{LEcuyerS07},
+% which encompasses the two former ones. Furthermore, the output sequence is cryptographically secure
+% when $S$ is cryptographically secure~\cite{DBLP:journals/corr/abs-1112-5239}.
+% We are then left to prove $\textit{CIPRNG}_f^2(u,v)$ is chaotic.
+
+% \subsection{The $\textit{CIPRNG}_f^2(u,v)$ is chaotic for well-chosen $f$}\label{sec:wellchosen}
+
+% \subsection{The generator as a discrete dynamical system}
+
+
+% This algorithm may be seen as $\mathsf{p}$ functional composition of $F_f$.
+% We thus introduce the function 
+% $F_{f,\mathsf{p}} :  \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^\mathsf{p}  \rightarrow \mathds{B}^\mathsf{N}$ defined by 
+
+% $$
+% F_{f,\mathsf{p}} (x,(u^0, u^1, \hdots, u^{\mathsf{p}-1}))  \mapsto 
+% F_f(\hdots (F_f(F_f(x,u^0), u^1), \hdots), u^{\mathsf{p}-1}).
+% $$
+
+
+
+
+Let us first introduce $\mathcal{P} \subset \mathds{N}$ a finite nonempty
+set having the cardinality $\mathsf{p} \in \mathds{N}^\ast$.
+Intuitively, this  is the set of authorized numbers of iterations.
+Denote by $p_1, p_2, \hdots, p_\mathsf{p}$ the ordered elements of $\mathcal{P}$: $\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$
+and $p_1< p_2< \hdots < p_\mathsf{p}$. In our algorithm, 
+$\mathsf{p}$ is 1 and $p_1$ is $b$. 
 
 
-Define by $\mathcal{S}_X$ the set of sequences whose elements belong in $X \subset \mathds{N}, X \neq \varnothing$,
-that is, $\mathcal{S}_X = \mathcal{X}^\mathds{N}$.
-Let $\mathsf{N} \in \mathds{N}^\ast$, $f:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$, and
-$\mathcal{P} \subset \mathds{N}^\ast$ a non empty and finite set of integers.
 
 
-Any couple $(u,v) \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$ defines
-a ``chaotic iterations based'' pseudorandom number generator, which is denoted by  $\textit{CIPRNG}_f^2(u,v)$~\cite{wbg10:ip}. It is 
-defined as follows:
-\begin{equation}
-\label{CIPRNGver2}
-\left\{
-\begin{array}{l}
- x^0 \in \mathds{B}^\mathsf{N}\\
- \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket, x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if  }~ i=u^n \\ x_i^n & \text{else} \end{array} \right.\\
- \forall n \in \mathds{N}, y^n = x^{v^n} .
-\end{array}
-\right.
-\end{equation}
-The outputted sequence produced by this generator is $\left(y^n\right)_{n \in \mathds{N}}$. 
-Remark that, given a sequence $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ called a ``chaotic strategy'',
-the following way to iterate: 
-$$x^0 \in \mathds{B}^\mathsf{N}, \forall n \in \mathds{N}, \forall i \in \llbracket 1, \mathsf{N} \rrbracket,  x_i^{n+1} = \left\{ \begin{array}{ll} f(x^n)_i & \text{if  }~ i=S^n \\ x_i^n & \text{else} \end{array} \right. ,$$
-is referred in the discrete mathematics literature as ``chaotic iterations''~\cite{Robert} (a terminology which has
-\emph{a priori} no relation with the mathematical theory of chaos recalled previously), which
-explains the name provided to these categories of pseudorandom number generators.
-
-
-The formerly proposed $\textit{CIPRNG}_f^1(u)$~\cite{bgw09:ip,guyeuxTaiwan10} is equal to \linebreak $\textit{CIPRNG}_f^2\left(u,\left(1\right)_{n\in \mathds{N}}\right)$, where $\left(1\right)_{n\in \mathds{N}}$ is the sequence that is 
-uniformly equal to 1. 
-It has been proven as chaotic for the vectorial Boolean negation $f_0:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$, 
-$(x_1, \hdots , x_\mathsf{N}) \longmapsto (\overline{x_1}, \hdots, \overline{x_\mathsf{N}})$ in \cite{bgw09:ip} 
-and for a larger set of well-chosen iteration functions in~\cite{bcgr11:ip} but,
-as only one bit is modified at each iteration, this generator is not able to pass any reasonable statistical tests.
-
-The $\textit{XOR~CIPRNG}(S)$, for its part~\cite{DBLP:journals/corr/abs-1112-5239}, is defined as follows: $x^0 \in \mathds{B}^\mathsf{N}$, and $\forall n \in \mathds{N}, x^{n+1} = x^n \oplus S^n$
-where $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$ and $\oplus$ stands for the bitwise \emph{exclusive or} (xor) operation
-between the binary decomposition of $x^n$ and $S^n$. This is indeed a $CIPRNG_{f_0}^2 (u,v)$ generator:
-%, for 
-%$u,v \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$: 
-for any given $S \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$, $v^n$ is the number
-of 1's in the binary decomposition of $S^n$ while $u^{v^n}, u^{v^n+1}, \hdots , u^{v^{n+1}-1}$
-are the positions of these ones.
-The $\textit{XOR~CIPRNG}$ has been proven chaotic and it is able to pass all the most stringent statistical 
-batteries of tests~\cite{DBLP:journals/corr/abs-1112-5239}, namely: DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, and TestU01~\cite{LEcuyerS07},
-which encompasses the two former ones. Furthermore, the output sequence is cryptographically secure
-when $S$ is cryptographically secure~\cite{DBLP:journals/corr/abs-1112-5239}.
-We are then left to prove $\textit{CIPRNG}_f^2(u,v)$ is chaotic.
-
-\subsection{The $\textit{CIPRNG}_f^2(u,v)$ is chaotic for well-chosen $f$}\label{sec:wellchosen}
-
-\subsubsection{The generator as a discrete dynamical system}
-
-
-Using notations of the previous section, consider a $\textit{CIPRNG}_f^2(u,v)$ generator $G$, with
-$\mathsf{N} \in \mathds{N}^\ast$, $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$,
-$u \in \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}$, and $v \in \mathcal{S}_\mathcal{P}$, with
-$\mathcal{P} \subset \mathds{N}$ a finite nonempty set having the cardinality 
-$\mathsf{p} \in \mathds{N}^\ast$.
-Denote by $p_1, p_2, \hdots, p_\mathsf{p}$ the ordered elements of $\mathcal{P}$: $\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$
-and $p_1< p_2< \hdots < p_\mathsf{p}$.
-Let 
-$$
-\begin{array}{cccc}
- F_f: & \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket & \longrightarrow & \mathds{B}^\mathsf{N}\\
-      & (e,i) & \longmapsto & (e_1, \hdots , e_{i-1}, f(e)_i, e_{i+1}, \hdots , e_{\mathsf{N}}) 
-\end{array}
-$$
-and
+The Algorithm~\ref{CI Algorithm} 
+may be seen as $b$ functional composition of $F_f$.
+However, it can be generalized with $p_i$, $p_i \in \mathcal{P}$,
+functional compositions of $F_f$.
+Thus, for any $p_i \in \mathcal{P}$ we introduce the function 
+$F_{f,p_i} :  \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^{p_i}  \rightarrow \mathds{B}^\mathsf{N}$ defined by 
+
 $$
 $$
-\begin{array}{cccc}
- F_{f,\mathsf{p}} : & \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^\mathsf{p} & \longrightarrow & \mathds{B}^\mathsf{N}\\
-      & (e,(u^0, u^1, \hdots, u^{\mathsf{p}-1})) & \longmapsto & F_f(\hdots (F_f(F_f(e,u^0), u^1), \hdots), u^{\mathsf{p}-1}) .
-\end{array}
+F_{f,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1}))  \mapsto 
+F_f(\hdots (F_f(F_f(x,u^0), u^1), \hdots), u^{p_i-1}).
 $$
 
 $$
 
-Denote by $\mathcal{X}_{\mathsf{N},\mathcal{P}}=  \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, where 
-$\mathds{S}_{\mathsf{N},\mathcal{P}}=\mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket}\times \mathcal{S}_\mathcal{P}$, 
-we define the shift operation on sequences as follows,
-$$\begin{array}{cccc}
-\sigma:&\mathcal{S}_{X} &\longrightarrow
-& \mathcal{S}_{X} \\
-& (u^k)_{k \in \mathds{N}} & \longmapsto & (u^{k+1})_{k \in \mathds{N}}, 
-\end{array}
-$$
-and let
+
+The considered space is 
+ $\mathcal{X}_{\mathsf{N},\mathcal{P}}=  \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, where 
+$\mathds{S}_{\mathsf{N},\mathcal{P}}=
+\llbracket 1, \mathsf{N} \rrbracket^{\Nats}\times 
+\mathcal{P}^{\Nats}$. 
+Each element in this space is a pair where the first element is 
+$\mathsf{N}$-uple in $\Bool^{\mathsf{N}}$, as in the previous space.  
+The second element is a pair $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats})$ of infinite sequences.
+The sequence $(v^k)_{k \in \Nats}$ defines how many iterations are executed at time $k$ between two outputs. 
+The sequence $(u^k)_{k \in \Nats}$ defines which elements is modified. 
+
+Let us define the shift function $\Sigma$ for any element of $\mathds{S}_{\mathsf{N},\mathcal{P}}$.
 $$\begin{array}{cccc}
 \Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow
 &\mathds{S}_{\mathsf{N},\mathcal{P}} \\
 $$\begin{array}{cccc}
 \Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow
 &\mathds{S}_{\mathsf{N},\mathcal{P}} \\
@@ -174,7 +207,7 @@ X^{n+1} = G_f(X^n)$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
 
 
 
 
 
 
-\subsubsection{A metric on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
+\subsection{A metric on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
 
 We define a distance $d$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ as follows. 
 Consider 
 
 We define a distance $d$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ as follows. 
 Consider 
@@ -203,7 +236,7 @@ part of $d(X,\check{X})$ is completed by 0's until reaching
 $p+n\times \max{(\mathcal{P})}$ digits.
 \item If $v^0<\check{v}^0$, then the $ \max{(\mathcal{P})}$  blocs of $n$
 digits are $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$,
 $p+n\times \max{(\mathcal{P})}$ digits.
 \item If $v^0<\check{v}^0$, then the $ \max{(\mathcal{P})}$  blocs of $n$
 digits are $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$,
-$\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digits), followed by O's if required.
+$\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digits), followed by 0's if required.
 \item The case $v^0>\check{v}^0$ is dealt similarly.
 \end{itemize}
 \item The next $p$ digits are $|v^1-\check{v}^1|$, etc.
 \item The case $v^0>\check{v}^0$ is dealt similarly.
 \end{itemize}
 \item The next $p$ digits are $|v^1-\check{v}^1|$, etc.
@@ -220,14 +253,14 @@ $s=\left\{
 u=\underline{6,} ~ \underline{11,5}, ...\\
 v=1,2,...
 \end{array}
 u=\underline{6,} ~ \underline{11,5}, ...\\
 v=1,2,...
 \end{array}
-\right.$\\
+\right.$
 while
 $\check{s}=\left\{
 \begin{array}{l}
 \check{u}=\underline{6,4} ~ \underline{1}, ...\\
 \check{v}=2,1,...
 \end{array}
 while
 $\check{s}=\left\{
 \begin{array}{l}
 \check{u}=\underline{6,4} ~ \underline{1}, ...\\
 \check{v}=2,1,...
 \end{array}
-\right.$
+\right.$.
 
 So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$
 Indeed, the $p=2$ first digits are 01, as $|v^0-\check{v}^0|=1$, 
 
 So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$
 Indeed, the $p=2$ first digits are 01, as $|v^0-\check{v}^0|=1$, 
@@ -250,7 +283,7 @@ $s=\left\{
 u=\underline{6,7,} ~ \underline{4,2,} ...\\
 v=2,2,...
 \end{array}
 u=\underline{6,7,} ~ \underline{4,2,} ...\\
 v=2,2,...
 \end{array}
-\right.$\\
+\right.$
 while
 $\check{s}=\left\{
 \begin{array}{l}
 while
 $\check{s}=\left\{
 \begin{array}{l}
@@ -286,7 +319,7 @@ $$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \su
 
 Let us show that,
 \begin{proposition}
 
 Let us show that,
 \begin{proposition}
-$d$ is a distance on $\mathcal{X}$.
+$d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
 \end{proposition}
 
 
 \end{proposition}
 
 
@@ -344,50 +377,71 @@ $G_f(x^n)_2$ is convergent to $G_f(x)_2$.
 \end{itemize}
 \end{proof}
 
 \end{itemize}
 \end{proof}
 
-\begin{figure}[h]
-\centering
-\includegraphics[scale=0.85]{graphe1.pdf}
-\caption{Chaotic iterations of $f_0$, defining the $CIPRNG_{f_0}^1$ ($\mathsf{N}=2$)}
-\label{graphe1}
-\end{figure}
 
 
-\subsubsection{The $\textit{CIPRNG}_f^2(u,v)$ as iterations on a graph}
 
 
-We define the directed graph $\mathcal{G}_{f,\mathcal{P}}$ as follows.
+\subsection{$\Gamma_{\mathcal{P}}(f)$ as an extension of  $\Gamma(f)$}
+
+Let $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$.
+We define the directed graph $\Gamma_{\mathcal{P}}(f)$ as follows.
 \begin{itemize}
 \item Its vertices are the $2^\mathsf{N}$ elements of $\mathds{B}^\mathsf{N}$.
 \item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples 
 \begin{itemize}
 \item Its vertices are the $2^\mathsf{N}$ elements of $\mathds{B}^\mathsf{N}$.
 \item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples 
-having their elements in $\llbracket 1, \mathsf{N} \rrbracket $.
-\item There is an arc labeled $a_1, \hdots, a_{p_i}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ between vertices $x$ and $y$ if and only if $y=F_{f,p_i} (x, (a_1, \hdots, a_{p_i})) $.
+  having their elements in $\llbracket 1, \mathsf{N} \rrbracket $.
+\item There is an arc labeled $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ between vertices $x$ and $y$ if and only if 
+$y=F_{f,p_i} (x, (u_0, \hdots, u_{p_i-1})) $.
 \end{itemize}
 
 \end{itemize}
 
-
-\begin{figure}[h]
-\centering
-\includegraphics[scale=0.85]{graphe2.pdf}
-\caption{Iteration graph of $CIPRNG_{f_0}^2$, $\mathcal{P}=\{2,3\}$, $\mathsf{N}=2$}
-\label{graphe2}
+It is not hard to see that the graph $\Gamma_{\{1\}}(f)$ is 
+$\Gamma(f)$.
+
+\begin{figure}[ht]
+  \centering
+  \begin{subfigure}[b]{0.45\textwidth}
+    \centering
+    \includegraphics[scale=0.85]{graphe1.pdf}
+    \caption{$\Gamma(f_0)$}
+    \label{graphe1}
+  \end{subfigure}%
+  ~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc.
+  % (or a blank line to force the subfigure onto a new line)
+  \begin{subfigure}[b]{0.3\textwidth}
+    \centering  
+    \includegraphics[scale=0.85]{graphe2.pdf}
+    \caption{$\Gamma_{\{2,3\}}(f_0)$}
+    \label{graphe2}
+  \end{subfigure}
+  ~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc.
+  \caption{Iterating $f_0:(x_1,x_2) \mapsto (\overline{x_1}, \overline{x_2})$}
+  \label{fig:itg}
 \end{figure}
 
 \end{figure}
 
+
 \begin{xpl}
 \begin{xpl}
-Consider for instance $\mathsf{N}=2$, $f_0:\mathds{B}^2 \longrightarrow \mathds{B}^2, (x_1,x_2) \longmapsto (\overline{x_1}, \overline{x_2})$, and
-$\mathcal{P}=\{2,3\}$. Chaotic iterations of $f_0$ are given in Figure~\ref{graphe1} while the digraph  $\mathcal{G}_{f_0,\{2,3\}}$ is depicted in
-Figure~\ref{graphe2}. Notice that here, orientations of arcs are not necessary 
-since the function $f$ is equal to its inverse $f^{-1}$. 
+Consider for instance $\mathsf{N}=2$, 
+Let $f_0:\mathds{B}^2 \longrightarrow \mathds{B}^2$ be the negation function,
+\textit{i.e.}, $f_0(x_1,x_2) = (\overline{x_1}, \overline{x_2})$, and consider
+$\mathcal{P}=\{2,3\}$. The graphs of iterations are given in 
+\textsc{Figure~\ref{fig:itg}}.
+The \textsc{Figure~\ref{graphe1}} shows what happens when 
+displaying each iteration result.
+On the contrary, the \textsc{Figure~\ref{graphe2}} explicits the behaviors
+when always applying 2 or 3 modification and next outputing results. 
+Notice that here, orientations of arcs are not necessary 
+since the function $f_0$ is equal to its inverse $f_0^{-1}$. 
 \end{xpl}
 
 \end{xpl}
 
-\subsubsection{Proofs of chaos}
+\subsection{Proofs of chaos}
 
 We will show that,
 \begin{proposition}
 \label{prop:trans}
 
 We will show that,
 \begin{proposition}
 \label{prop:trans}
- $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected if and only if $G_f$ is 
+ $\Gamma_{\mathcal{P}}(f)$ is strongly connected if and only if $G_f$ is 
 topologically transitive on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
 \end{proposition}
 
 
 \begin{proof}
 topologically transitive on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
 \end{proposition}
 
 
 \begin{proof}
-Suppose that $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected. 
+Suppose that $\Gamma_{\mathcal{P}}(f)$ is strongly connected. 
 Let $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v})) 
 \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$.
 We will find a point $y$ in the open ball $\mathcal{B}(x,\varepsilon )$ and
 Let $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v})) 
 \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$.
 We will find a point $y$ in the open ball $\mathcal{B}(x,\varepsilon )$ and
@@ -407,7 +461,7 @@ Then $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))<\varepsilon$.
 In other words, any $y$ of the form $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}),
 (v^0, ..., v^{k_1}))$ is in $\mathcal{B}(x,\varepsilon)$.
 
 In other words, any $y$ of the form $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}),
 (v^0, ..., v^{k_1}))$ is in $\mathcal{B}(x,\varepsilon)$.
 
-Let $y^0$ such a point and $z=G_f^{k_1}(y^0) = (e',(u',v'))$. $\mathcal{G}_{f,\mathcal{P}}$
+Let $y^0$ such a point and $z=G_f^{k_1}(y^0) = (e',(u',v'))$. $\Gamma_{\mathcal{P}}(f)$
 being strongly connected, there is a path between $e'$ and $\check{e}$. Denote
 by $a_0, \hdots, a_{k_2}$ the edges visited by this path. We denote by
 $V^{k_1}=|a_0|$ (number of terms in the finite sequence $a_1$),
 being strongly connected, there is a path between $e'$ and $\check{e}$. Denote
 by $a_0, \hdots, a_{k_2}$ the edges visited by this path. We denote by
 $V^{k_1}=|a_0|$ (number of terms in the finite sequence $a_1$),
@@ -422,7 +476,7 @@ Let $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0,
  and $G_{f}^{k_1+k_2}(y)=\check{x}$.
  
  
  and $G_{f}^{k_1+k_2}(y)=\check{x}$.
  
  
-Conversely, if $\mathcal{G}_{f,\mathcal{P}}$ is not strongly connected, then there are 
+Conversely, if $\Gamma_{\mathcal{P}}(f)$ is not strongly connected, then there are 
 2 vertices $e_1$ and $e_2$ such that there is no path between $e_1$ and $e_2$.
 That is, it is impossible to find $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$
 and $n \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$
 2 vertices $e_1$ and $e_2$ such that there is no path between $e_1$ and $e_2$.
 That is, it is impossible to find $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$
 and $n \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$
@@ -432,7 +486,7 @@ cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transiti
 
 We show now that,
 \begin{proposition}
 
 We show now that,
 \begin{proposition}
-If $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected, then $G_f$ is 
+If $\Gamma_{\mathcal{P}}(f)$ is strongly connected, then $G_f$ is 
 regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
 \end{proposition}
 
 regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
 \end{proposition}
 
@@ -443,7 +497,7 @@ that
 $$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \mid \right.$$
 $$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\}
 \subset \mathcal{B}(x,\varepsilon),$$
 $$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \mid \right.$$
 $$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\}
 \subset \mathcal{B}(x,\varepsilon),$$
-and $y=G_f^{k_1}(e,(u,v))$. $\mathcal{G}_{f,\mathcal{P}}$ being strongly connected,
+and $y=G_f^{k_1}(e,(u,v))$. $\Gamma_{\mathcal{P}}(f)$ being strongly connected,
 there is at least a path from the Boolean state $y_1$ of $y$ and $e$.
 Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path.
 Then the point:
 there is at least a path from the Boolean state $y_1$ of $y$ and $e$.
 Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path.
 Then the point:
@@ -455,7 +509,18 @@ is a periodic point in the neighborhood $\mathcal{B}(x,\varepsilon)$ of $x$.
 
 $G_f$ being topologically transitive and regular, we can thus conclude that
 \begin{Theo}
 
 $G_f$ being topologically transitive and regular, we can thus conclude that
 \begin{Theo}
-The pseudorandom number generator $\textit{CIPRNG}_f^2$ denoted by $G_f$ in
-this section is chaotic on $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ if
-and only if its graph $\mathcal{G}_{f,\mathcal{P}}$ is strongly connected.
+The function $G_f$ is chaotic on $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ if
+and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is strongly connected.
 \end{Theo}
 \end{Theo}
+
+\begin{Corollary}
+  The pseudorandom number generator $\chi_{\textit{14Secrypt}}$ is not chaotic
+  on $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ for the negation function.
+\end{Corollary}
+\begin{proof}
+  In this context, $\mathcal{P}$ is the singleton $\{b\}$.
+  If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach 
+  its neighborhood and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected. 
+  If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach itself 
+  and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected.
+\end{proof}
index 646041279c11725486107a867ef7cc7f1b755160..097d51461c3e7f0dde2a3da75eb55447fc6c29d6 100644 (file)
--- a/intro.tex
+++ b/intro.tex
@@ -1,65 +1,65 @@
-L'exploitation de  \og systèmes chaotiques\fg{} pour générer des séquences
-pseudo-aléatoires est un sujet actif de recherche~\cite{915396,915385,5376454}. 
-Ces systèmes sont choisis principalement
-en raison de leur imprévisibilité et de leur sensibilité aux conditions initiales.
+L'exploitation de  \og systèmes chaotiques\fg{} pour générer des séquences
+pseudo-aléatoires est un sujet actif de recherche~\cite{915396,915385,5376454}. 
+Ces systèmes sont choisis principalement
+en raison de leur imprévisibilité et de leur sensibilité aux conditions initiales.
 
 
-Souvent   les   travaux  se   limitent   à   itérer   une  fonction   paramétrée
+Souvent   les   travaux  se   limitent   à   itérer   une  fonction   paramétrée
 \emph{chaotique}  comme la  fonction logistique~\cite{915396,915385},  ou encore
 \emph{chaotique}  comme la  fonction logistique~\cite{915396,915385},  ou encore
-celle du  chat d'Arnold~\cite{5376454}\ldots Il  reste à trouver  les paramètres
-optimaux permettant d'éviter les attracteurs de telles fonctions et garantissant
-que les séquences de nombres  produits suivent une loi de distribution uniforme.
-Pour vérifier  la qualité des  sorties produites il  est usuel de  soumettre les
-PRNG   (Pseudo-Random  Number   Generator)   à  des   tests  statistiques   tels
+celle du  chat d'Arnold~\cite{5376454}\ldots Il  reste à trouver  les paramètres
+optimaux permettant d'éviter les attracteurs de telles fonctions et garantissant
+que les séquences de nombres  produits suivent une loi de distribution uniforme.
+Pour vérifier  la qualité des  sorties produites il  est usuel de  soumettre les
+PRNG   (Pseudo-Random  Number   Generator)   à  des   tests  statistiques   tels
 DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10} et TestU01~\cite{LEcuyerS07}.
 
 DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10} et TestU01~\cite{LEcuyerS07}.
 
-Dans son acception vulgarisée, 
-la notion de chaos est souvent réduite à celle de forte sensibilité
+Dans son acception vulgarisée, 
+la notion de chaos est souvent réduite à celle de forte sensibilité
 aux conditions initiales (le fameux \og \emph{effet papillon}\fg{}): 
 aux conditions initiales (le fameux \og \emph{effet papillon}\fg{}): 
-une fonction continue $k$ définie sur un espace métrique 
+une fonction continue $k$ définie sur un espace métrique 
 est dite \emph{fortement sensible aux conditions initiales} si pour tout
 point $x$ et pour toute valeur positive $\epsilon$
 il est possible de trouver un point $y$, arbitrairement proche 
 de $x$, et un entier $t$ tels que la distance entre les 
 est dite \emph{fortement sensible aux conditions initiales} si pour tout
 point $x$ et pour toute valeur positive $\epsilon$
 il est possible de trouver un point $y$, arbitrairement proche 
 de $x$, et un entier $t$ tels que la distance entre les 
-$t^{\textrm{ièmes}}$ itérés de $x$ et de $y$ 
--- notés $k^t(x)$ et $k^t(y)$ 
--- est supérieure à $\epsilon$. 
-Cependant, dans sa définition du chaos, 
-Devaney~\cite{Devaney} impose à la fonction chaotique deux autres propriété
-appelées \emph{transitivité} et \emph{régularité},
-Les fonctions citées plus haut ont été étudiées 
-au regard de ces propriétés et ont été prouvées comme chaotiques sur $\R$.
-Cependant, rien ne garantit que ces propriétés sont préservées sur les nombres 
-flottants qui est le domaine d'interprétation des nombres réels de $\R$.
-
-Pour éviter cette perte de chaos,  nous avons présenté des PRNGs qui itèrent des
+$t^{\textrm{ièmes}}$ itérés de $x$ et de $y$ 
+-- notés $k^t(x)$ et $k^t(y)$ 
+-- est supérieure à $\epsilon$. 
+Cependant, dans sa définition du chaos, 
+Devaney~\cite{Devaney} impose à la fonction chaotique deux autres propriété
+appelées \emph{transitivité} et \emph{régularité},
+Les fonctions citées plus haut ont été étudiées 
+au regard de ces propriétés et ont été prouvées comme chaotiques sur $\R$.
+Cependant, rien ne garantit que ces propriétés sont préservées sur les nombres 
+flottants qui est le domaine d'interprétation des nombres réels de $\R$.
+
+Pour éviter cette perte de chaos,  nous avons présenté des PRNGs qui itèrent des
 fonctions continues  $G_f$ sur  un domaine discret  $\{ 1, \ldots,  n \}^{\Nats}
 fonctions continues  $G_f$ sur  un domaine discret  $\{ 1, \ldots,  n \}^{\Nats}
-\times  \{0,1\}^n$  où $f$  est  une  fonction  booléenne (\textit{i.e.},  $f  :
-\{0,1\}^n      \rightarrow      \{0,1\}^n$).       Ces     générateurs      sont
-$\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11ip},
+\times  \{0,1\}^n$  où $f$  est  une  fonction  booléenne (\textit{i.e.},  $f  :
+\{0,1\}^n      \rightarrow      \{0,1\}^n$).       Ces     générateurs      sont
+$\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11:ip},
 $\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip}                                     et
 $\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip}                                     et
-$\chi_{\textit{14Secrypt}}$ \cite{chgw14oip}     où    \textit{CI}    signifie
+$\chi_{\textit{14Secrypt}}$ \cite{chgw14oip}     où    \textit{CI}    signifie
 \emph{Chaotic Iterations}.
 
 \emph{Chaotic Iterations}.
 
-Dans~\cite{bcgr11ip} nous avons tout d'abord  prouvé que pour établir la nature
-chaotique de l'algorithme $\textit{CIPRNG}_f^1$,  il est nécessaire et suffisant
-que le  graphe des  itérations asynchrones soit  fortement connexe.   Nous avons
-ensuite  prouvé que  pour  que la  sortie de  cet  algorithme suive  une loi  de
-distribution uniforme, il  est nécessaire et suffisant que  la matrice de Markov
-associée à ce graphe soit  doublement stochastique.  Nous avons enfin établi des
-conditions suffisantes pour garantir  la première propriété de connexité.  Parmi
-les  fonctions générées,  on ne  retenait ensuite  que celles  qui  vérifiait la
-seconde  propriété.  Dans~\cite{chgw14oip},  nous avons  proposé  une démarche
-algorithmique permettant d'obtenir  directement un graphe d'itérations fortement
+Dans~\cite{bcgr11:ip} nous avons tout d'abord  prouvé que pour établir la nature
+chaotique de l'algorithme $\textit{CIPRNG}_f^1$,  il est nécessaire et suffisant
+que le  graphe des  itérations asynchrones soit  fortement connexe.   Nous avons
+ensuite  prouvé que  pour  que la  sortie de  cet  algorithme suive  une loi  de
+distribution uniforme, il  est nécessaire et suffisant que  la matrice de Markov
+associée à ce graphe soit  doublement stochastique.  Nous avons enfin établi des
+conditions suffisantes pour garantir  la première propriété de connexité.  Parmi
+les  fonctions générées,  on ne  retenait ensuite  que celles  qui  vérifiait la
+seconde  propriété.  Dans~\cite{chgw14oip},  nous avons  proposé  une démarche
+algorithmique permettant d'obtenir  directement un graphe d'itérations fortement
 connexe et  dont la matrice de  Markov est doublement  stochastique.  Le travail
 connexe et  dont la matrice de  Markov est doublement  stochastique.  Le travail
-présenté ici généralise ce dernier  article en changeant le domaine d'itération,
-et donc de métrique. L'algorithme  obtenu possède les même propriétés théoriques
-mais un temps de mélange plus réduit.
+présenté ici généralise ce dernier  article en changeant le domaine d'itération,
+et donc de métrique. L'algorithme  obtenu possède les même propriétés théoriques
+mais un temps de mélange plus réduit.
 
 
-% Pour décrire un peu plus précisément le principe de
-% la génération pseudo-aléatoire, considérons l'espace booléen 
+% Pour décrire un peu plus précisément le principe de
+% la génération pseudo-aléatoire, considérons l'espace booléen 
 % $\Bool=\{0,1\}$
 % muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\bullet}$ \fg{} 
 % $\Bool=\{0,1\}$
 % muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\bullet}$ \fg{} 
-% définies par les tableaux ci-dessous:
+% définies par les tableaux ci-dessous:
 
 % \begin{center}
 %   \begin{tabular}{|c|c|c|}
 
 % \begin{center}
 %   \begin{tabular}{|c|c|c|}
@@ -90,64 +90,64 @@ mais un temps de m
 % \end{center}
 
 
 % \end{center}
 
 
-% La fonction itérée est
-% une fonction $f$ de $\Bool^n$ dans lui-même qui à
+% La fonction itérée est
+% une fonction $f$ de $\Bool^n$ dans lui-même qui à
 % un mot binaire $x = (x_1,\ldots,x_n)$ 
 % associe le mot $(f_1(x),\ldots, f_n(x))$.
 % un mot binaire $x = (x_1,\ldots,x_n)$ 
 % associe le mot $(f_1(x),\ldots, f_n(x))$.
-% Un exemple de fonction de $\Bool^n$ dans lui-même
-% est la fonction négation 
-% définie par  
+% Un exemple de fonction de $\Bool^n$ dans lui-même
+% est la fonction négation 
+% définie par  
 % $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. 
 
 % $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. 
 
-% Le principe itératif, basé sur  le mode opératoire dit \emph{asynchrone}, est le
-% suivant: à chaque itération  $t$, on choisit un indice $i$ entre  $1$ et $n$, et
-% le mot $x^t = (x_1^t,\ldots,x_n^t)$  est remplacé par $x^{t+1} = (x_1^t,\ldots ,
+% Le principe itératif, basé sur  le mode opératoire dit \emph{asynchrone}, est le
+% suivant: à chaque itération  $t$, on choisit un indice $i$ entre  $1$ et $n$, et
+% le mot $x^t = (x_1^t,\ldots,x_n^t)$  est remplacé par $x^{t+1} = (x_1^t,\ldots ,
 % x_{i-1}^t, f_i(x^t), x_{i+1}^t,\ldots, x_n^t)$.
 
 % x_{i-1}^t, f_i(x^t), x_{i+1}^t,\ldots, x_n^t)$.
 
-% Au  bout d'un  nombre $N$  d'itérations,  si la  fonction (notée  $G_f$ dans  ce
-% document)  que l'on  peut  associer à  l'algorithme  décrit ci-dessus  a de  \og
-% \emph{bonnes}\fg{} propriétés chaotiques, le  mot $x^N$ doit être \og \emph{très
-%   différent}\fg{} de  $x^0$ de  façon à  sembler ne plus  dépendre de  $x_0$. En
-% effet, pour  un générateur aléatoire, il  faut que la structure  de $x^N$ semble
-% être due  au hasard;  pour une application  cryptographique, il faut  qu'il soit
-% matériellement  impossible   (dans  les  conditions   techniques  actuelles)  de
-% retrouver $x^0$ à partir de $x^N$.
+% Au  bout d'un  nombre $N$  d'itérations,  si la  fonction (notée  $G_f$ dans  ce
+% document)  que l'on  peut  associer à  l'algorithme  décrit ci-dessus  a de  \og
+% \emph{bonnes}\fg{} propriétés chaotiques, le  mot $x^N$ doit être \og \emph{très
+%   différent}\fg{} de  $x^0$ de  façon à  sembler ne plus  dépendre de  $x_0$. En
+% effet, pour  un générateur aléatoire, il  faut que la structure  de $x^N$ semble
+% être due  au hasard;  pour une application  cryptographique, il faut  qu'il soit
+% matériellement  impossible   (dans  les  conditions   techniques  actuelles)  de
+% retrouver $x^0$ à partir de $x^N$.
 
 % Tous  les  mots   de  $\Bool^n$  peuvent  constituer  les   $2^n$  sommets  d'un
 % \gls{graphoriente} (cf. glossaire) dans lequel  un arc relie deux sommets $x$ et
 
 % Tous  les  mots   de  $\Bool^n$  peuvent  constituer  les   $2^n$  sommets  d'un
 % \gls{graphoriente} (cf. glossaire) dans lequel  un arc relie deux sommets $x$ et
-% $x'$  s'il existe  une itération  de l'algorithme  de génération  qui  permet de
-% passer directement de  $x$ à $x'$.   Ce graphe est  appelé le \emph{graphe  d'itérations} et
+% $x'$  s'il existe  une itération  de l'algorithme  de génération  qui  permet de
+% passer directement de  $x$ à $x'$.   Ce graphe est  appelé le \emph{graphe  d'itérations} et
 % nous montrons ici que si  l'on a un \gls{graphfortementconnexe} (cf. glossaire),
 % alors la fonction $G_f$ est transitive, donc chaotique.
 
 % nous montrons ici que si  l'on a un \gls{graphfortementconnexe} (cf. glossaire),
 % alors la fonction $G_f$ est transitive, donc chaotique.
 
-% Enfin, un bon générateur aléatoire se doit de 
+% Enfin, un bon générateur aléatoire se doit de 
 % fournir  des nombres selon une \gls{distributionuniforme} (cf. glossaire). 
 % fournir  des nombres selon une \gls{distributionuniforme} (cf. glossaire). 
-% La dernière partie de cet article donne, 
-% dans le cas où le graphe d'itérations est fortement connexe, 
-% une condition nécessaire et suffisante pour que
-% cette propriété soit satisfaite.
+% La dernière partie de cet article donne, 
+% dans le cas où le graphe d'itérations est fortement connexe, 
+% une condition nécessaire et suffisante pour que
+% cette propriété soit satisfaite.
 
 
 
 
-% Le chaos a été appliqué à des domaines variés en 
+% Le chaos a été appliqué à des domaines variés en 
 % informatique, comme les fonctions de hachage,
 % informatique, comme les fonctions de hachage,
-% la stéganographie, la génération de nombres pseudo 
-% aléatoires\ldots
-% Toutes ces  applications  exploitent les  propriétés définissant des 
-% fonctions  chaotiques et énoncées par Devaney,  telles que la
-% transitivité, la régularité et la sensibilité aux conditions initiales.
-
-
-% Les systèmes dynamiques \emph{chaotiques} sont des processus itératifs 
-% définis par une fonction chaotique  $f$  d'un  domaine $E$ dans lui-même.
-% En démarrant d'un état quelconque $x$ du sytème, 
-% nommé par la suite \emph{configuration}, 
-% le système construit la séquence $x$, $f(x)$, $f^2(x)$, $f^3(x)$, \dots 
-% où $f^k(x)$  est le   $k^{\textrm{ème}}$ itéré  de  $f$ en  $x$.  
+% la stéganographie, la génération de nombres pseudo 
+% aléatoires\ldots
+% Toutes ces  applications  exploitent les  propriétés définissant des 
+% fonctions  chaotiques et énoncées par Devaney,  telles que la
+% transitivité, la régularité et la sensibilité aux conditions initiales.
+
+
+% Les systèmes dynamiques \emph{chaotiques} sont des processus itératifs 
+% définis par une fonction chaotique  $f$  d'un  domaine $E$ dans lui-même.
+% En démarrant d'un état quelconque $x$ du sytème, 
+% nommé par la suite \emph{configuration}, 
+% le système construit la séquence $x$, $f(x)$, $f^2(x)$, $f^3(x)$, \dots 
+% où $f^k(x)$  est le   $k^{\textrm{ème}}$ itéré  de  $f$ en  $x$.  
 % La plupart des applications informatiques dite \og chaotiques \fg{}
 % La plupart des applications informatiques dite \og chaotiques \fg{}
-% sont basées sur des processus itératifs de la forme $x^{n+1} = f(x^n)$
-% où $f$ est la fonction  \emph{tente} avec  $x^0 = 0,4001$ (donnée à la figure~\ref{fig:iter:tent}) 
-% ou la fonction  \emph{logistique} avec $\mu = 3,45$ et $x^0 = 0,1$ (donnée à la figure~\ref{fig:iter:log}) 
-% connues pour être chaotiques dans $\R$.
+% sont basées sur des processus itératifs de la forme $x^{n+1} = f(x^n)$
+% où $f$ est la fonction  \emph{tente} avec  $x^0 = 0,4001$ (donnée à la figure~\ref{fig:iter:tent}) 
+% ou la fonction  \emph{logistique} avec $\mu = 3,45$ et $x^0 = 0,1$ (donnée à la figure~\ref{fig:iter:log}) 
+% connues pour être chaotiques dans $\R$.
 
 % \begin{figure}[hb]
 % \begin{center}
 
 % \begin{figure}[hb]
 % \begin{center}
@@ -168,80 +168,80 @@ mais un temps de m
 %       \label{fig:iter:log}
 %     }
 % \end{center}
 %       \label{fig:iter:log}
 %     }
 % \end{center}
-%  \caption{Systèmes itératifs basés sur des fonctions chaotiques dans $\R$ \label{fig:iter}}
+%  \caption{Systèmes itératifs basés sur des fonctions chaotiques dans $\R$ \label{fig:iter}}
 % \end{figure}
 
 
 % \end{figure}
 
 
-% Cependant il n'a pas été établi que des fonctions prouvées
-% comme étant chaotiques sur $\R$ le restent sur les  nombres à virgule flottante,
-% qui est le domaine d'interprétation informatique des réels.  
-% On souhaite ainsi éviter une éventuelle perte des propriétés de chaos
-% lors de l'exécution des programmes implémentant ces fonctions. 
-% Ce document présente pour cela l'alternative suivante: 
-% à partir d'une fonction booléenne, $f: \Bool^n \rightarrow \Bool^n$, 
-% où $\Bool$ est le domaine des booléens  $\{0,1\}$, on
+% Cependant il n'a pas été établi que des fonctions prouvées
+% comme étant chaotiques sur $\R$ le restent sur les  nombres à virgule flottante,
+% qui est le domaine d'interprétation informatique des réels.  
+% On souhaite ainsi éviter une éventuelle perte des propriétés de chaos
+% lors de l'exécution des programmes implémentant ces fonctions. 
+% Ce document présente pour cela l'alternative suivante: 
+% à partir d'une fonction booléenne, $f: \Bool^n \rightarrow \Bool^n$, 
+% où $\Bool$ est le domaine des booléens  $\{0,1\}$, on
 % construit une fonction $G_f : \llbracket 1 ;  n \rrbracket^{\Nats}  \times \Bool^n$, 
 % construit une fonction $G_f : \llbracket 1 ;  n \rrbracket^{\Nats}  \times \Bool^n$, 
-% où $\llbracket 1  ; n \rrbracket$ est l'ensemble des entiers
-% $\{1, 2, \hdots,  n\}$ et on itère celle-ci.
-% Comme $f$ est discrète, $G_f$ l'est aussi et les résultats théoriques
-% obtenus sur $G_f$, notamment sa chaoticité, sont maintenus durant 
-% l'implémentation.
-% Un exemple de fonction booléenne de $\Bool^n$ dans lui-même est la fonction négation 
-% définie par  
+% où $\llbracket 1  ; n \rrbracket$ est l'ensemble des entiers
+% $\{1, 2, \hdots,  n\}$ et on itère celle-ci.
+% Comme $f$ est discrète, $G_f$ l'est aussi et les résultats théoriques
+% obtenus sur $G_f$, notamment sa chaoticité, sont maintenus durant 
+% l'implémentation.
+% Un exemple de fonction booléenne de $\Bool^n$ dans lui-même est la fonction négation 
+% définie par  
 % $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. 
 
 
 
 
 % $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. 
 
 
 
 
-% De plus,  plutôt que de trouver des exemples de telles fonctions $f$, et de prouver 
-% (\textit{a  posteriori}) la chaoticité de $G_f$, on peut penser à caractériser  
-% les fonctions engendrant systématiquement des fonctions chaotiques.
-% Ce document présente une telle caractérisation 
-% qui s'exprime sur le graphe des itérations asynchrones
-% de la fonction booléenne $f$, qui est, intuitivement, le graphe 
-% de toutes les itérations possibles de la fonction. 
-% Cette situation se réduit en un problème portant sur des graphes à $2^n$  
+% De plus,  plutôt que de trouver des exemples de telles fonctions $f$, et de prouver 
+% (\textit{a  posteriori}) la chaoticité de $G_f$, on peut penser à caractériser  
+% les fonctions engendrant systématiquement des fonctions chaotiques.
+% Ce document présente une telle caractérisation 
+% qui s'exprime sur le graphe des itérations asynchrones
+% de la fonction booléenne $f$, qui est, intuitivement, le graphe 
+% de toutes les itérations possibles de la fonction. 
+% Cette situation se réduit en un problème portant sur des graphes à $2^n$  
 % sommets.  
 % sommets.  
-% Ainsi pour étendre l'applicabilité de cette caractérisation, on s'intéresse
+% Ainsi pour étendre l'applicabilité de cette caractérisation, on s'intéresse
 % au graphe des interactions de $f$, qui, intuitivement,
 % au graphe des interactions de $f$, qui, intuitivement,
-% représente les dépendances entre les $f_i$, $1\le i \le n$ et les $i$
-% et qui ne contient que  $n$ sommets (et qui est à comparer aux $2^n$ 
+% représente les dépendances entre les $f_i$, $1\le i \le n$ et les $i$
+% et qui ne contient que  $n$ sommets (et qui est à comparer aux $2^n$ 
 % sommets.
 % sommets.
-% Sur ce graphe on exprime des conditions garantissant la chaoticité de la fonction $G_f$.
-% Ainsi, toutes les fonctions $G_f$ engendrées à partir d'un graphe
-% d'interactions de $f$ aux propriétés \textit{ad hoc} seront chaotiques.
+% Sur ce graphe on exprime des conditions garantissant la chaoticité de la fonction $G_f$.
+% Ainsi, toutes les fonctions $G_f$ engendrées à partir d'un graphe
+% d'interactions de $f$ aux propriétés \textit{ad hoc} seront chaotiques.
 
 
-% Se pose enfin l'applicabilité des fonctions $G_f$ à la génération
-% de nombres pseudo aléatoires, l'aléa étant intuitivement 
+% Se pose enfin l'applicabilité des fonctions $G_f$ à la génération
+% de nombres pseudo aléatoires, l'aléa étant intuitivement 
 % une notion proche de celle du chaos.
 % une notion proche de celle du chaos.
-% Pour aborder cette classe de problèmes, on remarque que l'on doit au moins 
-% garantir que l'ensemble des valeurs retournées par l'algorithme suit
-% une loi uniforme, propriété qui n'est pas imposée d'un point de vue topologique.
-% Ce document montre que cette contrainte peut s'exprimer à nouveau sur le graphe des itérations asynchrones de $f$
-% et qu'on peut ainsi filtrer les bons candidats à la génération de nombres pseudo aléatoires.
-% Cette idée est validée après évaluation 
-% des générateurs de nombres pseudo aléatoires 
+% Pour aborder cette classe de problèmes, on remarque que l'on doit au moins 
+% garantir que l'ensemble des valeurs retournées par l'algorithme suit
+% une loi uniforme, propriété qui n'est pas imposée d'un point de vue topologique.
+% Ce document montre que cette contrainte peut s'exprimer à nouveau sur le graphe des itérations asynchrones de $f$
+% et qu'on peut ainsi filtrer les bons candidats à la génération de nombres pseudo aléatoires.
+% Cette idée est validée après évaluation 
+% des générateurs de nombres pseudo aléatoires 
 % sur une batterie de tests.
 
 
 % sur une batterie de tests.
 
 
-% Le reste de ce document est organisé comme suit. 
-% La section~\ref{section:chaos} présente ce qu'est un système dynamique discret booléen itérant une fonction $f$.
-% La chaoticité de la fonction engendrée $G_f$ est caractérisée en 
+% Le reste de ce document est organisé comme suit. 
+% La section~\ref{section:chaos} présente ce qu'est un système dynamique discret booléen itérant une fonction $f$.
+% La chaoticité de la fonction engendrée $G_f$ est caractérisée en 
 % section~\ref{sec:charac}. 
 % section~\ref{sec:charac}. 
-% Des conditions suffisantes pour obtenir cette chaoticité sont présentées  en
+% Des conditions suffisantes pour obtenir cette chaoticité sont présentées  en
 % section~\ref{sec:sccg}.
 % section~\ref{sec:sccg}.
-% L'application à la génération de nombres pseudo aléatoires est formalisée,
-% les fonctions dont l'image est uniformément distribuée sur le domaine sont
-% caractérisées et les générateurs sont évalués en section~\ref{sec:prng}.
-
-Dans  la section  suivante,  nous  rappelons les  notions  élémentaires sur  les
-systèmes   booléens.   La  section~\ref{section:caracterisation}   présente  les
-définitions théoriques liées au chaos. Ensuite, une application de ces résultats
-à    la   génération    de   nombres    pseudo-aléatoires   est    proposée   en
-section~\ref{section:genpa}  ainsi  qu'une   méthode  permettant  d'obtenir  des
-matrices         d'itérations         doublement        stochastiques         en
-section~\ref{section:genmat}.  Enfin, en section~\ref{section:expes}  la qualité
-du PRNG obtenu est éprouvée avec les tests standards du domaine.
+% L'application à la génération de nombres pseudo aléatoires est formalisée,
+% les fonctions dont l'image est uniformément distribuée sur le domaine sont
+% caractérisées et les générateurs sont évalués en section~\ref{sec:prng}.
+
+Dans  la section  suivante,  nous  rappelons les  notions  élémentaires sur  les
+systèmes   booléens.   La  section~\ref{section:caracterisation}   présente  les
+définitions théoriques liées au chaos. Ensuite, une application de ces résultats
+à    la   génération    de   nombres    pseudo-aléatoires   est    proposée   en
+section~\ref{section:genpa}  ainsi  qu'une   méthode  permettant  d'obtenir  des
+matrices         d'itérations         doublement        stochastiques         en
+section~\ref{section:genmat}.  Enfin, en section~\ref{section:expes}  la qualité
+du PRNG obtenu est éprouvée avec les tests standards du domaine.
 
 
 %%% Local Variables: 
 
 
 %%% Local Variables: 
index 5fa40f49c90e3753b0ccb7a792e66d38ea9cb201..bc8524b5951330394e500461650e708f68be85c5 100644 (file)
--- a/main.tex
+++ b/main.tex
@@ -1,15 +1,18 @@
 \documentclass{ita}
 \usepackage{graphicx}
 \documentclass{ita}
 \usepackage{graphicx}
+\usepackage{caption}
+\usepackage{subcaption}
+
 \usepackage{dsfont}
 \usepackage{stmaryrd}
 \usepackage{dsfont}
 \usepackage{stmaryrd}
-\usepackage[font=footnotesize]{subfig}
+%\usepackage[font=footnotesize]{subfig}
 \usepackage{ifthen}
 \usepackage{color}
 \usepackage{algorithm2e}
 \usepackage{epstopdf}
 \usepackage{ifthen}
 \usepackage{color}
 \usepackage{algorithm2e}
 \usepackage{epstopdf}
+%\usepackage{ntheorem}
 
 
-
-\usepackage[latin1]{inputenc}
+\usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc} 
 \usepackage[english]{babel}
 \usepackage{amsmath,amssymb,latexsym,eufrak,euscript}
 \usepackage[T1]{fontenc} 
 \usepackage[english]{babel}
 \usepackage{amsmath,amssymb,latexsym,eufrak,euscript}
@@ -28,7 +31,7 @@
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-% Définitions personnelles
+% Définitions personnelles
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 \definecolor{bleuclair}{rgb}{0.75,0.75,1.0}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 \definecolor{bleuclair}{rgb}{0.75,0.75,1.0}
 \def \ts {\tau_{\rm stop}}
 
 
 \def \ts {\tau_{\rm stop}}
 
 
-% \theoremstyle{plain}
-% \theoremheaderfont{\normalfont\bfseries\sc}
-% \theorembodyfont{\slshape}
-% \theoremsymbol{\ensuremath{\diamondsuit}}
-% \theoremprework{\bigskip}
-% \theoremseparator{.}
-\newtheorem{Def}{\underline{Definition}}
-\newtheorem{Lemma}{\underline{Lemma}}
-\newtheorem{Theo}{\underline{Theorem}}
-% \theoremheaderfont{\sc}
-% \theorembodyfont{\upshape}
-% \theoremstyle{nonumberplain}
-% \theoremseparator{}
-% \theoremsymbol{\rule{1ex}{1ex}}
-\newtheorem{Proof}{Proof}
+\newtheorem{Def}{Definition}
+%\newtheorem{Lemma}{\underline{Lemma}}
+\newtheorem{Theo}{Theorem}
+\newtheorem{Corollary}{Corollary}
+\newtheorem{Lemma}{Lemma}
 \newtheorem{proposition}{Proposition}
 \newtheorem{proposition}{Proposition}
-\newtheorem{xpl}{Running Example}
+\newtheorem*{xpl}{Running Example}
 
 \newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}}
 %\newcommand{\ie}{\textit{i.e.}}
 
 \newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}}
 %\newcommand{\ie}{\textit{i.e.}}
 
 \begin{document}
 
 
 \begin{document}
 
-\author{Jean-François Couchot, Christophe Guyeux, Pierre-Cyrile Heam}
-\address{Institut FEMTO-ST, Université de Franche-Comté, Belfort, France}
+\author{Jean-François Couchot, Christophe Guyeux, Pierre-Cyrile Heam}
+\address{Institut FEMTO-ST, Université de Franche-Comté, Belfort, France}
 
 
-%\author{Sylvain Contassot-Vivier}
-%\address{Loria - UMR 7503, Université de Lorraine, Nancy, France}
 
 
-\date{...}
 
 \begin{abstract}
 
 \begin{abstract}
-This   paper  extends   the  results   presented  in~\cite{bcgr11ip}
-and~\cite{chgw14oip} by using the \emph{chaotic} updating mode, in the sense
+This   paper  extends   the  results   presented  in~\cite{bcgr11:ip}
+and~\cite{DBLP:conf/secrypt/CouchotHGWB14} 
+by using the \emph{chaotic} updating mode, in the sense
 of F.  Robert~\cite{Robert}.  In this mode, several components of the system
 may be  updated at each iteration.   At the theoretical level,  we show that
     the properties of  chaos and uniformity of the  obtained PRNG are preserved.
 of F.  Robert~\cite{Robert}.  In this mode, several components of the system
 may be  updated at each iteration.   At the theoretical level,  we show that
     the properties of  chaos and uniformity of the  obtained PRNG are preserved.
@@ -116,6 +107,8 @@ may be  updated at each iteration.   At the theoretical level,  we show that
     reduced mixing time.
 \end{abstract}
 
     reduced mixing time.
 \end{abstract}
 
+\maketitle
+
 \section{Introduction}
 %\input{intro}
 
 \section{Introduction}
 %\input{intro}
 
@@ -127,27 +120,27 @@ may be  updated at each iteration.   At the theoretical level,  we show that
 \input{chaos}
 
 \section{Generating....}
 \input{chaos}
 
 \section{Generating....}
-\JFC{Reprendre Mons en synthétisant... conclusion: n-cube moins hamitonien.
-question efficacité d'un tel algo}
+\JFC{Reprendre Mons en synthétisant... conclusion: n-cube moins hamitonien.
+question efficacité d'un tel algo}
 %\input{chaos}
 
 \section{Random walk on the modified Hypercube}
 \input{stopping}
 
 % Donner la borne du stopping time quand on marche dedans (nouveau). 
 %\input{chaos}
 
 \section{Random walk on the modified Hypercube}
 \input{stopping}
 
 % Donner la borne du stopping time quand on marche dedans (nouveau). 
-% Énoncer le problème de la taille de cette borne
+% Énoncer le problème de la taille de cette borne
 % (elle est certes finie, mais grande). 
 
 
 
 
 %\section{Quality study of the strategy}
 % (elle est certes finie, mais grande). 
 
 
 
 
 %\section{Quality study of the strategy}
-%6) Se pose alors la question de comment générer une stratégie de "bonne qualité". Par exemple, combien de générateurs aléatoires embarquer ? (nouveau)
+%6) Se pose alors la question de comment générer une stratégie de "bonne qualité". Par exemple, combien de générateurs aléatoires embarquer ? (nouveau)
 
 
 \section{Application to Pseudorandom Number Generation}
 \input{prng}
 
 
 \section{Application to Pseudorandom Number Generation}
 \input{prng}
-\JFC{ajouter ici les expérimentations}
+\JFC{ajouter ici les expérimentations}
 
 
 \section{Conclusion}
 
 
 \section{Conclusion}
diff --git a/markov.bib b/markov.bib
deleted file mode 100644 (file)
index 9b5189b..0000000
+++ /dev/null
@@ -1,390 +0,0 @@
-@inproceedings{chgw+14oip,
-inhal = {no},
-domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO, INFO:INFO_SE},
-equipe = {ie},
-classement = {COM},
-author = {Couchot, Jean-Fran\c{c}ois and H\'eam, Pierre-Cyrille and Guyeux, Christophe and Wang, Qianxue and Bahi, Jacques},
-title = {Pseudorandom Number Generators with Balanced Gray Codes},
-booktitle = {Secrypt 2014, 11th Int. Conf. on Security and Cryptography},
-pages = {***--***},
-address = {Vienna, Austria},
-month = aug,
-date = {28-30 aout},
-year = 2014,
-note = {Position short paper. To appear},
-
-}
-@Article{rwfg,
-  author =      {Laurent Saloff-Coste},
-  title =       {Random Walks on Finite Groups},
-  journal =     {Probability on Descrete Structures},
-  year =        {},
-  OPTkey =      {},
-  volume =      {110},
-  OPTnumber =   {},
-  pages =       {263-346},
-  OPTmonth =    {},
-  note =        {http://stat.stanford.edu/~cgates/PERSI/papers/rwfg.pdf},
-  OPTannote =   {}
-}
-
-@book{LevinPeresWilmer2006,
-  added-at = {2010-01-19T17:51:27.000+0100},
-  author = {Levin, David A. and Peres, Yuval and Wilmer, Elizabeth L.},
-  biburl = {http://www.bibsonomy.org/bibtex/2097dc4d1d0e412b2444f540b04110797/tmalsburg},
-  interhash = {61354795a6accb6407bfdbf04753a683},
-  intrahash = {097dc4d1d0e412b2444f540b04110797},
-  keywords = {markovchains probabilitytheory textbook},
-  publisher = {American Mathematical Society},
-  timestamp = {2010-01-19T17:51:27.000+0100},
-  title = {{Markov chains and mixing times}},
-  url = {http://scholar.google.com/scholar.bib?q=info:3wf9IU94tyMJ:scholar.google.com/&output=citation&hl=en&as_sdt=2000&ct=citation&cd=0},
-  year = 2006
-}
-
-@BOOK{devaney,
-  title = {An Introduction to Chaotic Dynamical Systems},
-  publisher = {Addison-Wesley},
-  year = {1989},
-  author = {Devaney, Robert L.},
-  address = {Redwood City, CA},
-  edition = {2nd}
-}
-
-
-@ARTICLE{Banks92,
-  author = {J. Banks and J. Brooks and G. Cairns and P. Stacey},
-  title = {On {D}evaney's Definition of Chaos},
-  journal = {Amer. Math. Monthly},
-  year = {1992},
-  volume = {99},
-  pages = {332--334},
-  keywords = {(c+),},
-  owner = {guyeux},
-  timestamp = {27/01/2008}
-}
-
-
-@INPROCEEDINGS{wbg10ip,
-  author = {Wang, Qianxue and Bahi, Jacques and Guyeux, Christophe and Fang,
-       Xiaole},
-  title = {Randomness quality of {CI} chaotic generators. Application to Internet
-       security},
-  booktitle = {INTERNET'2010. The 2nd Int. Conf. on Evolving Internet},
-  year = {2010},
-  pages = {125--130},
-  address = {Valencia, Spain},
-  month = sep,
-  publisher = {IEEE Computer Society Press},
-  note = {Best Paper award},
-  classement = {ACTI},
-  doi = {10.1109/INTERNET.2010.30},
-  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
-  equipe = {and},
-  inhal = {no},
-  url = {http://doi.ieeecomputersociety.org/10.1109/INTERNET.2010.30}
-}
-
-
-
-@INPROCEEDINGS{bgw10ip,
-  author = {Bahi, Jacques and Guyeux, Christophe and Wang, Qianxue},
-  title = {A Pseudo Random Numbers Generator Based on Chaotic Iterations. Application
-       to Watermarking},
-  booktitle = {WISM 2010, Int. Conf. on Web Information Systems and Mining},
-  year = {2010},
-  volume = {6318},
-  series = {LNCS},
-  pages = {202--211},
-  address = {Sanya, China},
-  month = oct,
-  classement = {ACTI},
-  doi = {10.1007/978-3-642-16515-3_26},
-  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
-  equipe = {and},
-  inhal = {no},
-  url = {http://dx.doi.org/10.1007/978-3-642-16515-3_26}
-}
-
-
-
-@INPROCEEDINGS{bgw09ip,
-  author = {Bahi, Jacques and Guyeux, Christophe and Wang, Qianxue},
-  title = {A novel pseudo-random generator based on discrete chaotic iterations},
-  booktitle = {INTERNET'09, 1-st Int. Conf. on Evolving Internet},
-  year = {2009},
-  pages = {71--76},
-  address = {Cannes, France},
-  month = aug,
-  classement = {ACTI},
-  doi = {10.1109/INTERNET.2009.18},
-  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
-  equipe = {and},
-  inhal = {no},
-  url = {http://dx.doi.org/10.1109/INTERNET.2009.18}
-}
-
-
-
-@INPROCEEDINGS{guyeuxTaiwan10,
-  author = {Bahi, Jacques M. and Guyeux, Christophe and Wang, Qianxue},
-  title = {Improving random number generators by chaotic iterations. {A}pplication
-       in data hiding},
-  booktitle = {ICCASM 2010, Int. Conf. on Computer Application and System Modeling},
-  year = {2010},
-  pages = {V13-643--V13-647},
-  address = {Taiyuan, China},
-  month = oct,
-  classement = {ACTI},
-  doi = {10.1109/ICCASM.2010.5622199},
-  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
-  equipe = {and},
-  inhal = {no},
-  url = {http://dx.doi.org/10.1109/ICCASM.2010.5622199}
-}
-
-@inproceedings{bcgw11ip,
-inhal = {no},
-domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
-equipe = {and},
-classement = {ACTI},
-author = {Bahi, Jacques and Couchot, Jean-Fran\c{c}ois and Guyeux, Christophe and Wang, Qianxue},
-title = {Class of Trustworthy Pseudo Random Number Generators},
-booktitle = {INTERNET 2011, the 3-rd Int. Conf. on Evolving Internet},
-pages = {72--77},
-address = {Luxembourg, Luxembourg},
-month = jun,
-year = 2011}
-
-
-
-@INPROCEEDINGS{bcgr11ip,
-  author = {Bahi, Jacques and Couchot, Jean-Fran\c{c}ois and Guyeux, Christophe
-       and Richard, Adrien},
-  title = {On the Link Between Strongly Connected Iteration Graphs and Chaotic
-       Boolean Discrete-Time Dynamical Systems},
-  booktitle = {FCT'11, 18th Int. Symp. on Fundamentals of Computation Theory},
-  year = {2011},
-  volume = {6914},
-  series = {LNCS},
-  pages = {126--137},
-  address = {Oslo, Norway},
-  month = aug,
-  classement = {ACTI},
-  doi = {10.1007/978-3-642-22953-4_11},
-  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
-  equipe = {and},
-  inhal = {no},
-  url = "http://dx.doi.org/10.1007/978-3-642-22953-4_11"
-}
-
-
-
-@INPROCEEDINGS{bg10aip,
-  author = {Bahi, Jacques and Guyeux, Christophe},
-  title = {Topological chaos and chaotic iterations, application to Hash functions},
-  booktitle = {IJCNN'10, Int. Joint Conf. on Neural Networks, joint to WCCI'10,
-       IEEE World Congress on Computational Intelligence},
-  year = {2010},
-  pages = {1--7},
-  address = {Barcelona, Spain},
-  month = jul,
-  note = {Best paper award},
-  classement = {ACTI},
-  doi = {10.1109/IJCNN.2010.5596512},
-  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
-  equipe = {and},
-  inhal = {no},
-  url = {http://dx.doi.org/10.1109/IJCNN.2010.5596512}
-}
-
-
-@ARTICLE{DBLPjournals/corr/abs-1112-5239,
-  author = {Jacques M. Bahi and Rapha{\"e}l Couturier and Christophe Guyeux and
-       Pierre-Cyrille H{\'e}am},
-  title = {Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom
-       Numbers on GPU},
-  journal = {CoRR},
-  year = {2011},
-  volume = {abs/1112.5239},
-  bibsource = {DBLP, http://dblp.uni-trier.de},
-  ee = {http://arxiv.org/abs/1112.5239}
-}
-
-@MISC{Nist10,
-  author = {E. Barker and A. Roginsky},
-  title = {DRAFT {N}{I}{S}{T} Special Publication 800-131 Recommendation for
-       the Transitioning of Cryptographic Algorithms and Key Sizes},
-  year = {2010},
-  owner = {christophe},
-  timestamp = {2010.08.18}
-}
-
-
-@ARTICLE{LEcuyerS07,
-  author = {Pierre L'Ecuyer and Richard J. Simard},
-  title = {Test{U01}: {A} {C} library for empirical testing of random number
-       generators},
-  journal = {ACM Trans. Math. Softw},
-  year = {2007},
-  volume = {33},
-  number = {4},
-  bibdate = {2007-11-06},
-  bibsource = {DBLP, http://dblp.uni-trier.de/db/journals/toms/toms33.html#LEcuyerS07},
-  url = {http://doi.acm.org/10.1145/1268776.1268777}
-}
-
-
-@ARTICLE{Marsaglia1996,
-  author = {G. Marsaglia},
-  title = {DIEHARD: a battery of tests of randomness},
-  journal = {http://stat.fsu.edu/~geo/diehard.html},
-  year = {1996},
-  owner = {qianxue},
-  timestamp = {2009.11.09}
-}
-
-@PHDTHESIS{Xiaole13,
-  author = {Xiaole Fang},
-  title = {Utilization of chaotic dynamics for generating pseudorandom numbers
-       in various contexts},
-  school = {Universit\'{e} de Franche-Comt\'{e}},
-  year = {2013},
-  owner = {guyeux},
-  timestamp = {2008.01.02}
-}
-
-@BOOK{Robert,
-  title = {Discrete Iterations, a Metric Study},
-  publisher = {Springer-Verlag},
-  year = {1986},
-  author = {Fran\,cois Robert},
-  volume = {6},
-  series = {Series in Computational Mathematics}
-}
-
-
-@ARTICLE{915396,
-author={Stojanovski, T. and Pihl, J. and Kocarev, L.}, 
-journal={Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on}, 
-title={Chaos-based random number generators. Part II: practical realization}, 
-year={2001}, 
-month={Mar}, 
-volume={48}, 
-number={3}, 
-pages={382-385}, 
-keywords={CMOS analogue integrated circuits;chaos generators;circuit simulation;piecewise linear techniques;random number generation;redundancy;switched current circuits;0.8 micron;1 Mbit/s;chaos-based random number generators;chaotic piecewise-linear one-dimensional map;output bit rate;parasitic attractors;periodic attractors;post-layout circuit simulations;process conditions;redundancy;standard CMOS process;switched current techniques;Bit rate;CMOS process;Chaos;Circuits;Electric breakdown;Information analysis;Piecewise linear techniques;Power supplies;Random number generation;Temperature}, 
-doi={10.1109/81.915396}, 
-ISSN={1057-7122},}
-
-
-@ARTICLE{915385, 
-author={Stojanovski, T. and Kocarev, L.}, 
-journal={Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on}, 
-title={Chaos-based random number generators-part I: analysis [cryptography]}, 
-year={2001}, 
-month={Mar}, 
-volume={48}, 
-number={3}, 
-pages={281-288}, 
-keywords={Markov processes;chaos;cryptography;piecewise linear techniques;random number generation;Markov generating partition;Markov information source;chaos-based random number generators;cryptography;information generation process;parameter values;piecewise-linear one-dimensional map;random number generator;Chaos;Cryptographic protocols;Cryptography;Current measurement;Low-frequency noise;Noise measurement;Random number generation;Random sequences;Security;Semiconductor device noise}, 
-doi={10.1109/81.915385}, 
-ISSN={1057-7122},}
-
-@INPROCEEDINGS{5376454, 
-author={Li Cao and Lequan Min and Hongyan Zang}, 
-booktitle={Computational Intelligence and Security, 2009. CIS '09. International Conference on}, 
-title={A Chaos-Based Pseudorandom Number Generator and Performance Analysis}, 
-year={2009}, 
-month={Dec}, 
-volume={1}, 
-pages={494-498}, 
-keywords={binary sequences;chaos;discrete systems;random number generation;synchronisation;2D Arnold cat map;6D discrete chaos map;FIPA-140-2 tests;National Institute of Standard and Technology;binary number sequences;chaos-based pseudorandom number generator;confidence interval analysis;generalized chaos synchronization theorem;performance analysis;Chaos;Chaotic communication;Computational intelligence;NIST;Nonlinear dynamical systems;Performance analysis;Random number generation;Security;Space technology;Testing;Discrete chaos map;generalized chaos synchronization;one-time-pad;statistical test}, 
-doi={10.1109/CIS.2009.203},}
-
-@article{bfgw13ij,
-inhal = {no},
-domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
-equipe = {and},
-classement = {ACLI},
-impact-factor ={1.065},
-isi-acro = {J NETW COMPUT APPL},
-author = {Bahi, Jacques and Fang, Xiaole and Guyeux, Christophe and Wang, Qianxue},
-title = {Suitability of chaotic iterations schemes using {XORshift} for security applications},
-journal = {JNCA, Journal of Network and Computer Applications},
-pages = {282--292},
-volume = 37,
-doi = {10.1016/j.jnca.2013.03.001},
-url = {http://dx.doi.org/10.1016/j.jnca.2013.03.001},
-abstract = {The design and engineering of original cryptographic solutions is a major concern to provide secure information systems. In a previous study, we have described a generator based on chaotic iterations, which uses the well-known XORshift generator. By doing so, we have improved the statistical performances of XORshift and make it behave chaotically, as defined by Devaney. The speed and security of this former generator have been improved in a second study, to make its usage more relevant in the Internet security context. In this paper, these contributions are summarized and a new version of the generator is introduced. It is based on a new Lookup Table implying a large improvement of speed. A comparison and a security analysis between the XORshift and these three versions of our generator are proposed, and various new statistical results are given. Finally, an application in the information hiding framework is presented, to give an illustrative example of the use of such a generator in the Internet security field.},
-publisher = {Elsevier},
-year = 2013,
-
-}
-
-
-@article{Marsaglia2003JSSOBKv08i14,
-  author =     "George Marsaglia",
-  title =      "Xorshift RNGs",
-  journal =    "Journal of Statistical Software",
-  volume =     "8",
-  number =     "14",
-  pages =      "1--6",
-  day =        "4",
-  month =      "7",
-  year =       "2003",
-  CODEN =      "JSSOBK",
-  ISSN =       "1548-7660",
-  bibdate =    "2003-07-04",
-  URL =        "http://www.jstatsoft.org/v08/i14",
-  accepted =   "2003-07-04",
-  acknowledgement = "",
-  keywords =   "",
-  submitted =  "2003-05-06",
-}
-
-
-
-@INPROCEEDINGS{cghwb14ip,
-  author = {Couchot, Jean-Fran\c{c}ois and Guyeux, Christophe and Heam, 
-Pierre-Cyrille, and Wang, Qianxue and Bahi, Jacques},
-  title = {Pseudorandom Number Generators with Balanced Gray Codes},
-  booktitle = {SECRYPT 2014, the 11th International Conference on Security and Cryptography},
-  year = {2014},
-  pages = {***--***},
-  address = {Vienna, Austria},
-  month = aug,
-  classement = {ACTI},
-  doi = {10.1007/978-3-642-22953-4_11},
-  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
-  equipe = {and},
-  inhal = {no},
-}
-
-@Article{ZanSup04,
-  author =       {Suparta, IN and Zanten, AJ van},
-  title =        {Totally balanced and exponentially balanced Gray codes},
-  journal =      {Discrete Analysis and Operation Research (Russia)},
-  year =         {2004},
-  OPTkey =       {},
-  volume =    {11},
-  number =    {4},
-  pages =     {81-98},
-  OPTmonth =     {},
-  OPTnote =      {},
-  OPTannote =    {}
-}
-
-@Article{Feder2009NTB,
-  title =      "Nearly tight bounds on the number of Hamiltonian
-                circuits of the hypercube and generalizations",
-  author =     "Tom{\'a}s Feder and Carlos S. Subi",
-  journal =    "Info. Process. Lett",
-  year =       "2009",
-  number =     "5",
-  volume =     "109",
-  pages =      "267--272",
-  URL =        "http://dx.doi.org/10.1016/j.ipl.2008.10.015",
-}
-
-
index 9441aab3a586ced9fb98b0b7d799c13e24d4ffed..1200bc519103d7ac6dbe9a9d3c4d32404fdff062 100644 (file)
@@ -3,36 +3,49 @@ $\Bool=\{0,1\}$ with the classical operators of conjunction '.',
 of disjunction '+', of negation '$\overline{~}$', and of 
 disjunctive union $\oplus$. 
 
 of disjunction '+', of negation '$\overline{~}$', and of 
 disjunctive union $\oplus$. 
 
-Let $n$ be a positive integer. A  {\emph{Boolean map} $f$ is 
-a function from $\Bool^n$  
+Let us first introduce basic notations.
+Let $\mathsf{N}$ be a positive integer. The set $\{1, 2, \hdots , \mathsf{N}\}$
+of integers belonging between $1$ and $\mathsf{N}$
+is further denoted as $\llbracket 1, \mathsf{N} \rrbracket$.
+A  {\emph{Boolean map} $f$ is 
+a function from $\Bool^{\mathsf{N}}$  
 to itself 
 such that 
 to itself 
 such that 
-$x=(x_1,\dots,x_n)$ maps to $f(x)=(f_1(x),\dots,f_n(x))$.
+$x=(x_1,\dots,x_{\mathsf{N}})$ maps to $f(x)=(f_1(x),\dots,f_{\mathsf{N}}(x))$.
+In what follows, for any finite set $X$, $|X|$ denotes its cardinality and 
+$\lfloor y \rfloor$ is
+the largest integer lower than $y$.
+
 Functions are iterated as follows. 
 At the $t^{th}$ iteration, only the $s_{t}-$th component is said to be
 Functions are iterated as follows. 
 At the $t^{th}$ iteration, only the $s_{t}-$th component is said to be
-``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;n \rrbracket$ called ``strategy''. 
+``iterated'', where $s = \left(s_t\right)_{t \in \mathds{N}}$ is a sequence of indices taken in $\llbracket 1;{\mathsf{N}} \rrbracket$ called ``strategy''. 
 Formally,
 Formally,
-let $F_f: \llbracket1;n\rrbracket\times \Bool^{n}$ to $\Bool^n$ be defined by
+let $F_f:  \Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket$ to $\Bool^{\mathsf{N}}$ be defined by
 \[
 \[
-F_f(i,x)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_n).
+F_f(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_{\mathsf{N}}).
 \]
 \]
-Then, let $x^0\in\Bool^n$ be an initial configuration
+Then, let $x^0\in\Bool^{\mathsf{N}}$ be an initial configuration
 and $s\in
 and $s\in
-\llbracket1;n\rrbracket^\Nats$ be a strategy, 
+\llbracket1;{\mathsf{N}}\rrbracket^\Nats$ be a strategy, 
 the dynamics are described by the recurrence
 \begin{equation}\label{eq:asyn}
 the dynamics are described by the recurrence
 \begin{equation}\label{eq:asyn}
-x^{t+1}=F_f(s_t,x^t).
+x^{t+1}=F_f(x^t,s_t).
 \end{equation}
 
 
 \end{equation}
 
 
+
+
+
 Let be given a Boolean map $f$. Its associated   
 {\emph{iteration graph}}  $\Gamma(f)$ is the
 directed graph such that  the set of vertices is
 Let be given a Boolean map $f$. Its associated   
 {\emph{iteration graph}}  $\Gamma(f)$ is the
 directed graph such that  the set of vertices is
-$\Bool^n$, and for all $x\in\Bool^n$ and $i\in \llbracket1;n\rrbracket$,
-the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(i,x)$. 
+$\Bool^{\mathsf{N}}$, and for all $x\in\Bool^{\mathsf{N}}$ and $i\in \llbracket1;{\mathsf{N}}\rrbracket$,
+the graph $\Gamma(f)$ contains an arc from $x$ to $F_f(x,i)$.
+Each arc $(x,F_f(x,i))$ is labelled with $i$. 
+
 
 \begin{xpl}
 
 \begin{xpl}
-Let us consider for instance $n=3$.
+Let us consider for instance ${\mathsf{N}}=3$.
 Let 
 $f^*: \Bool^3 \rightarrow \Bool^3$ be defined by
 $f^*(x_1,x_2,x_3) = 
 Let 
 $f^*: \Bool^3 \rightarrow \Bool^3$ be defined by
 $f^*(x_1,x_2,x_3) = 
@@ -40,86 +53,49 @@ $f^*(x_1,x_2,x_3) =
 \overline{x_1}\overline{x_3} + x_1x_2)$.
 The iteration graph $\Gamma(f^*)$ of this function is given in 
 Figure~\ref{fig:iteration:f*}.
 \overline{x_1}\overline{x_3} + x_1x_2)$.
 The iteration graph $\Gamma(f^*)$ of this function is given in 
 Figure~\ref{fig:iteration:f*}.
+\end{xpl}
 
 
-\vspace{-1em}
 \begin{figure}[ht]
 \begin{center}
 \includegraphics[scale=0.5]{images/iter_f0c}
 \end{center}
 \begin{figure}[ht]
 \begin{center}
 \includegraphics[scale=0.5]{images/iter_f0c}
 \end{center}
-\vspace{-0.5em}
 \caption{Iteration Graph $\Gamma(f^*)$ of the function $f^*$}\label{fig:iteration:f*}
 \end{figure}
 \caption{Iteration Graph $\Gamma(f^*)$ of the function $f^*$}\label{fig:iteration:f*}
 \end{figure}
-\end{xpl}
-
 
 
-Let thus be given such kind of map.
-This article focuses on studying its iterations according to
-the equation~(\ref{eq:asyn}) with a given strategy.
-First of all, this can be interpreted as walking into its iteration graph 
-where the choice of the edge to follow is decided by the strategy.
-Notice that the iteration graph is always a subgraph of 
-$n$-cube augmented with all the self-loop, \textit{i.e.}, all the 
-edges $(v,v)$ for any $v \in \Bool^n$. 
-Next, if we add probabilities on the transition graph, iterations can be 
-interpreted as Markov chains.
+Let us finally recall the pseudorandom number generator $\chi_{\textit{14Secrypt}}$
+\cite{DBLP:conf/secrypt/CouchotHGWB14}
+formalized in Algorithm~\ref{CI Algorithm}.
+It is based on random walks in $\Gamma(f)$. 
+More precisely, let be given a Boolean map $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$,
+an input PRNG \textit{Random},
+an integer $b$ that corresponds to a number of iterations, and 
+an initial configuration $x^0$. 
+Starting from $x^0$, the algorithm repeats $b$ times 
+a random choice of which edge to follow and traverses this edge.
+The final configuration is thus outputted.
 
 
-\begin{xpl}
-Let us consider for instance  
-the graph $\Gamma(f)$ defined 
-in \textsc{Figure~\ref{fig:iteration:f*}.} and 
-the probability function $p$ defined on the set of edges as follows:
-$$
-p(e) \left\{
-\begin{array}{ll}
-= \frac{2}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\
-= \frac{1}{6} \textrm{ otherwise.}
-\end{array}
-\right.  
-$$
-The matrix $P$ of the Markov chain associated to the function $f^*$ and to its probability function $p$ is 
-\[
-P=\dfrac{1}{6} \left(
-\begin{array}{llllllll}
-4&1&1&0&0&0&0&0 \\
-1&4&0&0&0&1&0&0 \\
-0&0&4&1&0&0&1&0 \\
-0&1&1&4&0&0&0&0 \\
-1&0&0&0&4&0&1&0 \\
-0&0&0&0&1&4&0&1 \\
-0&0&0&0&1&0&4&1 \\
-0&0&0&1&0&1&0&4 
-\end{array}
-\right)
-\]
-\end{xpl}
 
 
+\begin{algorithm}[ht]
+\begin{scriptsize}
+%\JFC{Mettre ceci dans une boite flottante}
+\KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ (${\mathsf{N}}$ bits)}
+\KwOut{a configuration $x$ (${\mathsf{N}}$ bits)}
+$x\leftarrow x^0$\;
+\For{$i=0,\dots,b-1$}
+{
+$s\leftarrow{\textit{Random}({\mathsf{N}})}$\;
+$x\leftarrow{F_f(x,s)}$\;
+}
+return $x$\;
+\end{scriptsize}
+\caption{Pseudo Code of the $\chi_{\textit{14Secrypt}}$ PRNG}
+\label{CI Algorithm}
+\end{algorithm}
 
 
-% % Let us first recall the  \emph{Total Variation} distance $\tv{\pi-\mu}$,
-% % which is defined for two distributions $\pi$ and $\mu$ on the same set 
-% % $\Bool^n$  by:
-% % $$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$ 
-% % It is known that
-% % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$
-
-% % Let then $M(x,\cdot)$ be the
-% % distribution induced by the $x$-th row of $M$. If the Markov chain
-% % induced by
-% % $M$ has a stationary distribution $\pi$, then we define
-% % $$d(t)=\max_{x\in\Bool^n}\tv{M^t(x,\cdot)-\pi}.$$
-% Intuitively $d(t)$ is the largest deviation between
-% the distribution $\pi$ and $M^t(x,\cdot)$, which 
-% is the result of iterating $t$ times the function.
-% Finally, let $\varepsilon$ be a positive number, the \emph{mixing time} 
-% with respect to $\varepsilon$ is given by
-% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
-% It defines the smallest iteration number 
-% that is sufficient to obtain a deviation lesser than $\varepsilon$.
-% Notice that the upper and lower bounds of mixing times cannot    
-% directly be computed with eigenvalues formulae as expressed 
-% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work  
-% only consider reversible Markov matrices whereas we do no restrict our 
-% matrices to such a form.
 
 
 
 
+With all this material, we can study the chaos properties of these 
+function.
+This is the aims of the next section. 
 
 
 
 
index 2ceecc7d7f6de1810624248447ed15d4eb70dc61..88253cf19642f958b41ce6fe363085477988939c 100644 (file)
--- a/prng.tex
+++ b/prng.tex
@@ -40,7 +40,7 @@ the probability to execute the function $F_f$ is equal to 0.5 since
 the output of $\textit{Random(1)}$ is uniform in $\{0,1\}$.  
 
 Let $f: \Bool^{n} \rightarrow \Bool^{n}$.
 the output of $\textit{Random(1)}$ is uniform in $\{0,1\}$.  
 
 Let $f: \Bool^{n} \rightarrow \Bool^{n}$.
-It has been shown~\cite[Th. 4, p. 135]{BCGR11}} that 
+It has been shown~\cite[Th. 4, p. 135]{bcgr11:ip} that 
 if its iteration graph is strongly connected, then 
 the output of $\chi_{\textit{14Secrypt}}$ follows 
 a law that tends to the uniform distribution 
 if its iteration graph is strongly connected, then 
 the output of $\chi_{\textit{14Secrypt}}$ follows 
 a law that tends to the uniform distribution 
index 9664549d4fa96496bf1fd20c27d8a90a8fc80b5f..96fd41bce908524622db7243fcc3b079bd633b04 100644 (file)
@@ -1,3 +1,80 @@
+
+
+
+Let thus be given such kind of map.
+This article focuses on studying its iterations according to
+the equation~(\ref{eq:asyn}) with a given strategy.
+First of all, this can be interpreted as walking into its iteration graph 
+where the choice of the edge to follow is decided by the strategy.
+Notice that the iteration graph is always a subgraph of 
+${\mathsf{N}}$-cube augmented with all the self-loop, \textit{i.e.}, all the 
+edges $(v,v)$ for any $v \in \Bool^{\mathsf{N}}$. 
+Next, if we add probabilities on the transition graph, iterations can be 
+interpreted as Markov chains.
+
+\begin{xpl}
+Let us consider for instance  
+the graph $\Gamma(f)$ defined 
+in \textsc{Figure~\ref{fig:iteration:f*}.} and 
+the probability function $p$ defined on the set of edges as follows:
+$$
+p(e) \left\{
+\begin{array}{ll}
+= \frac{2}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\
+= \frac{1}{6} \textrm{ otherwise.}
+\end{array}
+\right.  
+$$
+The matrix $P$ of the Markov chain associated to the function $f^*$ and to its probability function $p$ is 
+\[
+P=\dfrac{1}{6} \left(
+\begin{array}{llllllll}
+4&1&1&0&0&0&0&0 \\
+1&4&0&0&0&1&0&0 \\
+0&0&4&1&0&0&1&0 \\
+0&1&1&4&0&0&0&0 \\
+1&0&0&0&4&0&1&0 \\
+0&0&0&0&1&4&0&1 \\
+0&0&0&0&1&0&4&1 \\
+0&0&0&1&0&1&0&4 
+\end{array}
+\right)
+\]
+\end{xpl}
+
+
+% % Let us first recall the  \emph{Total Variation} distance $\tv{\pi-\mu}$,
+% % which is defined for two distributions $\pi$ and $\mu$ on the same set 
+% % $\Bool^n$  by:
+% % $$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$ 
+% % It is known that
+% % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$
+
+% % Let then $M(x,\cdot)$ be the
+% % distribution induced by the $x$-th row of $M$. If the Markov chain
+% % induced by
+% % $M$ has a stationary distribution $\pi$, then we define
+% % $$d(t)=\max_{x\in\Bool^n}\tv{M^t(x,\cdot)-\pi}.$$
+% Intuitively $d(t)$ is the largest deviation between
+% the distribution $\pi$ and $M^t(x,\cdot)$, which 
+% is the result of iterating $t$ times the function.
+% Finally, let $\varepsilon$ be a positive number, the \emph{mixing time} 
+% with respect to $\varepsilon$ is given by
+% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$
+% It defines the smallest iteration number 
+% that is sufficient to obtain a deviation lesser than $\varepsilon$.
+% Notice that the upper and lower bounds of mixing times cannot    
+% directly be computed with eigenvalues formulae as expressed 
+% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work  
+% only consider reversible Markov matrices whereas we do no restrict our 
+% matrices to such a form.
+
+
+
+
+
+
+
 This section considers functions $f: \Bool^n \rightarrow \Bool^n $ 
 issued from an hypercube where an Hamiltonian path has been removed.
 A specific random walk in this modified hypercube is first 
 This section considers functions $f: \Bool^n \rightarrow \Bool^n $ 
 issued from an hypercube where an Hamiltonian path has been removed.
 A specific random walk in this modified hypercube is first