From: couchot Date: Mon, 9 Feb 2015 14:20:56 +0000 (+0100) Subject: initialisation X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/c8b7da5a49ee32f19091be950c39633b20b344e3 initialisation --- diff --git a/Equivalence.tex b/Equivalence.tex new file mode 100644 index 0000000..d315b6b --- /dev/null +++ b/Equivalence.tex @@ -0,0 +1,294 @@ +%%%%%%%% Sample LaTeX input for Complex Systems %%%%%%%%%%% +% +% This is a LaTeX input file +% Text following % on a particular line is treated as a comment, and +% ignored by LaTeX. +% You do not need to type any text that follows a % +% +\documentclass{article} + +\usepackage{epsf} +\usepackage{complex-systems} +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{algorithm} +\usepackage{algorithmic} +\usepackage[utf8]{inputenc} +\usepackage{color} +\usepackage{framed} + +% complex-systems.sty is the special macro package for Complex Systems. +% epsf.sty is the preferred graphics import method + +% complex-systems.sty defines the following defaults: +% \newtheorem{theorem}{Theorem} +% \newtheorem{lemma}{Lemma} +% \newtheorem{corollary}{Corollary} +% \newtheorem{example}{Example} +% \newtheorem{proposition}{Proposition} + +%%% Personal definitions +\newcommand{\Alg}[1]{Algorithm~\ref{#1}} +\newcommand{\Sec}[1]{Section~\ref{#1}} +\newcommand{\Equ}[1]{Equ.(\ref{#1})} +\newcommand{\Prop}[1]{Prop.~\ref{#1}} +\newcommand{\Th}[1]{Theorem~\ref{#1}} +\newcommand{\Fig}[1]{Fig.~\ref{#1}} +\newcommand{\Def}[1]{Def.~\ref{#1}} + +\newcommand{\astep}{\stackrel{a.s}{\mapsto}} +\newcommand{\alead}{\stackrel{a.i}{\leadsto}} +\newcommand{\aconv}{\stackrel{a.cv}{\Longrightarrow}} +\newcommand{\notaconv}{\stackrel{a.cv}{\Longrightarrow}\hspace{-5mm}/\hspace{3.2mm}} +\newcommand{\boolprod}{\stackrel{\sim}{\prod}} +\newcommand{\cycle}{Cycle} +\newcommand{\pcycle}{p\_Cyc} +\newcommand{\sub}{S} + +\def\N{\mathbb{N}} +\def\R{\mathbb{R}} + +\definecolor{shadecolor}{rgb}{0.95,0.95,0.95} +\newenvironment{Algo}{\begin{center}\begin{minipage}[h]{0.95\columnwidth}\begin{shaded}\begin{tabbing}% + \hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\= \kill} % + { \end{tabbing}\vspace{-1em}\end{shaded}\end{minipage}\end{center}\vspace{-1em}} + +%%% +%%% MAIN DOCUMENT +%%% +\begin{document} + +% +% The format for a general title is slightly complicated; +% here first is a comment giving a simple example: % +% \title{Sample Paper for Complex Systems} +% \author{\authname{First Author}\\[2pt] +% \authadd{University Department, University Name, Address,}\\ +% \authadd{City, State ZIP/Zone, Country}\\ +% \authadd{and}\\ +% \authadd{Group, Company, Address, City, State ZIP/Zone, Country}\\ +% \and +% \authname{Second Author}\\ +% \authname{Third Author}\\ +% \authname{Fourth Author}\\[2pt] +% \authadd{Group, Laboratory, Address, City, State ZIP/Zone, Country} +% } +% \markboth{F. Author, S. Author, T. Author, and F. Author} +% {Sample Paper for Complex Systems} +% \maketitle + +% Here is a more complete case: + +\title{Transformation of Asynchronous System with Delays to Asynchronous System + without Delays} +% Use \\ to indicate line breaks in titles longer than about +% 55 characters. +% Lines throughout the title section should be broken so that +% successive lines are progressively shorter. +% Use \thanks for footnotes to the title. Put acknowledgments at the +% end of the paper. +% +% \thanks{The title serves as a headline for the paper: many readers +% use it to decide whether to look at the paper. Avoid excessively +% general, technical, or cutesy titles. Questions are acceptable as +% titles. Capitalize the first letters of important words only. +% Funding and personal acknowledgments go at the end of the paper. +% Use footnotes to the title only for statements such as ``This paper +% was based on a talk given at the conference on$\ldots$'' or ``Part 1 +% in this series of papers appeared in$\ldots$''}} + +\author{\authname{Sylvain Contassot-Vivier% +\thanks{Electronic mail address: contasss@loria.fr}} +\\[2pt] +% Use \\[2pt] to end the line and add space between author and affiliation +\authadd{Loria UMR 7503, Université Lorraine}\\ +\authadd{Campus Scientifique - BP 239}\\ +\authadd{54506 Vandoeuvre-lès-Nancy, France} +%\thanks{Give complete affiliation and mailing address, including +%country. Capitalize important words and proper names only. (Use +%standard two-letter abbreviations for state names.) For foreign +%addresses, give as much as possible in English. }\\ +%\authadd{and}\\ +%\authadd{Group, Company, Address, City, State ZIP/Zone, Country}\\ +%\and +% precede the second set of authors with \and. +%\authname{Second Author} \\ +%\authname{Third Author}\\ +%\authname{Fourth Author}\\[2pt] +% Each author name goes on a separate line. +%\authadd{Group, Laboratory, Address, City, State ZIP/Zone, Country} +% Put no ``.'' at the end of any address. +} + +\maketitle +% End title section + +% The following specifies the running headings +\markboth{S. Contassot-Vivier}{Equivalence between asynchronous systems} + +% Each running heading should be less than about 50 characters long. +% If necessary, give a shortened version of the title. Do not use +% abbreviations. +% +% If they will fit, include complete author names; otherwise use +% initials only. If abbreviated names do not fit, truncate the author +% list and end with ``and others''. + +\begin{abstract} + This paper presents a transformation process of any asynchronous complex + system with delays to an equivalent asynchronous system without delays. The + interest of such equivalence lies in the suppression of the history dependency + of the system in its evolution. This has an important impact on the study of + the dynamic of the system. The equivalence is illustrated on representative + examples and the gain is pointed out by a comparison between algorithms for + attraction basin determination. +\end{abstract} + +% The text of the paper follows. It is usually easiest to put +% everything in the same file. The file may however need to be +% split for some computer mail systems. +% Automatic section numbering in the LaTeX source is encouraged, +% but is not essential. + +\section{Introduction} +\label{intro} + +The different models of complex systems are essential in the study of many real +life systems, whatever they are natural or man-made. % As a particularly +% interesting example, parallel iterative algorithms play a central role in the +% domain of scientific computation and simulation. Indeed, such algorithms are the +% key to high accuracy and large scale simulations of complex phenomena. +In this paper, we focus on the discrete-time discrete-state systems. The +discrete nature of the states is not a limitation of the model according to +potential applications in computer science as current computers actually use +discrete number representations. However, the study of their behavior stays +difficult, especially due to the fast combinatorial explosion in possible states +of such systems. Moreover, different models exist that can take into account +some specific behaviors such as asynchrony between the elements of the system +and also communication delays between the elements. Such models are very +interesting because they are among the most general ones. However, it is yet +harder to study them, especially the ones including communication delays due to +the dependence of the history of the system in its evolution. + +In this paper, we propose an equivalence between asynchronous systems with and +without communication delays. The interest of such an equivalence is the +possibility to reduce the complexity of the behavior study of systems with +delays. In fact, the history of the system is no more required to explore its +possible evolutions and this represents a great simplification. Moreover, it +allows the use of the same theoretical results and tools as for systems without +delays. + +The next section presents the standard formulation of complex systems, recall +the main asynchronous modes that are usually studied and details the specific +model we focus on. In \Sec{sec:transfo}, the theoretical result of equivalence +between asynchronism with delays and asynchronism without delays is presented. +Then, some representative examples are given in \Sec{sec:ex}. Finally, a +comparison of attraction basin determination between the two formulations of a +given system is performed in \Sec{sec:comp}. + +\section{Asynchronous complex systems} +\label{sec:base} + +\subsection{Notations} +\label{sec:notations} + +Classically, a complex system is composed of $n$ elements. Each element $x_i$ +takes its value in the set $E_i$ and the global value of the system is then the +collection of the states of all the elements $x=(x_1,...x_n)$ in the set $E = +\prod_{i=1}^nE_i$. The dynamics of the system is given by the evolution +functions $f_i$ respectively associated to the $x_i$. Here again, the collection +of the individual functions forms the global evolution function of the system +$f=(f_1,f_2,...,f_n)$. Each $f_i$ may be general and can be expressed as +algorithms taking as input the values of the components in the system and +yielding one value in $E_i$. This feature is very important as it implies a +larger generality than specific systems such as cellular automata. Finally, the +system evolves during discrete time $t$ (also called iterations) and the state +at time $t$ is denoted by $x^{t}=(x_1^t,...,x_n^t)$. + +The synchronous dynamics of such a system is given by \Alg{algo:sync}. +\begin{algorithm}[h] + \caption{Synchronous system} + \label{algo:sync} + \begin{Algo} + Given an initial state $x^{0}=(x_{1}^{0},...,x_{n}^{0})$\\ + \textbf{for} $t=0,1,...$\\ + \>\textbf{for} $i=1,...,n$\\ + \>\>$x_{i}^{t+1} = f_i(x^{t}) = f_i(x_1^t,x_2^t, ...,x_n^t)$\\ + \>\textbf{endfor}\\ + \textbf{endfor} + \end{Algo} +\end{algorithm} + +\subsection{Asynchronous mode} +\label{sec:opmodes} + +Classically, different models of asynchronism are used depending on the way the +communications are managed and the updatings are +performed~\cite{Rob86,BT89,HM93}. In this study, we consider the fully +asynchronous mode with delays according to \Alg{algo:async}. + +\begin{algorithm}[h] + \caption{Asynchronous system} + \label{algo:async} + \begin{Algo} + Given an initial state $x^{0}=(x_{1}^{0},...,x_{n}^{0})$\\ + \textbf{for} $t=0,1,...$\\ + \>\textbf{for} $i=1,...,n$\\ + \>\>\textbf{if} $i\in J(t)$ \textbf{then}\\ + \>\>\>$x_{i}^{t+1} = f_i(x_1^{t-d_1^i(t)},x_2^{t-d_2^i(t)}, ...,x_n^{t-d_n^i(t)})$\\ + \>\>\textbf{else}\\ + \>\>\>$x_{i}^{t+1} = x_i^t$\\ + \>\>\textbf{endif}\\ + \>\textbf{endfor}\\ + \textbf{endfor} + \end{Algo} +\end{algorithm} + +In this algorithm, $J(t)$ is the subset of elements of the system that are +updated at time $t$ and $d_j^i(t)$ is the delay of element $j$ according to $i$ +at time $t$. So, $d_j^i(t)$ represents the number of iterations between the +production of the value of $x_j$ and its reception on element $i$. When this +value is 0, then there is no delay and element $i$ uses the value of element $j$ +at the previous iteration. Although $d_j^i(t)$ is not bounded, it is generally +assumed that the versions of values received on each element follow the +evolution of the system, that is to say: +$\lim_{t\rightarrow\infty}t-d_{j}^{i}(t) =\infty$. Moreover, the \emph{fair + sampling} condition is also supposed. It assumes that all the element are +regularly updated: $\forall i\in\left\{ 1,...,n\right\} ,\left| \left\{ t,i\in + J(t)\right\} \right| =\infty$. + +\section{Transformation Process } +\label{sec:transfo} + +\section{Representative Examples} +\label{sec:ex} + +\section{Comparison of Attraction Basin Determination} +\label{sec:comp} + +\section*{Acknowledgments} + +\bibliographystyle{plain} +\bibliography{biblio} +%\begin{thebibliography}{99} +% The number of 9s indicates how wide the reference +% numbers must hang for all references to be aligned properly. + +% \bibitem{a-review} +% % ``a-review'' is just a sample tag: use a tag that describes the +% % paper; or perhaps just use numerical tags. +% First Author and Second Author, ``A Review Article,'' \textit{Full Name +% of Journal}, \textbf{volume} (date) page--page. +% % Use \textit{...} for italics, \textbf{...} for boldface. +% % Do not explicitly use the word ``volume'' +% % The full year (e.g., 1991) should be used for the date. +% % Use -- to get an appropiate dash between page numbers. + +%\end{thebibliography} + +\end{document} + + + + diff --git a/annexecontinuite.tex b/annexecontinuite.tex new file mode 100644 index 0000000..8929705 --- /dev/null +++ b/annexecontinuite.tex @@ -0,0 +1,53 @@ +Montrons que pour toute fonction booléenne +$f$ de $\Bool^n$ dans lui-même, $G_f$ est continue sur $(\mathcal{X},d)$. + +Soit $(s_t,x^t)^{t \in \Nats}$ une suite de points de +l'espace $\mathcal{X}$ qui converge vers $(S,x)$. +Montrons que $(G_f (s_t,x^t))^{t \in \Nats}$ converge vers $G_f (S,x)$. + +La distance $d((s_t,x^t), (S,x))$ tend vers 0. +Il en est donc de même pour $d_H(x^t, x)$ et $d_S(s_t, S)$. +Or, $d_H(x^t, x)$ ne prend que des valeurs entières. +Cette distance est donc nulle à partir d'un certain $t_0$. +Ainsi, à partir de $t>t_0$, on a $x^t = x$ . +De plus, $d_S(s_t, S)$ tend vers $0$ donc $d_S(s_t, S) < 10^{-1}$ +à partir d'un certain rang $t_1$. +Ainsi, à partir de $t>t_1$, les suites $(s_t)_{t \in \Nats}$ +ont toutes le même premier terme, qui est celui +de $S$ pour $t$ supérieur à $t_1$. +Pour $t > \max(t_0,t_1)$, les configurations $x^t$ et $x$ +sont les mêmes, +et les stratégies $s_t$ et $S$ ont le même premier terme +($s_0^t = s_0$), donc les configurations +de $F_f(s_0^t,x^t)$ et de $F_f (s_0,x)$ sont égales et donc la distance +entre $G_f(s_t,x^t)$ et $G_f (S,x)$ est inférieure à 1. + +Montrons maintenant que la distance entre +$G_f (s_t,x^t)$ et $G_f (S,x)$ +tend bien vers 0 quand $t$ tend vers $+\infty$. Soit $\epsilon > 0$. +\begin{itemize} + \item Si $\epsilon \ge 1$. Comme la distance $d(G_f(s_t,x^t), G_f (S,x))<1$ + pour $t > \max(t_0, t_1)$, alors + $d(G_f(s_t,x^t), G_f (S,x))<\epsilon$ + \item Si $\epsilon < 1$, alors $\exists k \in \Nats \textrm{ tel que } + 10^{-k} > \epsilon > 10^{-(k+1)}$. + Comme $d_S(s_t, S)$ tend vers 0, il existe +un rang $t_2$ à partir duquel +$\forall t > t_2 , d_S(s_t, S) < 10^{-(k+2)}$: +à partir de ce rang, les $k+2$ premiers termes de $s_t$ sont ceux de $S$. +Donc les $k + 1$ premiers termes des stratégies de +$G_f (s_t,x^t)$ et de +$G_f (s,x)$ sont les mêmes (puisque $G_f$ +opère un décalage sur les stratégies), et vue la +définition de $d_S$, la partie décimale de la distance entre les points +$(s_t,x^t)$ et $(S,x)$ est +inférieure à $10^{-(k+1)} \le \epsilon$. +\end{itemize} +Pour conclure, $\forall\epsilon > 0$, +$\exists~T_0 = \max(t_0, t_1, t_2) \in \Nats$ t.q.\linebreak +$\forall t > T_0 , d (Gf (s_t,x^t),G_f (S,x))< \epsilon$. + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "main" +%%% End: diff --git a/annexesccg.tex b/annexesccg.tex new file mode 100644 index 0000000..10a8054 --- /dev/null +++ b/annexesccg.tex @@ -0,0 +1,126 @@ +Soit $\alpha\in\Bool$. +On nomme $f^{\alpha}$ la fonction de $\Bool^{n-1}$ +dans lui-même définie pour +chaque $x\in\Bool^{n-1}$ par +\[ +f^{\alpha}(x)=(f_1(x,\alpha),\dots,f_{n-1}(x,\alpha)). +\] +On nomme $\Gamma(f)^\alpha$ le sous-graphe +de $\Gamma(f)$ engendré par le sous-ensemble +$\Bool^{n-1} \times \{\alpha\}$ de $\Bool^n$. + +Énonçons et prouvons tout d'abord les lemmes techniques suivants: + +\begin{Lemma}\label{lemma:subgraph} +$G(f^\alpha)$ est un sous-graphe de $G(f)$: chaque arc de $G(f^\alpha)$ est +un arc de $G(f)$. De plus si $G(f)$ n'a pas d'arc de $n$ vers un autre +sommet $i\neq n$, alors on déduit +$G(f^\alpha)$ de $G(f)$ en supprimant le sommet $n$ ainsi que tous les +arcs dont $n$ est soit l'extrémité, soit l'origine (et dans ce dernier +cas, les arcs sont des boucles sur $n$). +\end{Lemma} + +\begin{Proof} +Supposons que $G(f^{\alpha})$ possède un arc de $j$ vers $i$ de signe +$s$. Par définition, il existe un sommet $x\in\Bool^{n-1}$ tel que +$f'^{\alpha}_{ij}(x)=s$, et puisque +$f'^{\alpha}_{ij}(x)=f'_{ij}(x,\alpha)$, on en déduit que $G(f)$ possède un arc +de $j$ à $i$ de signe $s$. Ceci prouve la première assertion. +Pour démontrer la seconde, il suffit de prouver que si +$G(f)$ a un arc de $j$ vers $i$ de signe $s$, avec $i,j\neq n$, alors +$G(f^\alpha)$ contient aussi cet arc. Ainsi, supposons que $G(f)$ a un +arc de $j$ vers $i$ de signe $s$, avec $i,j\neq n$. +Alors, il existe +$x\in\Bool^{n-1}$ et $\beta\in\Bool$ tels que +$f'_{ij}(x,\beta)=s$. Si $f'_{ij}(x,\beta)\neq f'_{ij}(x,\alpha)$, alors +$f_i$ dépend du $n^{\textrm{ème}}$ composant, ce qui est en contradiction +avec les hypothèses. +Ainsi $f'_{ij}(x,\alpha)$ est égal à $s$. +On a donc aussi +$f'^{\alpha}_{ij}(x)=s$. Ainsi $G(f^\alpha)$ possède un arc de $j$ vers $i$ de signe $s$. +\end{Proof} + +\begin{Lemma}\label{lemma:iso} +Les graphes $\Gamma(f^\alpha)$ et $\Gamma(f)^\alpha$ sont isomorphes. +\end{Lemma} + +\begin{Proof} +Soit $h$ la bijection de $\Bool^{n-1}$ vers +$\Bool^{n-1}\times \{\alpha\}$ définie par $h(x)=(x,\alpha)$ pour chaque +$x\in\Bool^{n-1}$. +On voit facilement que $h$ permet de définir un isomorphisme +entre $\Gamma(f^\alpha)$ et $\Gamma(f)^\alpha$: +$\Gamma(f^\alpha)$ possède un arc de $x$ vers $y$ si et seulement si +$\Gamma(f)^\alpha$ a un arc de $h(x)$ vers $h(y)$. +\end{Proof} + + +\begin{Proof} +{\sc{\hspace{-.76em}du théorème~\ref{th:Adrien} :}} +La preuve se fait par induction sur $n$. +Soit $f$ une fonction de $\Bool^n$ dans lui-même et qui vérifie les hypothèses +du théorème. +Si $n=1$ la démonstration est élémentaire: +en raison du troisième point du théorème, $G(f)$ a une boucle négative; +ainsi $f(x)=\overline{x}$ et $\Gamma(f)$ est un cycle de longueur 2. +On suppose donc que $n>1$ et que le théorème est valide pour toutes les +fonctions de $\Bool^{n-1}$ dans lui-même. +En raison du premier point du théorème, $G(f)$ +contient au moins un sommet $i$ tel qu'il n'existe pas dans $G(f)$ +d'arc de $i$ vers un autre sommet $j\neq i$. +Sans perte de généralité, on peut considérer que +ce sommet est $n$. +Alors, d'après le lemme~\ref{lemma:subgraph}, +$f^0$ et $f^1$ vérifient les conditions de l'hypothèse. +Ainsi, par hypothèse d'induction $\Gamma(f^0)$ et +$\Gamma(f^1)$ sont fortement connexes. +Et d'après le lemme~\ref{lemma:iso}, +$\Gamma(f)^0$ et $\Gamma(f)^1$ sont fortement +connexes. +Pour prouver que $\Gamma(f)$ est fortement connexe, il suffit +de prouver que $\Gamma(f)$ contient un arc $x\to y$ avec +$x_n=0y_n$. +En d'autres mots, il suffit de prouver que: +\begin{equation}\tag{$*$} +\forall \alpha\in\Bool,~\exists x\in\Bool^n,\qquad x_n=\alpha\neq f_n(x). +\end{equation} + +On suppose tout d'abord que $n$ a une boucle +négative. +Alors, d'après la définition de +$G(f)$, il existe $x\in\Bool^n$ tel que $f'_{nn}(x)<0$. +Ainsi si $x_n=0$, on a $f_n(x)>f_n(\overline{x}^n)$, et donc +$x_n=0\neq f_n(x)$ et +$\overline{x}^n_n=1\neq f_n(\overline{x}^n)$; +et si $x_n=1$, on a +$f_n(x) 0, +\exists Z \in \mathcal{X}, +\exists t \in \Nats, +d(X,Z) < \epsilon \land k^t(Z) = Y +\] +\end{Def} + +\begin{Def}[Point périodique] + Un point $P \in \mathcal{X}$ est dit \textbf{périodique} de période $t$ pour + une fonction $k$ si $t$ est un entier naturel non nul tel que $k^t(P) = P$ et + pour tout $n$, $0 < n \le t-1$, on a $k^n(P) \neq P$. + Par la suite, $\textbf{Per(k)}$ dénote l'ensemble des points périodiques de + $k$ dans $\mathcal{X}$ de période quelconque. +\end{Def} + +\begin{Def}[Régularité] +Une fonction $k$ est dite \textbf{régulière} dans $(\mathcal{X},d)$ +si l'ensemble des points périodiques de $k$ est dense dans $\mathcal{X}$, +c'est-à-dire si la propriété suivante est établie: +\[ +\forall X \in \mathcal{X}, \forall \epsilon > 0, \exists Y \in \textit{Per}(k) + \textrm{ tel que } d(X,Y) < \epsilon. +\] +\end{Def} + +\begin{Def}[Forte sensibilité aux conditions initiales] +Une fonction $k$ définie sur $(\mathcal{X},d)$ +est \textbf{fortement sensible aux conditions initiales} +s'il existe une valeur $\epsilon> 0$ telle que +pour tout $X \in \mathcal{X}$ et pour tout + $\delta > 0$, il existe $Y \in \mathcal{X}$ et +$t \in \Nats$ qui vérifient $d(X,Y) < \delta$ et +$d(k^t(X) , k^t(Y)) > \epsilon$. +\end{Def} + + +John Banks et ses collègues ont cependant +démontré que la sensibilité aux conditions initiales est une conséquence +de la régularité et de la transitivité topologique~\cite{Banks92}. +On ne se focalise donc que sur ces deux dernières +propriétés pour caractériser les fonctions booléennes $f$ +rendant chaotique la fonction engendrée $G_f$. +Ceci est réalisé en établissant les relations d'inclusion entre +les ensembles $\mathcal{T}$ des fonctions topologiquement transitives, +$\mathcal{R}$ des fonctions régulières +et $\mathcal{C}$ des fonctions chaotiques définis respectivement ci-dessous: +\begin{itemize} +\item $\mathcal{T} = \left\{f : \mathds{B}^n \to +\mathds{B}^n \big/ G_f \textrm{ est transitive} \right\}$, +\item $\mathcal{R} = \left\{f : \mathds{B}^n \to +\mathds{B}^n \big/ G_f \textrm{ est régulière} \right\}$, +\item $\mathcal{C} = \left\{f : \mathds{B}^n \to +\mathds{B}^n \big/ G_f \textrm{ est chaotique} \right\}$. +\end{itemize} + + +Commençons par caractériser l'ensemble $\mathcal{T}$ des fonctions transitives: + +\begin{Theo} $G_f$ est transitive si et seulement si + $\Gamma(f)$ est fortement connexe. +\end{Theo} + +\begin{Proof} + +$\Longleftarrow$ Supposons que $\Gamma(f)$ soit fortement connexe. +Soient $(S,x)$ et $(S',x')$ deux points de $\mathcal{X}$ et $\varepsilon >0$. +On construit la stratégie $\tilde S$ telle que la distance +entre $(\tilde S,x)$ et $(S,x)$ est inférieure à +$\varepsilon$ et telle que les itérations parallèles de $G_f$ depuis +$(\tilde S,x)$ mènent au point $(S',x')$. + +Pour cela, on pose $t_1 =-\lfloor\log_{10}(\varepsilon)\rfloor$ et $x''$ la +configuration de $\Bool^n$ obtenue depuis $(S,x)$ après $t_1$ itérations +parallèles de $G_f$. +Comme $\Gamma(f)$ est fortement connexe, il existe une +stratégie $S''$ et un entier $t_2$ tels que $x'$ est atteint depuis +$(S'',x'')$ après $t_2$ itérations de $G_f$. + +Considérons à présent la stratégie +$\tilde S=(s_0,\dots,s_{t_1-1},s''_0,\dots,s''_{t_2-1},s'_0,s'_1,s'_2,s'_3\dots)$. +Il est évident que $(s',x')$ est atteint depuis $(\tilde S,x)$ après +$t_1+t_2$ itérations parallèles de $G_f$. Puisque +$\tilde s_t=s_t$ pour $t0$. Pour +prouver que $f$ appartient à $\mathcal{R}$, il suffit de prouver +qu'il existe une stratégie $\tilde S$ telle que la distance entre +$(\tilde S,x)$ et $(S,x)$ est inférieure à $\varepsilon$ et telle que +$(\tilde S,x)$ est un point périodique. + +Soit $t_1=-\lfloor \log_{10}(\varepsilon)\rfloor$ et soit $x'$ la +configuration obtenue après $t_1$ itérations de $G_f$ depuis $(S,x)$. +D'après la proposition précédente, $\Gamma(f)$ est fortement connexe. +Ainsi, il existe une stratégie $S'$ et un nombre $t_2\in\Nats$ tels +que $x$ est atteint depuis $(S',x')$ après $t_2$ itérations de $G_f$. + +Soit alors la stratégie $\tilde S$ qui alterne les $t_1$ premiers termes +de $S$ avec les $t_2$ premiers termes de $S'$. +Ainsi $\tilde S$ est définie par +\begin{equation*} +(s_0,\dots,s_{t_1-1},s'_0,\dots,s'_{t_2-1},s_0,\dots,s_{t_1-1},s'_0,\dots,s'_{t_2-1},s_0,\dots). +\end{equation*} +Il est évident que $(\tilde S,x)$ s'obtient à partir de $(\tilde S,x)$ après +$t_1+t_2$ itérations parallèles de $G_f$. Ainsi $(\tilde S,x)$ est un point +périodique. Puisque $\tilde s_t$ est égal à $s_t$ pour $t0.$$ + +On énonce enfin le théorème suivant liant les +\glspl{vecteurDeProbabilite} (cf. glossaire) +et les \glspl{chaineDeMarkov} (cf. glossaire) +: + + +\begin{Theo}\label{th} + Si $M$ est une matrice stochastique régulière, alors $M$ + possède un unique vecteur stationnaire de probabilités $\pi$ + ($\pi.M = \pi$). + De plus, si $\pi^0$ est un \gls{vecteurDeProbabilite} + et si on définit + la suite $(\pi^{k})^{k \in \Nats}$ par + $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$ + alors la \gls{chaineDeMarkov} $\pi^k$ + converge vers $\pi$ lorsque $k$ tend vers l'infini. +\end{Theo} + + +Montrons sur un exemple jouet à deux éléments +que ce théorème permet de vérifier si la sortie d'un générateur de +nombres pseudo-aléatoires est uniformément distribuée ou non. +Soit alors $g$ et $h$ deux fonctions de $\Bool^2$ +définies par $g(x_1,x_2)=(\overline{x_1},x_1.\overline{x_2}) $ +et $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$. +% Leurs graphes d'interactions donnés en figures \ref{fig:g:inter} et \ref{fig:h:inter} +% vérifient les hypothèses du théorème~\ref{th:Adrien}. +Leurs graphes d'itérations +sont fortement connexes, ce que l'on a pu déjà vérifier aux figures +\ref{fig:g:iter} et \ref{fig:h:iter}. +\textit{A priori}, ces deux fonctions pourraient être intégrées +dans un générateur de nombres pseudo-aléatoires. Montrons que ce n'est pas le cas pour $g$ et +que cela l'est pour $h$. + +Comme le générateur \textit{Random} possède une sortie uniformément +distribuée, la stratégie est uniforme sur $\llbracket 1, 2^2 \rrbracket$, +et donc, +pour tout sommet de $\Gamma(g)$ et de $\Gamma(h)$, +chaque arc sortant de ce sommet a, parmi l'ensemble des arcs sortant +de ce sommet, une probabilité $1/4$ d'être celui qui sera traversé. +En d'autres mots, $\Gamma(g)$ est le graphe orienté d'une chaîne de Markov. +Il est facile de vérifier que la \gls{matriceDeTransitions} (cf. glossaire) +d'un tel processus +est $M_g = \frac{1}{4} \check{M}_g$, +où $\check{M}_g$ est la \gls{matriceDAdjacence} (cf. glossaire) +donnée en figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$. + +\begin{figure}[ht] + \begin{center} + \subfloat[$\check{M}_g $]{ + \begin{minipage}{0.25\textwidth} + \begin{center} + % \vspace{-3cm} + $\left( + \begin{array}{cccc} + 2 & 0 & 2 & 0 \\ + 1 & 1 & 1 & 1 \\ + 1 & 1 & 1 & 1 \\ + 1 & 1 & 1 & 1 + \end{array} + \right) + $ + \end{center} + \end{minipage} + \label{fig:g:incidence} + } + \subfloat[$\check{M}_h $]{ + \begin{minipage}{0.25\textwidth} + \begin{center} + $\left( + \begin{array}{cccc} + 2 & 0 & 2 & 0 \\ + 0 & 2 & 0 & 2 \\ + 1 & 1 & 1 & 1 \\ + 1 & 1 & 1 & 1 + \end{array} + \right) + $ + \end{center} + \end{minipage} + \label{fig:h:incidence} + } + \end{center} + \caption{Graphe des fonctions candidates avec $n=2$.} + \label{fig:xplgraph} +\end{figure} + +Les deux matrices $M_g$ et $M_h$ sont stochastiques. Pour +montrer qu'elles sont régulières il suffit de constater qu'aucun élément de +$M^2_g$ ni de $M^2_h$ n'est nul. +De plus, les vecteurs de probabilités +$\pi_g=(\frac{1}{3}, \frac{1}{6},\frac{1}{3},\frac{1}{6})$ et +$\pi_h=(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4})$ +vérifient $\pi_g M_g = \pi_g$ et +$\pi_h M_h = \pi_h$. +Alors d'après le théorème~\ref{th}, +pour n'importe quel vecteur initial de probabilités $\pi^0$, on a +$\lim_{k \to \infty} \pi^0 M^k_g = \pi_g$ et +$\lim_{k \to \infty} \pi^0 M^k_h = \pi_h$. +Ainsi, la chaîne de Markov associée à $h$ tend vers une +distribution uniforme, contrairement à celle associée à $g$. +On en déduit que $g$ ne devrait pas être itérée dans +un générateur de nombres pseudo-aléatoires. +Au contraire, +$h$ devrait pouvoir être embarquée dans l'algorithme~\ref{CI Algorithm}, +pour peu que le nombre $b$ d'itérations entre deux mesures successives +de valeurs soit suffisamment grand de sorte que +le vecteur d'état de la chaîne de Markov +ait une distribution suffisamment proche de la distribution uniforme. + + +Considérons le lemme technique suivant: +\begin{Lemma}\label{lem:stoc} +Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\Gamma(f)$, et $M$ la matrice +$2^n\times 2^n$ définie par +$M = \frac{1}{n}\check{M}$. +Alors $M$ est une matrice stochastique régulière si et seulement si +$\Gamma(f)$ est fortement connexe. +\end{Lemma} + +\begin{Proof} +On remarque tout d'abord que $M$ +est une matrice stochastique par construction. +Supposons $M$ régulière. +Il existe donc $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket +1; 2^n \rrbracket$. L'inégalité $\check{M}_{ij}^k>0$ est alors établie. +Puisque $\check{M}_{ij}^k$ est le nombre de chemins de $i$ à $j$ de longueur $k$ +dans $\Gamma(f)$ et puisque ce nombre est positif, alors +$\Gamma(f)$ est fortement connexe. + +Réciproquement si $\Gamma(f)$ +est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut être construit pour atteindre $j$ depuis $i$ en au plus $2^n$ étapes. +Il existe donc +$k_{ij} \in \llbracket 1, 2^n \rrbracket$ tel que $\check{M}_{ij}^{k_{ij}}>0$. +Comme tous les multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que +$\check{M}_{ij}^{l\times k_{ij}}>0$, +on peut conclure que, si +$k$ est le plus petit multiple commun de $\{k_{ij} \big/ i,j \in \llbracket 1, 2^n \rrbracket \}$ alors +$\forall i,j \in \llbracket 1, 2^n \rrbracket, \check{M}_{ij}^{k}>0$. +Ainsi, $\check{M}$ et donc $M$ sont régulières. +\end{Proof} + +Ces résultats permettent de formuler et de prouver le théorème suivant: + +\begin{Theo} + Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son + graphe d'itérations, $\check{M}$ sa matrice d'adjacence + et $M$ une matrice $2^n\times 2^n$ définie comme dans le lemme précédent. + Si $\Gamma(f)$ est fortement connexe, alors + la sortie du générateur de nombres pseudo-aléatoires détaillé par + l'algorithme~\ref{CI Algorithm} suit une loi qui + tend vers la distribution uniforme si + et seulement si $M$ est une matrice doublement stochastique. +\end{Theo} +\begin{Proof} + $M$ est une matrice stochastique régulière (lemme~\ref{lem:stoc}) + qui a un unique vecteur de probabilités stationnaire + (théorème \ref{th}). + Soit $\pi$ défini par + $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$. + On a $\pi M = \pi$ si et seulement si + la somme des valeurs de chaque colonne de $M$ est 1, + \textit{i.e.} si et seulement si + $M$ est doublement stochastique. +\end{Proof} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "main" +%%% End: diff --git a/glossaire.tex b/glossaire.tex new file mode 100644 index 0000000..7bf0eb6 --- /dev/null +++ b/glossaire.tex @@ -0,0 +1,82 @@ +\newglossaryentry{graphoriente}{name=Graphe orienté, description={ +Un graphe orienté $G=(S,A)$ +est défini par la donnée d'un ensemble de sommets $S$ et +d'un ensemble d'arcs $A$, +chaque arc étant représenté par un couple de sommets. +Si $x$ et $y$ sont des sommets de $S$, +le couple $(x,y)$ représente l'arc orienté allant du sommet \emph{origine} +$x$ au sommet \emph{extrémité} $y$}} + +\newglossaryentry{graphfortementconnexe}{name=Graphe fortement connexe, description={ +Un graphe orienté $G=(S,A)$ est fortement connexe si pour tout +couple de sommets $x$, $y$ de $S$ il existe un chemin reliant $x$ à $y$ +et un chemin reliant $y$ à $x$}} + +\newglossaryentry{distributionuniforme}{name=distribution uniforme, description={Les lois de distribution uniforme (ou loi uniformes continues) +forment une famille de lois à densité, caractérisées par le fait que +tous les intervalles de même longueur inclus dans le support de la loi ont +la même probabilité}} + +\newglossaryentry{partieentiere}{name=partie entière, symbol={\ensuremath{\lfloor x \rfloor}}, +description={La partie entière d'un nombre réel (notée $\lfloor x \rfloor$) est l'entier qui lui est immédiatement + inférieur ou égal}} + +\newglossaryentry{distanceHamming}{name=distance de Hamming, description= +{La distance de Hamming entre deux éléments $x=(x_1,\ldots,x_n)$ et +$y=(y_1,\ldots,y_n)$ dans $\Bool^n$ +est le nombre d'indices $i$, $1 \le i \le n$ tels que +$x_i$ diffère de $y_i$}} + +\newglossaryentry{decalageDeBits}{name=décalage de bits, +plural=décalages de bits, +description={Soit $x$ un nombre binaire de $n$ bits et $b$ un entier. +Le nombre binaire de $n$ bits $x \ll b$ (respectivement $x \gg b$) +est obtenu en +décalant les bits de $x$ de $b$ bits vers la gauche +(resp. vers la droite) et +en complétant avec des zéros à droite (resp. à gauche)}} + +\newglossaryentry{chaineDeMarkov}{name=chaîne de Markov, +plural=chaînes de Markov, description={ +On se restreint à la définition d'une chaîne de Markov homogène. Celle-ci +désigne une suite de variables aléatoires $(X_n)_{n \in \Nats}$ +à temps discret, à espace d'états discret, sans mémoire et +dont le mécanisme de transition ne change pas au cours du temps. +Formellement la propriété suivante doit être établie :\linebreak +\begin{small} + $ + % \begin{equation*} + % \begin{array}{l} + \forall n \ge 0, \forall (i_0, \ldots, i_{n-1}, i,j),\\ + \textrm{ }P(X_{n+1}=j\mid X_0=i_0, X_1=i_1, \ldots, X_{n-1}=i_{n-1}, X_{n}=i) + \textrm{ }= P(X_{n+1}=j\mid X_n=i) + % \end{array} + % \end{equation*} + $ +\end{small}}} + +\newglossaryentry{vecteurDeProbabilite}{name=vecteur de probabilités, +plural=vecteurs de probabilités, description={ +Un vecteur de probabilités est un vecteur tel que toutes ses composantes +sont positives ou nulles et leur somme vaut 1}} + +\newglossaryentry{matriceDAdjacence}{name=matrice d'adjacence, +description={La matrice d'adjacence du graphe orienté $G=(S,A)$ à $n$ sommets +est la matrice $\check{M}$ de dimensions $n \times n$ +dont l'élément $\check{M}_{ij}$ représente le nombre d'arcs d'origine $i$ et d'extrémité $j$}} + +\newglossaryentry{xor}{name={ou exclusif}, symbol={\ensuremath{\oplus}}, +description={La fonction \og ou exclusif\fg{} (XOR, notée \ensuremath{\oplus}), est l'opérateur de $\Bool^2$ dans +$\Bool$ qui prend la valeur 1 si seulement +si les deux opérandes ont des valeurs distinctes}} + +\newglossaryentry{matriceDeTransitions}{name=matrice de transitions, description= +{ + Le nombre $p_{ij}= P(X_1=j \mid X_0 =i)$ est appelé probabilité de transition + de l'état $i$ à l'état $j$ en un pas. La matrice composée des $p_{ij}$ + est la matrice de transitions associée à la chaîne de Markov $X$}} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "main" +%%% End: diff --git a/gray.tex b/gray.tex new file mode 100644 index 0000000..129e2df --- /dev/null +++ b/gray.tex @@ -0,0 +1,245 @@ +On a vu dans la partie précédente que pour avoir un générateur à sortie +uniforme, il est nécessaire que la matrice d'adjacence du graphe d'itération du +système soit doublement stochastique. Nous présentons dans cette partie une +méthode permettant de générer de telles matrices. + +Les approches théoriques basées sur la programmation logique par contraintes sur +domaines finis ne sont pas envisageables en pratique dès que la taille des +matrices considérées devient suffisamment grande. + +Une approche plus pragmatique consiste à supprimer un cycle hamiltonien dans le +graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graphe une +arête sortante et une arête entrante. + +\begin{xpl} + On considère le + $3$-cube dans lequel le cycle hamiltonien défini par la séquence + $000,100,101,001,011,111,110,010,000$ a été supprimé. + Ceci correspond à la fonction $f^*$ définie par +$$f^*(x_1,x_2,x_3)= +(x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2}, +\overline{x_1}\overline{x_3} + x_1x_2). +$$ + +Le graphe des itérations chaotiques de $f^*$ est représenté à la +Figure~\ref{fig:iteration:f*}. +La matrice de Markov correspondante est donnée à +la figure~\ref{fig:markov:f*}. + +\begin{figure}[ht] + \begin{center} + \subfloat[Graphe des itérations chaotiques de $f^*$. + \label{fig:iteration:f*}]{ + \begin{minipage}{0.55\linewidth} + \centering + \includegraphics[width=\columnwidth]{images/iter_f}% + \end{minipage} + }% + \subfloat[Matrice de Markov du graphe d'itérations chaotiques de + $f^*$\label{fig:markov:f*}]{% + \begin{minipage}{0.35\linewidth} + \begin{scriptsize} + \begin{center} + $ \dfrac{1}{4} \left( + \begin{array}{cccccccc} + 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ + + 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ + + 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ + + 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ + + 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ + + 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ + + 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ + + 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ + + \end{array} \right) $ + \end{center} + \end{scriptsize} + \end{minipage} + }% + \caption{Représentations de $f^*(x_1,x_2,x_3)= + (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2}, + \overline{x_1}\overline{x_3} + x_1x_2)$.}\label{fig1} + \end{center} +\end{figure} +\end{xpl} + +\subsection{Suppression des cycles hamiltoniens} +\label{sec:hamiltonian} + +Dans un premier temps, nous montrons en section~\ref{sub:removing:theory} que la +suppression d'un cycle hamiltonien produit bien des matrices doublement +stochastiques. Nous établissons ensuite le lien avec les codes de Gray +équilibrés. + +\subsubsection{Aspects théoriques} +\label{sub:removing:theory} + +Nous donnons deux résultats complémentaires, reliant la suppression d'un cycle +hamiltonien du $n$-cube, les matrices doublement stochastiques et la forte +connexité du graphe d'itérations. + +\begin{Theo}\label{th:supprCH} + La suppression d'un cycle hamiltonien dans une matrice de Markov $M$, issue du + $n$-cube, produit une matrice doublement stochastique. +\end{Theo} +\begin{Proof} + +Un cycle hamiltonien passe par chaque n{\oe}ud une et une seule fois. +Pour chaque n{\oe}ud $v$ dans le $n$-cube $C_1$, +une arête entrante $(o,v)$ et une arête sortante $(v,e)$ +est ainsi enlevée. +Considérons un autre $n$-cube $C_2$ auquel on ajoute les arêtes +pour le rendre complet. La matrice de Markov $M$ correspondante est +remplie de $\frac{1}{2^n}$ et est doublement stochastique. +Comme on enlève exactement une arête sortante $(v,e)$ +à chaque n{\oe}ud $v$ dans $C_1$, on enlève ainsi dans +$C_2$ les $2^{n-1}$ arêtes issues de $v$ et +relatives aux parties de $\{1,\ldots,n\}$ qui +contiennent $e$. Cela revient à annuler +dans la matrice $M$ les $2^{n-1}$ coefficients correspondants et ajouter +$1/2$ à l'élément $M_{vv}$. +La matrice $M$ reste stochastique. +On effectue un raisonnement similaire pour les arêtes entrantes: +comme on enlève exactement une arête entrante $(o,v)$ pour chaque +n{\oe}ud $v$ dans $C_1$, dans $C_2$, ce sont exactement +$2^{n-1}$ arêtes menant à $v$ qui sont enlevées. +Dans $M$ les $2^{n-1}$ coefficients correspondants sont mis à 0 et +$M_{vv}$ vaut alors $\frac{2^{n-1} +1}{2}$. +$M$ est donc doublement stochastique. +\end{Proof} + + + +\begin{Theo}\label{th:grapheFC} + Le graphe d'itérations issu du $n$-cube, auquel un cycle hamiltonien est + enlevé, est fortement connexe. +\end{Theo} + + +\begin{Proof} +On considère les deux $n$-cubes $C_1$ et $C_2$ définis +dans la preuve du théorème~\ref{th:supprCH}. +Dans $C_1$ on considère le cycle inverse $r$ du cycle +hamiltonien $c$. +Aucun arc n'appartient à la fois à $r$ et à $c$: +en effet, sinon $c$ contiendrait un n{\oe}ud deux fois. +Ainsi aucune arête de $r$ n'est enlevée dans $C_1$. +Le cycle $r$ est évidement un cycle hamiltonien et contient tous les n{\oe}uds. +Tous les n{\oe}uds de $C_1$ dans lequel $c$ a été enlevé sont accessibles +depuis n'importe quel n{\oe}ud. Le graphe des itérations $\Gamma$ qui +étend le précédent graphe est ainsi fortement connexe. + +\end{Proof} + + + +Les preuves, relativement directes, sont laissées en exercices au lecteur. Par +contre, ce qui est moins aisé est la génération de cycles hamiltoniens dans le +$n$-cube, ce qui revient à trouver des \emph{codes de Gray cycliques}. On +rappelle que les codes de Gray sont des séquences de mots binaires de taille +fixe ($n$), dont les éléments successifs ne différent que par un seul bit. Un +code de Gray est \emph{cyclique} si le premier élément et le dernier ne +différent que par un seul bit. + +\subsection{Lien avec les codes de Gray cycliques (totalement) équilibrés} +\label{sub:gray} + +La borne inférieure du nombre de codes de Gray ($\left(\frac{n*\log2}{e \log + \log n}\times(1 - o(1))\right)^{2^n}$), donnée dans~\cite{Feder2009NTB}, +indique une explosion combinatoire pour notre recherche. Afin de contourner +cette difficulté, nous nous restreignons aux codes induisant un graphe +d'itérations $\Gamma(f)$ \emph{uniforme}. Cette uniformité se traduit par des +nombres d'arcs équilibrés entre les \emph{dimensions} du graphe, la dimension +$i$ correspondant aux seules variations du bit $i$ (parmi les $n$ bits au +total). Cette approche revient à chercher des codes de Gray cycliques +\emph{équilibrés}. + +Un code de Gray équilibré peut être défini de la façon suivante : + +\begin{Def}[Code de Gray cyclique équilibré]\label{def:grayequ} + Soit $L = w_1, w_2, \dots, w_{2^n}$ la séquence d'un code de Gray cyclique à + $n$ bits. Soit $S = s_1, s_2, \dots, s_{2^n}$ la séquence des transitions où + $s_i$, $1 \le i \le 2^n$ est l'indice du seul bit qui varie entre les mots + $w_i$ et $w_{i+1}$. Enfin, soit $\textit{NT}_n : \{1,\dots, n\} \rightarrow + \{0, \ldots, 2^n\}$ la fonction qui au paramètre $i$ associe le \emph{nombre + de transitions} présentes dans la séquence $L$ pour le bit $i$, c'est-à-dire + le nombre d'occurrences de $i$ dans $S$. + + Le code $L$ est \textbf{équilibré} si $\forall + i,j\in\{1,...,n\},~|\textit{NT}_n(i) - \textit{NT}_n(j)| \le 2$. Il est + \textbf{totalement équilibré} si $\forall + i\in\{1,...,n\},~\textit{NT}_n(i)=\frac{2^n}{n}$. +\end{Def} + +On peut donc déjà déduire qu'il ne peut exister des codes de Gray totalement +équilibrés que pour les systèmes ayant un nombre d'éléments $n=2^k, k>0$. De +plus, comme dans tout code de Gray cyclique, $\textit{NT}_n(i)$ est pair +$\forall i\in\{1,...,n\}$, alors les systèmes ayant un nombre d'éléments +différent de $2^k$, ne peuvent avoir que des codes de Gray équilibrés avec +$\textit{NT}_n(i)=\lfloor\frac{2^n}{n}\rfloor$ ou +$\textit{NT}_n(i)=\lceil\frac{2^n}{n}\rceil, \forall i\in\{1,...,n\}$ et +vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$. + +\begin{xpl} + Soit $L^*=000,100,101,001,011,111,110,010$ le code de Gray correspondant au + cycle hamiltonien enlevé de $f^*$. Sa séquence des transitions est \linebreak + $S=3,1,3,2,3,1,3,2$ et les nombres de transitions sont $\textit{TC}_3(1)= + \textit{TC}_3(2)=2$ et $\textit{TC}_3(3)=4$. Un tel code est équilibré. + + Si l'on considère maintenant $L^4=$ 0000, 0010, 0110, 1110, 1111, 0111, 0011, + 0001, 0101, 0100, 1100, 1101, 1001, 1011, 1010, 1000, un code de Gray + cyclique. En construisant la séquence $S=$ 2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4, + on constate que $\forall + i\in\{1,..,4\},~\textit{TC}_4(i)=4$ et donc que + ce code est totalement équilibré. +\end{xpl} + +\subsection{Génération de codes de Gray équilibrés par induction} +\label{sec:induction} + +Dans leur article de 2004~\cite{ZanSup04}, Zanten et Suparta proposent un +algorithme inductif pour générer des codes de Gray équilibrés de $n$ bits à +partir de codes de $n-2$ bits. Cependant, leur méthode n'est pas +constructive. En effet, elle effectue des manipulations sur un partitionnement du +code de Gray initial de $n-2$ bits pour obtenir un code de Gray sur $n$ bits, +mais le résultat n'est pas systématiquement équilibré. Il est donc nécessaire +d'évaluer les résultats obtenus à partir de tous les partitionnements réalisables +en suivant les contraintes spécifiées. Or, le nombre de possibilités augmente +exponentiellement (voir~\cite{Mons14} pour l'évaluation détaillée), ce qui rend +déraisonnable tout parcours exhaustif. Une amélioration proposée +dans~\cite{Mons14} permet de réduire le nombre de partitionnements considérés, +mais l'ordre de grandeur reste similaire. On constate donc clairement ici la +nécessité de trouver des algorithmes de génération de codes de Gray équilibrés +plus efficaces. Ce problème représente une des voies que nous souhaitons +explorer dans la suite de nos travaux. + +Le tableau~\ref{table:nbFunc} donne le nombre de fonctions différentes +compatibles avec les codes de Gray équilibrés générés par l'approche précédente +selon le nombre de bits. Il donne donc la taille de la classe des générateurs +pouvant être produits. Les cas 7 et 8 ne sont que des bornes minimales basées +sur des sous-ensembles des partitionnements possibles. + +\begin{table}[table:nbFunc]{Nombre de générateurs selon le nombre de bits.} + \begin{center} + \begin{tabular}{|l|c|c|c|c|c|} + \hline + $n$ & 4 & 5 & 6 & 7 & 8 \\ + \hline + nb. de fonctions & 1 & 2 & 1332 & > 2300 & > 4500 \\ + \hline + \end{tabular} + \end{center} +\end{table} + + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "main" +%%% End: diff --git a/images/Gi.dot b/images/Gi.dot new file mode 100644 index 0000000..cf9e416 --- /dev/null +++ b/images/Gi.dot @@ -0,0 +1,9 @@ +digraph { +1 -> 1 [label=" -"] +1 -> 4 [label=" +-"] +2 -> 2 [label=" -"] +2 -> 4 [label=" +-"] +3 -> 3 [label=" -"] +3 -> 4 [label=" +-"] +4 -> 4 [label=" +-"] +} \ No newline at end of file diff --git a/images/g-eps-converted-to.pdf b/images/g-eps-converted-to.pdf new file mode 100644 index 0000000..8973679 Binary files /dev/null and b/images/g-eps-converted-to.pdf differ diff --git a/images/g.dot b/images/g.dot new file mode 100644 index 0000000..ae54226 --- /dev/null +++ b/images/g.dot @@ -0,0 +1,21 @@ +digraph { +00 [shape="none",label="00", pos="0,0!"]; +01 [shape="none",label="01", pos="0,2!"]; +10 [shape="none",label="10", pos="2,0!"]; +11 [shape="none", label="11", pos="2,2!"]; + 00 -> 10 [headlabel="{1},{1,2}", labeldistance=5.0,labelangle=-15] + 01 -> 00 [headlabel="{2}", labeldistance=5.0,labelangle=15] + 01 -> 11 [headlabel="{1}", labeldistance=5.0,labelangle=-15] + 01 -> 10 [headlabel="{1,2}", labeldistance=5.0,labelangle=-15] + 10 -> 11 [headlabel="{2}", labeldistance=5.0,labelangle=-15] + 10 -> 00 [headlabel="{1}", labeldistance=5.0,labelangle=-15] + 10 -> 01 [headlabel="{1,2}", labeldistance=5.0,labelangle=-15] + 11 -> 10 [headlabel="{2}", labeldistance=5.0,labelangle=-15] + 11 -> 01 [headlabel="{1}", labeldistance=5.0,labelangle=-15] + 11 -> 00 [headlabel="{1,2}", labeldistance=5.0,labelangle=-15] + 01:nw -> 01:sw [headlabel="∅", labeldistance=2.5, labelangle=-90] + 00:nw -> 00:sw [headlabel="∅,{2}", labeldistance=2.5, labelangle=-90] + 11:ne -> 11:se [headlabel="∅",labeldistance=2.5,labelangle=90] + 10:ne -> 10:se [headlabel="∅",labeldistance=2.5,labelangle=90] + +} diff --git a/images/g.eps b/images/g.eps new file mode 100644 index 0000000..975515b --- /dev/null +++ b/images/g.eps @@ -0,0 +1,476 @@ +%!PS-Adobe-3.0 +%%Creator: graphviz version 2.36.0 (20140111.2315) +%%Title: %3 +%%Pages: (atend) +%%BoundingBox: (atend) +%%EndComments +save +%%BeginProlog +/DotDict 200 dict def +DotDict begin + +/setupLatin1 { +mark +/EncodingVector 256 array def + EncodingVector 0 + +ISOLatin1Encoding 0 255 getinterval putinterval +EncodingVector 45 /hyphen put + +% Set up ISO Latin 1 character encoding +/starnetISO { + dup dup findfont dup length dict begin + { 1 index /FID ne { def }{ pop pop } ifelse + } forall + /Encoding EncodingVector def + currentdict end definefont +} def +/Times-Roman starnetISO def +/Times-Italic starnetISO def +/Times-Bold starnetISO def +/Times-BoldItalic starnetISO def +/Helvetica starnetISO def +/Helvetica-Oblique starnetISO def +/Helvetica-Bold starnetISO def +/Helvetica-BoldOblique starnetISO def +/Courier starnetISO def +/Courier-Oblique starnetISO def +/Courier-Bold starnetISO def +/Courier-BoldOblique starnetISO def +cleartomark +} bind def + +%%BeginResource: procset graphviz 0 0 +/coord-font-family /Times-Roman def +/default-font-family /Times-Roman def +/coordfont coord-font-family findfont 8 scalefont def + +/InvScaleFactor 1.0 def +/set_scale { + dup 1 exch div /InvScaleFactor exch def + scale +} bind def + +% styles +/solid { [] 0 setdash } bind def +/dashed { [9 InvScaleFactor mul dup ] 0 setdash } bind def +/dotted { [1 InvScaleFactor mul 6 InvScaleFactor mul] 0 setdash } bind def +/invis {/fill {newpath} def /stroke {newpath} def /show {pop newpath} def} bind def +/bold { 2 setlinewidth } bind def +/filled { } bind def +/unfilled { } bind def +/rounded { } bind def +/diagonals { } bind def +/tapered { } bind def + +% hooks for setting color +/nodecolor { sethsbcolor } bind def +/edgecolor { sethsbcolor } bind def +/graphcolor { sethsbcolor } bind def +/nopcolor {pop pop pop} bind def + +/beginpage { % i j npages + /npages exch def + /j exch def + /i exch def + /str 10 string def + npages 1 gt { + gsave + coordfont setfont + 0 0 moveto + (\() show i str cvs show (,) show j str cvs show (\)) show + grestore + } if +} bind def + +/set_font { + findfont exch + scalefont setfont +} def + +% draw text fitted to its expected width +/alignedtext { % width text + /text exch def + /width exch def + gsave + width 0 gt { + [] 0 setdash + text stringwidth pop width exch sub text length div 0 text ashow + } if + grestore +} def + +/boxprim { % xcorner ycorner xsize ysize + 4 2 roll + moveto + 2 copy + exch 0 rlineto + 0 exch rlineto + pop neg 0 rlineto + closepath +} bind def + +/ellipse_path { + /ry exch def + /rx exch def + /y exch def + /x exch def + matrix currentmatrix + newpath + x y translate + rx ry scale + 0 0 1 0 360 arc + setmatrix +} bind def + +/endpage { showpage } bind def +/showpage { } def + +/layercolorseq + [ % layer color sequence - darkest to lightest + [0 0 0] + [.2 .8 .8] + [.4 .8 .8] + [.6 .8 .8] + [.8 .8 .8] + ] +def + +/layerlen layercolorseq length def + +/setlayer {/maxlayer exch def /curlayer exch def + layercolorseq curlayer 1 sub layerlen mod get + aload pop sethsbcolor + /nodecolor {nopcolor} def + /edgecolor {nopcolor} def + /graphcolor {nopcolor} def +} bind def + +/onlayer { curlayer ne {invis} if } def + +/onlayers { + /myupper exch def + /mylower exch def + curlayer mylower lt + curlayer myupper gt + or + {invis} if +} def + +/curlayer 0 def + +%%EndResource +%%EndProlog +%%BeginSetup +14 default-font-family set_font +1 setmiterlimit +% /arrowlength 10 def +% /arrowwidth 5 def + +% make sure pdfmark is harmless for PS-interpreters other than Distiller +/pdfmark where {pop} {userdict /pdfmark /cleartomark load put} ifelse +% make '<<' and '>>' safe on PS Level 1 devices +/languagelevel where {pop languagelevel}{1} ifelse +2 lt { + userdict (<<) cvn ([) cvn load put + userdict (>>) cvn ([) cvn load put +} if + +%%EndSetup +setupLatin1 +%%Page: 1 1 +%%PageBoundingBox: 36 36 265 245 +%%PageOrientation: Portrait +0 0 1 beginpage +gsave +36 36 229 209 boxprim clip newpath +1 1 set_scale 0 rotate 40 40 translate +% 00 +gsave +0 0 0 nodecolor +14 /Times-Roman set_font +38 24.89 moveto 14 (00) alignedtext +grestore +% 00->00 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 27 46.59 moveto +12 55.59 0 55.59 0 28.59 curveto +0 7.5 7.32 2.88 17.68 6.17 curveto +stroke +0 0 0 edgecolor +newpath 16.47 9.46 moveto +27 10.59 lineto +19.47 3.14 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 16.47 9.46 moveto +27 10.59 lineto +19.47 3.14 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +3.63 33.99 moveto 21 ({2}) alignedtext +grestore +% 10 +gsave +0 0 0 nodecolor +14 /Times-Roman set_font +182 24.89 moveto 14 (10) alignedtext +grestore +% 00->10 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 72.09 34 moveto +94.47 35.56 126.5 35.76 151.37 34.6 curveto +stroke +0 0 0 edgecolor +newpath 151.76 38.09 moveto +161.55 34.03 lineto +151.36 31.1 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 151.76 38.09 moveto +161.55 34.03 lineto +151.36 31.1 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +86.56 45.98 moveto 55 ({1},{1,2}) alignedtext +grestore +% 01 +gsave +0 0 0 nodecolor +14 /Times-Roman set_font +38 168.89 moveto 14 (01) alignedtext +grestore +% 01->00 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 45 154.35 moveto +45 129.79 45 85.84 45 56.95 curveto +stroke +0 0 0 edgecolor +newpath 48.5 56.68 moveto +45 46.68 lineto +41.5 56.68 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 48.5 56.68 moveto +45 46.68 lineto +41.5 56.68 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +21.56 91.28 moveto 21 ({2}) alignedtext +grestore +% 01->10 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 70.08 154.56 moveto +98.7 129.24 144.65 83.32 170.31 54.41 curveto +stroke +0 0 0 edgecolor +newpath 173.06 56.58 moveto +176.98 46.74 lineto +167.78 51.99 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 173.06 56.58 moveto +176.98 46.74 lineto +167.78 51.99 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +139.56 87.98 moveto 31 ({1,2}) alignedtext +grestore +% 11 +gsave +0 0 0 nodecolor +14 /Times-Roman set_font +182 168.89 moveto 14 (11) alignedtext +grestore +% 01->11 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 72.09 178 moveto +94.47 179.56 126.5 179.76 151.37 178.6 curveto +stroke +0 0 0 edgecolor +newpath 151.76 182.09 moveto +161.55 178.03 lineto +151.36 175.1 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 151.76 182.09 moveto +161.55 178.03 lineto +151.36 175.1 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +103.56 189.98 moveto 21 ({1}) alignedtext +grestore +% 10->00 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 161.91 23.18 moveto +139.53 21.63 107.5 21.42 82.63 22.58 curveto +stroke +0 0 0 edgecolor +newpath 82.24 19.09 moveto +72.45 23.15 lineto +82.64 26.08 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 82.24 19.09 moveto +72.45 23.15 lineto +82.64 26.08 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +109.44 3.8 moveto 21 ({1}) alignedtext +grestore +% 10->01 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 163.92 46.63 moveto +135.3 71.94 89.35 117.86 63.69 146.77 curveto +stroke +0 0 0 edgecolor +newpath 60.94 144.6 moveto +57.02 154.44 lineto +66.22 149.19 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 60.94 144.6 moveto +57.02 154.44 lineto +66.22 149.19 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +63.44 105.8 moveto 31 ({1,2}) alignedtext +grestore +% 10->11 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 184.33 46.83 moveto +181.87 71.39 181.59 115.34 183.5 144.24 curveto +stroke +0 0 0 edgecolor +newpath 180.04 144.82 moveto +184.34 154.5 lineto +187.02 144.25 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 180.04 144.82 moveto +184.34 154.5 lineto +187.02 144.25 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +157.01 103.72 moveto 21 ({2}) alignedtext +grestore +% 11->00 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 170.76 154.35 moveto +145.34 128.93 99.13 82.72 70.36 53.95 curveto +stroke +0 0 0 edgecolor +newpath 72.64 51.28 moveto +63.09 46.68 lineto +67.69 56.23 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 72.64 51.28 moveto +63.09 46.68 lineto +67.69 56.23 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +90.89 67.98 moveto 31 ({1,2}) alignedtext +grestore +% 11->01 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 161.91 167.18 moveto +139.53 165.63 107.5 165.42 82.63 166.58 curveto +stroke +0 0 0 edgecolor +newpath 82.24 163.09 moveto +72.45 167.15 lineto +82.64 170.08 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 82.24 163.09 moveto +72.45 167.15 lineto +82.64 170.08 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +109.44 147.8 moveto 21 ({1}) alignedtext +grestore +% 11->10 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 193.67 154.35 moveto +196.13 129.79 196.41 85.84 194.5 56.95 curveto +stroke +0 0 0 edgecolor +newpath 197.96 56.36 moveto +193.66 46.68 lineto +190.98 56.93 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 197.96 56.36 moveto +193.66 46.68 lineto +190.98 56.93 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +199.99 90.06 moveto 21 ({2}) alignedtext +grestore +endpage +showpage +grestore +%%PageTrailer +%%EndPage: 1 +%%Trailer +%%Pages: 1 +%%BoundingBox: 36 36 265 245 +end +restore +%%EOF diff --git a/images/gp.dot b/images/gp.dot new file mode 100644 index 0000000..161e9d2 --- /dev/null +++ b/images/gp.dot @@ -0,0 +1,5 @@ +digraph{ + 1 -> 1 [label=" -"] + 1 -> 2 [label=" +"] + 2 -> 2 [label=" -"] +} \ No newline at end of file diff --git a/images/h-eps-converted-to.pdf b/images/h-eps-converted-to.pdf new file mode 100644 index 0000000..6f5af57 Binary files /dev/null and b/images/h-eps-converted-to.pdf differ diff --git a/images/h.dot b/images/h.dot new file mode 100644 index 0000000..95e3145 --- /dev/null +++ b/images/h.dot @@ -0,0 +1,18 @@ +digraph { +00 [shape="none",label="00", pos="0,0!"]; +01 [shape="none",label="01", pos="0,2!"]; +10 [shape="none",label="10", pos="2,0!"]; +11 [shape="none", label="11", pos="2,2!"]; + 00 -> 10 [headlabel="{1},{1,2}", labeldistance=5.0,labelangle=-15] + 01 -> 11 [headlabel="{1},{1,2}", labeldistance=5.0,labelangle=-15] + 10 -> 11 [headlabel="{2}", labeldistance=5.0,labelangle=-15] + 10 -> 00 [headlabel="{1}", labeldistance=5.0,labelangle=-15] + 10 -> 01 [headlabel="{1,2}", labeldistance=5.0,labelangle=-15] + 11 -> 00 [headlabel="{1,2}", labeldistance=5.0,labelangle=-15] + 11 -> 10 [headlabel="{2}", labeldistance=5.0,labelangle=-15] + 11 -> 01 [headlabel="{1}", labeldistance=5.0,labelangle=-15] + 01:nw -> 01:sw [headlabel="∅,{2}", labeldistance=2.5, labelangle=-90] + 00:nw -> 00:sw [headlabel="∅,{2}", labeldistance=2.5, labelangle=-90] + 11:ne -> 11:se [headlabel="∅",labeldistance=2.5,labelangle=90] + 10:ne -> 10:se [headlabel="∅",labeldistance=2.5,labelangle=90] +} diff --git a/images/h.eps b/images/h.eps new file mode 100644 index 0000000..eddf9e2 --- /dev/null +++ b/images/h.eps @@ -0,0 +1,454 @@ +%!PS-Adobe-3.0 +%%Creator: graphviz version 2.36.0 (20140111.2315) +%%Title: %3 +%%Pages: (atend) +%%BoundingBox: (atend) +%%EndComments +save +%%BeginProlog +/DotDict 200 dict def +DotDict begin + +/setupLatin1 { +mark +/EncodingVector 256 array def + EncodingVector 0 + +ISOLatin1Encoding 0 255 getinterval putinterval +EncodingVector 45 /hyphen put + +% Set up ISO Latin 1 character encoding +/starnetISO { + dup dup findfont dup length dict begin + { 1 index /FID ne { def }{ pop pop } ifelse + } forall + /Encoding EncodingVector def + currentdict end definefont +} def +/Times-Roman starnetISO def +/Times-Italic starnetISO def +/Times-Bold starnetISO def +/Times-BoldItalic starnetISO def +/Helvetica starnetISO def +/Helvetica-Oblique starnetISO def +/Helvetica-Bold starnetISO def +/Helvetica-BoldOblique starnetISO def +/Courier starnetISO def +/Courier-Oblique starnetISO def +/Courier-Bold starnetISO def +/Courier-BoldOblique starnetISO def +cleartomark +} bind def + +%%BeginResource: procset graphviz 0 0 +/coord-font-family /Times-Roman def +/default-font-family /Times-Roman def +/coordfont coord-font-family findfont 8 scalefont def + +/InvScaleFactor 1.0 def +/set_scale { + dup 1 exch div /InvScaleFactor exch def + scale +} bind def + +% styles +/solid { [] 0 setdash } bind def +/dashed { [9 InvScaleFactor mul dup ] 0 setdash } bind def +/dotted { [1 InvScaleFactor mul 6 InvScaleFactor mul] 0 setdash } bind def +/invis {/fill {newpath} def /stroke {newpath} def /show {pop newpath} def} bind def +/bold { 2 setlinewidth } bind def +/filled { } bind def +/unfilled { } bind def +/rounded { } bind def +/diagonals { } bind def +/tapered { } bind def + +% hooks for setting color +/nodecolor { sethsbcolor } bind def +/edgecolor { sethsbcolor } bind def +/graphcolor { sethsbcolor } bind def +/nopcolor {pop pop pop} bind def + +/beginpage { % i j npages + /npages exch def + /j exch def + /i exch def + /str 10 string def + npages 1 gt { + gsave + coordfont setfont + 0 0 moveto + (\() show i str cvs show (,) show j str cvs show (\)) show + grestore + } if +} bind def + +/set_font { + findfont exch + scalefont setfont +} def + +% draw text fitted to its expected width +/alignedtext { % width text + /text exch def + /width exch def + gsave + width 0 gt { + [] 0 setdash + text stringwidth pop width exch sub text length div 0 text ashow + } if + grestore +} def + +/boxprim { % xcorner ycorner xsize ysize + 4 2 roll + moveto + 2 copy + exch 0 rlineto + 0 exch rlineto + pop neg 0 rlineto + closepath +} bind def + +/ellipse_path { + /ry exch def + /rx exch def + /y exch def + /x exch def + matrix currentmatrix + newpath + x y translate + rx ry scale + 0 0 1 0 360 arc + setmatrix +} bind def + +/endpage { showpage } bind def +/showpage { } def + +/layercolorseq + [ % layer color sequence - darkest to lightest + [0 0 0] + [.2 .8 .8] + [.4 .8 .8] + [.6 .8 .8] + [.8 .8 .8] + ] +def + +/layerlen layercolorseq length def + +/setlayer {/maxlayer exch def /curlayer exch def + layercolorseq curlayer 1 sub layerlen mod get + aload pop sethsbcolor + /nodecolor {nopcolor} def + /edgecolor {nopcolor} def + /graphcolor {nopcolor} def +} bind def + +/onlayer { curlayer ne {invis} if } def + +/onlayers { + /myupper exch def + /mylower exch def + curlayer mylower lt + curlayer myupper gt + or + {invis} if +} def + +/curlayer 0 def + +%%EndResource +%%EndProlog +%%BeginSetup +14 default-font-family set_font +1 setmiterlimit +% /arrowlength 10 def +% /arrowwidth 5 def + +% make sure pdfmark is harmless for PS-interpreters other than Distiller +/pdfmark where {pop} {userdict /pdfmark /cleartomark load put} ifelse +% make '<<' and '>>' safe on PS Level 1 devices +/languagelevel where {pop languagelevel}{1} ifelse +2 lt { + userdict (<<) cvn ([) cvn load put + userdict (>>) cvn ([) cvn load put +} if + +%%EndSetup +setupLatin1 +%%Page: 1 1 +%%PageBoundingBox: 36 36 266 245 +%%PageOrientation: Portrait +0 0 1 beginpage +gsave +36 36 230 209 boxprim clip newpath +1 1 set_scale 0 rotate 40 40 translate +% 00 +gsave +0 0 0 nodecolor +14 /Times-Roman set_font +38.73 24.89 moveto 14 (00) alignedtext +grestore +% 00->00 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 27.73 46.59 moveto +12.73 55.59 .73 55.59 .73 28.59 curveto +.73 7.5 8.05 2.88 18.41 6.17 curveto +stroke +0 0 0 edgecolor +newpath 17.19 9.46 moveto +27.73 10.59 lineto +20.19 3.14 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 17.19 9.46 moveto +27.73 10.59 lineto +20.19 3.14 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +0 29.47 moveto 34 ({2},∅) alignedtext +grestore +% 10 +gsave +0 0 0 nodecolor +14 /Times-Roman set_font +182.73 24.89 moveto 14 (10) alignedtext +grestore +% 00->10 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 72.81 34 moveto +95.19 35.56 127.22 35.76 152.1 34.6 curveto +stroke +0 0 0 edgecolor +newpath 152.49 38.09 moveto +162.27 34.03 lineto +152.09 31.1 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 152.49 38.09 moveto +162.27 34.03 lineto +152.09 31.1 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +87.29 45.98 moveto 55 ({1},{1,2}) alignedtext +grestore +% 01 +gsave +0 0 0 nodecolor +14 /Times-Roman set_font +38.73 168.89 moveto 14 (01) alignedtext +grestore +% 01->01 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 27.73 190.59 moveto +12.73 199.59 .73 199.59 .73 172.59 curveto +.73 151.5 8.05 146.88 18.41 150.17 curveto +stroke +0 0 0 edgecolor +newpath 17.19 153.46 moveto +27.73 154.59 lineto +20.19 147.14 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 17.19 153.46 moveto +27.73 154.59 lineto +20.19 147.14 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +6.5 173.47 moveto 21 ({2}) alignedtext +grestore +% 11 +gsave +0 0 0 nodecolor +14 /Times-Roman set_font +182.73 168.89 moveto 14 (11) alignedtext +grestore +% 01->11 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 72.81 178 moveto +95.19 179.56 127.22 179.76 152.1 178.6 curveto +stroke +0 0 0 edgecolor +newpath 152.49 182.09 moveto +162.27 178.03 lineto +152.09 175.1 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 152.49 182.09 moveto +162.27 178.03 lineto +152.09 175.1 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +87.29 189.98 moveto 55 ({1},{1,2}) alignedtext +grestore +% 10->00 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 162.64 23.18 moveto +140.26 21.63 108.23 21.42 83.35 22.58 curveto +stroke +0 0 0 edgecolor +newpath 82.96 19.09 moveto +73.18 23.15 lineto +83.36 26.08 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 82.96 19.09 moveto +73.18 23.15 lineto +83.36 26.08 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +110.16 3.8 moveto 21 ({1}) alignedtext +grestore +% 10->01 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 171.49 46.83 moveto +146.06 72.26 99.85 118.47 71.08 147.23 curveto +stroke +0 0 0 edgecolor +newpath 68.41 144.96 moveto +63.81 154.5 lineto +73.36 149.91 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 68.41 144.96 moveto +63.81 154.5 lineto +73.36 149.91 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +73.31 107.5 moveto 31 ({1,2}) alignedtext +grestore +% 10->11 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 185.05 46.83 moveto +182.59 71.39 182.32 115.34 184.23 144.24 curveto +stroke +0 0 0 edgecolor +newpath 180.76 144.82 moveto +185.07 154.5 lineto +187.74 144.25 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 180.76 144.82 moveto +185.07 154.5 lineto +187.74 144.25 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +157.73 103.72 moveto 21 ({2}) alignedtext +grestore +% 11->00 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 171.49 154.35 moveto +146.06 128.93 99.85 82.72 71.08 53.95 curveto +stroke +0 0 0 edgecolor +newpath 73.36 51.28 moveto +63.81 46.68 lineto +68.41 56.23 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 73.36 51.28 moveto +63.81 46.68 lineto +68.41 56.23 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +91.62 67.98 moveto 31 ({1,2}) alignedtext +grestore +% 11->01 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 162.64 167.18 moveto +140.26 165.63 108.23 165.42 83.35 166.58 curveto +stroke +0 0 0 edgecolor +newpath 82.96 163.09 moveto +73.18 167.15 lineto +83.36 170.08 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 82.96 163.09 moveto +73.18 167.15 lineto +83.36 170.08 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +110.16 147.8 moveto 21 ({1}) alignedtext +grestore +% 11->10 +gsave +1 setlinewidth +0 0 0 edgecolor +newpath 194.4 154.35 moveto +196.86 129.79 197.13 85.84 195.22 56.95 curveto +stroke +0 0 0 edgecolor +newpath 198.69 56.36 moveto +194.38 46.68 lineto +191.71 56.93 lineto +closepath fill +1 setlinewidth +solid +0 0 0 edgecolor +newpath 198.69 56.36 moveto +194.38 46.68 lineto +191.71 56.93 lineto +closepath stroke +0 0 0 edgecolor +14 /Times-Roman set_font +200.72 90.06 moveto 21 ({2}) alignedtext +grestore +endpage +showpage +grestore +%%PageTrailer +%%EndPage: 1 +%%Trailer +%%Pages: 1 +%%BoundingBox: 36 36 266 245 +end +restore +%%EOF diff --git a/images/hp.dot b/images/hp.dot new file mode 100644 index 0000000..a8145cf --- /dev/null +++ b/images/hp.dot @@ -0,0 +1,5 @@ +digraph{ + 1 -> 1 [label=" -"] + 1 -> 2 [label=" +-"] + 2 -> 2 [label=" +-"] +} \ No newline at end of file diff --git a/images/iter_f.dot b/images/iter_f.dot new file mode 100644 index 0000000..3f3ab3a --- /dev/null +++ b/images/iter_f.dot @@ -0,0 +1,42 @@ +digraph { +000 [shape="none",label="000", pos="2,4!"] +001 [shape="none",label="001", pos="0,6!"] +010 [shape="none",label="010", pos="4,4!"] +011 [shape="none",label="011", pos="6,6!"] +100 [shape="none",label="100", pos="2,2!"] +101 [shape="none",label="101", pos="0,0!"] +110 [shape="none",label="110", pos="4,2!"] +111 [shape="none",label="111", pos="6,0!"] +000:nw -> 000:sw [headlabel="∅,{1}", labeldistance=1.5,labelangle=-90] +000 -> 001 [headlabel="{3}{1,3}", labeldistance=5.0,labelangle=-15] +000 -> 010 [headlabel="{2}{1,2}", labeldistance=5.0,labelangle=15] +000 -> 011 [headlabel="{2,3}{1,2,3}", labeldistance=5.0,labelangle=-15] +001 -> 000 [headlabel="{3}{2,3}", labeldistance=7.0,labelangle=-15] +001:nw -> 001:sw [headlabel="∅,{2}", labeldistance=1.5,labelangle=-90] +001 -> 100 [headlabel="{1,3}{1,2,3}", labeldistance=7.0,labelangle=15] +001 -> 101 [headlabel="{1}{1,2}", labeldistance=7.0,labelangle=15] +010 -> 010 [headlabel="∅,{2}", labeldistance=2.0,labelangle=-15] +010 -> 011 [headlabel="{3}{2,3}", labeldistance=5.0,labelangle=-15] +010 -> 110 [headlabel="{1}{1,2}", labeldistance=5.0,labelangle=-15] +010 -> 111 [headlabel="{1,3}{1,2,3}", labeldistance=5.0,labelangle=-15] +011 -> 000 [headlabel="{2,3}{1,2,3}", labeldistance=7.0,labelangle=-15] +011 -> 001 [headlabel="{2}{1,2}", labeldistance=7.0,labelangle=15] +011 -> 010 [headlabel="{3}{1,3}", labeldistance=7.0,labelangle=-15] +011:ne -> 011:se [headlabel="∅,{1}", labeldistance=1.5,labelangle=90] +100 -> 000 [headlabel="{1}{1,3}", labeldistance=5.0,labelangle=0] +100 -> 010 [headlabel="{1,2}{1,2,3}", labeldistance=5.0,labelangle=-15] +100:nw -> 100:sw [headlabel="∅,{3}", labeldistance=1.5,labelangle=-90] +100 -> 110 [headlabel="{2}{2,3}", labeldistance=5.0,labelangle=-15] +101 -> 100 [headlabel="{3}{1,3}", labeldistance=7.0,labelangle=-15] +101:nw -> 101:sw [headlabel="∅,{1}", labeldistance=1.5,labelangle=-90] +101 -> 110 [headlabel="{2,3}{1,2,3}", labeldistance=10.0,labelangle=-5] +101 -> 111 [headlabel="{2}{1,2}", labeldistance=7.0,labelangle=-15] +110 -> 100 [headlabel="{2}{1,2}", labeldistance=5.0,labelangle=-15] +110 -> 101 [headlabel="{2,3}{1,2,3}", labeldistance=5.0,labelangle=-15] +110 -> 110 [headlabel="∅,{1}", labeldistance=2.0,labelangle=90] +110 -> 111 [headlabel="{3}{1,3}", labeldistance=5.0,labelangle=15] +111:ne -> 001:ne [headlabel="{1,2}{1,2,3}", labeldistance=5.0,labelangle=-15] +111 -> 011 [headlabel="{1}{1,3}", labeldistance=7.0,labelangle=15] +111 -> 101 [headlabel="{2}{2,3}", labeldistance=7.0,labelangle=-15] +111:ne -> 111:se [headlabel="∅,{3}", labeldistance=1.5,labelangle=90] +} diff --git a/images/iter_f0_chaos.dot b/images/iter_f0_chaos.dot new file mode 100644 index 0000000..2085927 --- /dev/null +++ b/images/iter_f0_chaos.dot @@ -0,0 +1,45 @@ +digraph { +000 [shape="none"label="000", pos="10,10!"]; +001 [shape="none"label="001", pos="11.7320508076,11!"]; +010 [shape="none", label="010", pos="12,10!"]; +011 [shape="none", label="011", pos="13.7320508076,11!"]; +100 [shape="none", label="100", pos="10,8!"]; +101 [shape="none", label="101", pos="11.7320508076,9!"]; +110 [shape="none", label="110", pos="12,8!"]; +111 [shape="none", label="111", pos="13.7320508076,9!"]; + 000 -> 000 [color="blue"] + 000 -> 010; + 000 -> 001; + 010 -> 010 [color="blue"] + 010 -> 110; + 010 -> 011; + 001 -> 000; + 001 -> 001 [color="blue"] + 001 -> 101; + 101 -> 101 [color="blue"] + 101 -> 100; + 101 -> 111; + 110 -> 110 [color="blue"] + 110 -> 100; + 110 -> 111; + 011 -> 010; + 011 -> 001; + 011 -> 011 [color="blue"] + 100 -> 000; + 100 -> 100 [color="blue"] + 100 -> 110 + 111 -> 111 [color="blue"] + 111 -> 011; + 111 -> 101 +/* + 000 -> 100 [style="dashed"] + 100 -> 101 [style="dashed"] + 101 -> 001 [style="dashed"] + 001 -> 011 [style="dashed"] + 011 -> 111 [style="dashed"] + 111 -> 110 [style="dashed"] + 110 -> 010 [style="dashed"] + 010 -> 000 [style="dashed"] +*/ + +} diff --git a/images/iter_f0_chaos_ini.dot b/images/iter_f0_chaos_ini.dot new file mode 100644 index 0000000..0650a0b --- /dev/null +++ b/images/iter_f0_chaos_ini.dot @@ -0,0 +1,45 @@ +digraph { +000 [shape="none"label="000"] +001 [shape="none"label="001"] +010 [shape="none", label="010"] +011 [shape="none", label="011"] +100 [shape="none", label="100"] +101 [shape="none", label="101"] +110 [shape="none", label="110"] +111 [shape="none", label="111"] + 000 -> 000 [color="blue"] + 000 -> 010; + 000 -> 001; + 010 -> 010 [color="blue"] + 010 -> 110; + 010 -> 011; + 001 -> 000; + 001 -> 001 [color="blue"] + 001 -> 101; + 101 -> 101 [color="blue"] + 101 -> 100; + 101 -> 111; + 110 -> 110 [color="blue"] + 110 -> 100; + 110 -> 111; + 011 -> 010; + 011 -> 001; + 011 -> 011 [color="blue"] + 100 -> 000; + 100 -> 100 [color="blue"] + 100 -> 110 + 111 -> 111 [color="blue"] + 111 -> 011; + 111 -> 101 +/* + 000 -> 100 [style="dashed"] + 100 -> 101 [style="dashed"] + 101 -> 001 [style="dashed"] + 001 -> 011 [style="dashed"] + 011 -> 111 [style="dashed"] + 111 -> 110 [style="dashed"] + 110 -> 010 [style="dashed"] + 010 -> 000 [style="dashed"] +*/ + +} diff --git a/images/iter_f0b.dot b/images/iter_f0b.dot new file mode 100644 index 0000000..e00de78 --- /dev/null +++ b/images/iter_f0b.dot @@ -0,0 +1,45 @@ +digraph { +000 [shape="none"label="000", pos="10,10!"]; +001 [shape="none"label="001", pos="11.7320508076,11!"]; +010 [shape="none", label="010", pos="12,10!"]; +011 [shape="none", label="011", pos="13.7320508076,11!"]; +100 [shape="none", label="100", pos="10,8!"]; +101 [shape="none", label="101", pos="11.7320508076,9!"]; +110 [shape="none", label="110", pos="12,8!"]; +111 [shape="none", label="111", pos="13.7320508076,9!"]; + 000 -> 000:w; + 000 -> 010; + 000 -> 001; + 010 -> 010; + 010 -> 110; + 010 -> 011; + 001 -> 000; + 001 -> 001:w; + 001 -> 101; + 101 -> 101:w; + 101 -> 100; + 101 -> 111; + 110 -> 110; + 110 -> 100; + 110 -> 111; + 011 -> 010; + 011 -> 001; + 011 -> 011; + 100 -> 000; + 100 -> 101; + 100 -> 100:w; + 111 -> 110; + 111 -> 011; + 111 -> 111; +/* + 000 -> 100 [style="dashed"] + 100 -> 101 [style="dashed"] + 101 -> 001 [style="dashed"] + 001 -> 011 [style="dashed"] + 011 -> 111 [style="dashed"] + 111 -> 110 [style="dashed"] + 110 -> 010 [style="dashed"] + 010 -> 000 [style="dashed"] +*/ + +} diff --git a/images/iter_f0c.dot b/images/iter_f0c.dot new file mode 100644 index 0000000..be8e695 --- /dev/null +++ b/images/iter_f0c.dot @@ -0,0 +1,45 @@ +digraph { +000 [shape="none"label="000", pos="10,10!"]; +001 [shape="none"label="001", pos="11.7320508076,11!"]; +010 [shape="none", label="010", pos="12,10!"]; +011 [shape="none", label="011", pos="13.7320508076,11!"]; +100 [shape="none", label="100", pos="10,8!"]; +101 [shape="none", label="101", pos="11.7320508076,9!"]; +110 [shape="none", label="110", pos="12,8!"]; +111 [shape="none", label="111", pos="13.7320508076,9!"]; + // 000:nw -> 000:so [color="blue"] + 000 -> 010; + 000 -> 001; + //010:ne -> 010:se [color="blue"] + 010 -> 110; + 010 -> 011; + 001 -> 000; + //001 -> 001 [color="blue"] + 001 -> 101; + //101 -> 101 [color="blue"] + 101 -> 100; + 101 -> 111; + //110 -> 110 [color="blue"] + 110 -> 100; + 110 -> 111; + 011 -> 010; + 011 -> 001; + //011 -> 011 [color="blue"] + 100 -> 000; + //100 -> 100 [color="blue"] + 100 -> 110 + //111 -> 111 [color="blue"] + 111 -> 011; + 111 -> 101 +/* + 000 -> 100 [style="dashed"] + 100 -> 101 [style="dashed"] + 101 -> 001 [style="dashed"] + 001 -> 011 [style="dashed"] + 011 -> 111 [style="dashed"] + 111 -> 110 [style="dashed"] + 110 -> 010 [style="dashed"] + 010 -> 000 [style="dashed"] +*/ + +} diff --git a/images/iter_f0c.eps b/images/iter_f0c.eps new file mode 100644 index 0000000..22d84c4 Binary files /dev/null and b/images/iter_f0c.eps differ diff --git a/intro.tex b/intro.tex new file mode 100644 index 0000000..6460412 --- /dev/null +++ b/intro.tex @@ -0,0 +1,250 @@ +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 +\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 +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é +aux conditions initiales (le fameux \og \emph{effet papillon}\fg{}): +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 +$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és +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} +\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}, +$\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip} et +$\chi_{\textit{14Secrypt}}$ \cite{chgw14oip} où \textit{CI} signifie +\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 +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. + +% 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{} +% définies par les tableaux ci-dessous: + +% \begin{center} +% \begin{tabular}{|c|c|c|} +% \hline +% + & 0 & 1 \\ +% \hline +% 0 & 0 & 1 \\ +% \hline +% 1 & 1 & 1 \\ +% \hline +% \end{tabular}\qquad +% \begin{tabular}{|c|c|c|} +% \hline +% . & 0 & 1 \\ +% \hline +% 0 & 0 & 0 \\ +% \hline +% 1 & 0 & 1 \\ +% \hline +% \end{tabular}\qquad +% \begin{tabular}{|c|c|c|} +% \hline +% x & 0 & 1 \\ +% \hline +% $\overline{x}$ & 1 & 0 \\ +% \hline +% \end{tabular} +% \end{center} + + +% 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 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})$. + +% 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)$. + +% 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 +% $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. + +% Enfin, un bon générateur aléatoire se doit de +% 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. + + +% Le chaos a été appliqué à des domaines variés en +% 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 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$. + +% \begin{figure}[hb] +% \begin{center} +% \subfloat[Fonction tente $f=\min\{x,\,1-x\}$]{ +% \begin{minipage}{0.45\textwidth} +% \begin{center} +% \includegraphics[height=3cm]{images/tente.png} +% \end{center} +% \end{minipage} +% \label{fig:iter:tent} +% } +% \subfloat[Fonction logistique $f(x) = \mu x (1 -x)$]{ +% \begin{minipage}{0.45\textwidth} +% \begin{center} +% \includegraphics[height=3cm]{images/logistique.png} +% \end{center} +% \end{minipage} +% \label{fig:iter:log} +% } +% \end{center} +% \caption{Systèmes itératifs basés sur des fonctions chaotiques dans $\R$ \label{fig:iter}} +% \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 +% 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 +% $\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$ +% sommets. +% Ainsi pour étendre l'applicabilité de cette caractérisation, on s'intéresse +% 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$ +% 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. + +% 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. +% 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. + + +% 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}. +% Des conditions suffisantes pour obtenir cette chaoticité sont présentées en +% 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. + + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "main" +%%% End: diff --git a/ita.cls b/ita.cls new file mode 100644 index 0000000..9d18b72 --- /dev/null +++ b/ita.cls @@ -0,0 +1,391 @@ +\NeedsTeXFormat{LaTeX2e} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%% ita class for LaTeX2e %% +%%% Pierre Damphousse %% +%%% Copyright (C) EDP Sciences %% +%%% Version 1.2. September 2002 %% +%%% tex-support@edpsciences.com %% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%% --> THE CLASS OPTION MATERIAL +%% --> THE CLASS PRESENTATION MATERIAL +%% --> THE SECTIONING MATERIAL +%% --> THE METRIC DATA +%% --> THE TOP MATTER MATERIAL +%---- (A) The MAKETITLE command and its components +%---- (B) Preparing the MAKETITLE components +% -1- Heading +% -2- Title and Running Title +% -3- Authors and Running authors +% -4- Date +% -5- Subject Class +% -6- Resume +% -7- Abstract +% -8- Address (\address, given after the \author command) +% -9- Thanks (given after the title: \thanks) +%% --> MISCELLANEOUS +%% --> MESSAGES +%% --> VARIOUS MACROS +%---- (A) LATIN ABBREVIATIONS +%---- (B) REFERENCES +%---- (C) NEWTHEOREM AND ENVIRONMENTS +%---- (D) MATHEMATICS +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% +%%----------------------------------------------------------------------------- +%% --> THE CLASS OPTION MATERIAL +%%----------------------------------------------------------------------------- +\ProvidesClass{ita}[1999/03/01 v1.1 EDP-Sciences] +\DeclareOption*{\PassOptionsToClass{\CurrentOption}{amsart}} +\ProcessOptions\relax +%%----------------------------------------------------------------------------- +%% --> THE CLASS PRESENTATION MATERIAL +%%----------------------------------------------------------------------------- +\LoadClass[reqno]{amsart}[1996/10/24] +\RequirePackage{cite} +%%----------------------------------------------------------------------------- +%% --> THE SECTIONING MATERIAL +%%----------------------------------------------------------------------------- +\def\section{\@startsection{section}{1}\z@{1.2\linespacing\@plus\linespacing}% +{\linespacing} {\fontsize{12}{14}\selectfont\scshape\centering}} +\def\subsection{\@startsection{subsection}{2}\z@{\linespacing\@plus.8\linespacing}% +{.8\linespacing}{\fontsize{10}{12}\selectfont\scshape}} +\def\subsubsection{\@startsection{subsubsection}{3}\z@{.7\linespacing\@plus.5\linespacing}% +{.5\linespacing}{\normalfont\itshape}} +\def\paragraph{\@startsection{paragraph}{4}\z@\z@{-\fontdimen2\font}\normalfont} +\def\subparagraph{\@startsection{subparagraph}{5}\z@\z@{-\fontdimen2\font}\normalfont} +%%----------------------------------------------------------------------------- +%% --> THE METRIC DATA +%%----------------------------------------------------------------------------- +\setlength\oddsidemargin {15pt}\setlength\evensidemargin{15pt} +\setlength{\textwidth}{125mm}\setlength{\textheight}{190mm} +\setlength{\headheight}{18pt} +%%----------------------------------------------------------------------------- +%% --> THE TOP MATTER MATERIAL +%%----------------------------------------------------------------------------- +% = = = = = = = = = = = = = = = = = = = = +%---- (A) The MAKETITLE command and its components +\def\@maketitle{% + \normalfont\normalsize + \let\@makefnmark\relax \let\@thefnmark\relax + \global\def\shorttitle{\@MSSG@RNNGTTL} + \global\def\shortauthors{\@MSSG@RNNGTHR} + \@mkboth{\@nx\shortauthors}{\@nx\shorttitle}% + \global\topskip42\p@\relax + \@SKIP@Aa + \vbox{\hbox to\hsize{{\fontsize{10}{12}\selectfont{\bf\@NMJRNL@E}}\hfill% + {\fontsize{8}{9}\selectfont\@JRNL@X}} + \hbox to\hsize{\fontsize{8}{9}\selectfont{\@NMJRNL@F}\hfill}} + \@SKIP@Ab + \@setkeywords + \@settitle + \@setauthors + \@setabstract + \@setresume + \@setsubjclass + \normalsize + \if@titlepage\newpage\else\dimen@34\p@\advance\dimen@-\baselineskip\vskip\dimen@\relax\fi + \gdef\thanks##1{\relax}\gdef\address##1{\relax} +}% end \@maketitle +% = = = = = = = = = = = = = = = = = = = = +%---- (B) Preparing the MAKETITLE components +%................ ................ ................ ................ ................ +% -1- Heading +%................ ................ ................ ................ ................ +\def\@SKIP@Aa{\vspace*{-1.5cm}}% +\def\@SKIP@Ab{\vspace*{1.5cm}}% +\def\@NMJRNL@F{{Informatique Th\'eorique et Applications}}% +\def\@NMJRNL@E{{Theoretical Informatics and Applications}}% +\def\@JRNL@X{{Will be set by the publisher}}% +\def\idline#1page#2{\global\def\@JRNL@X{#1}\setcounter{page}{#2}} +%................ ................ ................ ................ ................ +% -2- Title and Running Title +%................ ................ ................ ................ ................ +\def\@settitle{\begin{center}\fontsize{11}{15}\selectfont\bfseries + \uppercasenonmath\@title\@title\@thnks@i\@thnks@ii\@thnks@iii\@thnks@iv\@thnks@v +\ifnum\the\@c@thnks@=0\else\footnote{\box\@b@thnks@}\fi +\end{center}} +\newbox\@b@rnngttl +\def\runningtitle#1{\setbox\@b@rnngttl=\hbox{\fontsize{7}{9}\selectfont\rm\uppercase{#1}}} +%................ ................ ................ ................ ................ +% -3- Authors and Running authors +%................ ................ ................ ................ ................ +\def\@setauthors{\begingroup\trivlist + \centering\footnotesize \@topsep30\p@\relax\advance\@topsep by -\baselineskip + \item\relax\fontsize{12}{14}\selectfont\scshape\@@th@rs\ignorespaces + \footnote{\box\@b@ddrss@}\endtrivlist\endgroup} +\def\email#1{{e-mail: \tt#1}} +\newbox\@b@rnngthr +\def\runningauthors#1{\setbox\@b@rnngthr=\hbox{#1}% +\global\def\@rnngthrs{\fontsize{7}{9}\selectfont\rm\uppercase{#1}}} +\newcount\@c@thr@\@c@thr@=0 +\def\author#1{\global\advance\@c@thr@ by 1 + \global\expandafter\edef\csname @thr@\romannumeral\@c@thr@\endcsname{#1} + \global\expandafter\edef\csname @Mthr@\romannumeral\@c@thr@\endcsname{\uppercase{#1}} + \global\expandafter\def\csname @ddrss@\romannumeral\@c@thr@\endcsname{} + \global\expandafter\def\csname @scndddrss@\romannumeral\@c@thr@\endcsname{} + \global\expandafter\def\csname @smddrss@\romannumeral\@c@thr@\endcsname{}}%\author +% Elaborating the two author lists (First page and heading) +\newcount\@y\newcount\@x +\def\@cnjctn{\ifnum\the\@c@thr@=1\null\else{{\ and\ }}\fi} +\def\@Mcnjctn{\ifnum\the\@c@thr@=1\null\else{{\ AND\ }}\fi} +\def\@@th@rs{\@x=0\global\@y=\@c@thr@\global\advance\@y by -1 +\loop\advance\@x by 1 +\ifnum\the\@x<\the\@y\csname @thr@\romannumeral\@x\endcsname\ignorespaces + ${}^{\csname @ddrss@\romannumeral\@x\endcsname + \csname @smddrss@\romannumeral\@x\endcsname + \csname @scndddrss@\romannumeral\@x\endcsname}$, +\repeat +\csname @thr@\romannumeral\@y\endcsname\ignorespaces + ${}^{\csname @ddrss@\romannumeral\@y\endcsname + \csname @smddrss@\romannumeral\@y\endcsname + \csname @scndddrss@\romannumeral\@y\endcsname}$\@cnjctn +\csname @thr@\romannumeral\@c@thr@\endcsname\ignorespaces + ${}^{\csname @ddrss@\romannumeral\@c@thr@\endcsname + \csname @smddrss@\romannumeral\@c@thr@\endcsname + \csname @scndddrss@\romannumeral\@c@thr@\endcsname}$}%\@@th@rs +\def\M@@th@rs{\@x=0\global\@y=\@c@thr@\global\advance\@y by -1 +\loop\advance\@x by 1 +\ifnum\the\@x<\the\@y\csname @Mthr@\romannumeral\@x\endcsname, +\repeat +\csname @Mthr@\romannumeral\@y\endcsname\@Mcnjctn +\csname @Mthr@\romannumeral\@c@thr@\endcsname}%\M@@th@rs +\def\@qq#1#2{\vrule height#1 depth#2 width0pt} +%................ ................ ................ ................ ................ +% -4- Date and editor +%................ ................ ................ ................ ................ +\let\@date\@empty +\def\@setdate{\noindent\fontsize{8}{10}\selectfont\hbox{\@date\@addpunct.}} +\def\editor#1{\def\@editor{#1}} +\let\@editor\@empty +\def\@seteditor{\vskip6\p@\noindent\fontsize{8}{10}\selectfont\noindent\hbox{Communicated by +\@editor\@addpunct.}} +%................ ................ ................ ................ ................ +% -5- Subject Class +%................ ................ ................ ................ ................ +% +\def\@setsubjclass{\skip@20\p@\advance\skip@-\lastskip\advance\skip@-\baselineskip\vskip\skip@ + \moveright 3pc\hbox{{\bfseries\subjclassname.}\enspace \@subjclass \@addpunct.}} % +\renewcommand{\subjclassname}{AMS Subject Classification} +% +\newbox\@b@kwrds +\def\keywords#1{\global\setbox\@b@kwrds\vtop{\advance\hsize by-12pt + \noindent\footnotesize\textit{\@MSSG@KWRD@0K}#1\@qq{0pt}{4pt}}} +\def\@setkeywords{\ifvoid\@b@kwrds\else\footnote{\box\@b@kwrds}\fi} +%................ ................ ................ ................ ................ +% -6- Resume +%................ ................ ................ ................ ................ +\newbox\resumebox +\newenvironment{resume}{\ifx\maketitle\relax\ClassWarning{\@classname}{\@MSSG@CLSSWRNG}\fi + \global\setbox\resumebox=\vtop\bgroup\fontsize{9}{11}\selectfont\advance \hsize -6pc + \trivlist + \labelsep.5em\item[\hskip\labelsep{\scshape\fontsize{10}{12}\selectfont\bf R\'esum\'e}.]} +{\endtrivlist\egroup\ifx\@setresume\relax \@setresumea \fi} +\def\@setresume{\@setresumea\global\let\@setresume\relax} +\def\@setresumea{\skip@20\p@\advance\skip@-\lastskip\advance\skip@-\baselineskip \vskip\skip@ + \ifvoid\resumebox\else\moveright 3pc \box\resumebox\fi} +%................ ................ ................ ................ ................ +% -7- Abstract +%................ ................ ................ ................ ................ +\newbox\abstractbox +\renewenvironment{abstract}{\ifx\maketitle\relax\ClassWarning{\@classname}{\@MSSG@CLSSWRNGBSTRCT}\fi + \global\setbox\abstractbox=\vtop\bgroup\fontsize{9}{11}\selectfont + \advance \hsize -6pc + \trivlist + \labelsep.5em\item[\hskip\labelsep{\scshape\fontsize{10}{12}\selectfont\bf Abstract}.]} +{\endtrivlist\egroup\ifx\@setabstract\relax \@setabstracta \fi} +\def\@setabstract{\@setabstracta\global\let\@setabstract\relax} +\def\@setabstracta{\skip@20\p@ \advance\skip@-\lastskip \advance\skip@-\baselineskip \vskip\skip@ + \ifvoid\abstractbox{\hbox to\hsize{\kern3pc\fontsize{10}{12} + \selectfont\bf \hbox to55pt{Abstract\hfill}\qquad\@MSSG@BSTRCT\hfill}} + \else\moveright 3pc \box\abstractbox \fi} +%................ ................ ................ ................ ................ +% Address (\address, given after the \author command) +% -8- Same Address (\sameaddress, given after the \author command) +% Second Address (\secondaddress, given after the \author command) +%................ ................ ................ ................ ................ +\def\@spc{\kern1pt}\def\@spcc{\kern2pt} +\newcount\@c@ddrss@\newbox\@b@ddrss@ +% +\def\@dd@ddrss@#1{% +\global\setbox51=\vbox{\advance\hsize by-12pt\unvbox\@b@ddrss@ + \vtop{\footnotesize\noindent{${}^{\the\@c@ddrss@}$\ }\@qq{10pt}{0pt}\textrm{#1}}} + \global\setbox\@b@ddrss@=\vbox{\unvbox51}}% +% +\def\@dd@scndddrss@#1{% +\global\setbox51=\vbox{\advance\hsize by-12pt\unvbox\@b@ddrss@ + \vtop{\footnotesize\noindent{${}^{\the\@c@ddrss@}$\ }\@qq{10pt}{0pt}\textrm{#1}}} + \global\setbox\@b@ddrss@=\vbox{\unvbox51}} +% +\def\address#1{\global\advance\@c@ddrss@ by 1\@dd@ddrss@{#1} + \expandafter\edef\csname @ddrss@\romannumeral\@c@thr@\endcsname{\@spc\number\@c@ddrss@}} +\def\secondaddress#1{\global\advance\@c@ddrss@ by 1\@dd@ddrss@{#1} + \expandafter\edef\csname @scndddrss@\romannumeral\@c@thr@\endcsname% +{,\@spcc\number\@c@ddrss@}}%\secondaddress#1 +\def\sameaddress#1{\expandafter\edef\csname @smddrss@\romannumeral\@c@thr@\endcsname{\@spc{}#1}} +%................ ................ ................ ................ ................ +% -9- Thanks (given in the title: \thanks) +%................ ................ ................ ................ ................ +\def\@rmnnmrl#1{\ifcase#1\null\or*\or**\or***\or****\or*****\else\@MSSG@THNKS\fi} +\def\@thnks@i{}\def\@thnks@ii{}\def\@thnks@iii{}\def\@thnks@iv{}\def\@thnks@v{} +\newcount\@c@thnks@\newbox\@b@thnks@ +\def\@dd@thnks@#1{% +\global\setbox50=\vbox{\advance\hsize by-12pt\unvbox\@b@thnks@ + \vtop{\noindent\footnotesize{${}^{\@rmnnmrl\@c@thnks@}$\ }\@qq{10pt}{0pt}\textit{#1}\hfill}} +\global\setbox\@b@thnks@=\vbox{\unvbox50}}% +\def\thanks#1{\global\advance\@c@thnks@ by 1\@dd@thnks@{#1}% +\global\expandafter\edef\csname @thnks@\romannumeral\@c@thnks@\endcsname{% +\ifnum\the\@c@thnks@=1\@spcc${}^{\@rmnnmrl\@c@thnks@}$\else$^{,\@spcc\@rmnnmrl\@c@thnks@}$\fi}} +%%----------------------------------------------------------------------------- +%% --> MISCELLANEOUS +%%----------------------------------------------------------------------------- +\DeclareRobustCommand*\cal{\@fontswitch\relax\mathcal} +% +\renewcommand\normalsize{\@xsetfontsize\normalsize 6% + \@adjustvertspacing \let\@listi\@listI + \abovedisplayskip 11pt \@plus2pt \@minus2pt + \belowdisplayskip \abovedisplayskip} +% +\def\ps@firstpage{\ps@plain + \def\@oddfoot{\hfill{\scriptsize \copyright\ EDP Sciences 1999}}% + \let\@evenfoot\@oddfoot\def\@oddhead{\null\hss} + \let\@evenhead\@oddhead}% in case an article starts on a left-hand page +% +\def\ps@headings{\ps@empty + \def\@evenhead{\normalfont\scriptsize\llap{\normalsize\thepage\kern-4pt}\hfil\scriptsize\leftmark{}{}\hfil}% + \def\@oddhead{\normalfont\scriptsize\hfil\rightmark{}{}\hfil\rlap{\kern-4pt\normalsize{\thepage}}}% + \let\@mkboth\markboth} +\def\ps@myheadings{\ps@headings \let\@mkboth\@gobbletwo}\pagestyle{headings} +%%----------------------------------------------------------------------------- +%% --> MESSAGES +%%----------------------------------------------------------------------------- +\def\@MSSG@THNKS{At most 5 thanks allowed} +\def\@MSSG@CLSSWRNGRSM{Resume should precede \protect\maketitle\space in AMS documentclasses; reported} +\def\@MSSG@CLSSWRNGBSTRCT{Abstract should precede \protect\maketitle\space in AMS documentclasses; + reported} +\def\@MSSG@KWRD{{WARNING: --- Give at least one key words ---}} +\def\@MSSG@KWRD@0K{{Keywords and phrases:\ }} +\def\@MSSG@SBJCTCLSS{{--- Give AMS classification codes ---}} +\def\@MSSG@RSM{{WARNING: --- Il est obligatoire de donner un r\'esum\'e en fran\c cais! ---}} +\def\@MSSG@BSTRCT{{WARNING: --- An English abstract is mandatory! ---}} +\def\@MSSG@DT{{(The dates will be set by the publisher)}} +\def\@MSSG@DTR{{(The editor will be set by the publisher)}} +%% September 2002 +\def\@MSSG@RNNGTTL{\uppercase{Title will be set by the publisher}} +\def\@MSSG@RNNGTHR{\uppercase{Title will be set by the publisher}} +% +\def\@date{\@MSSG@DT} +\def\@editor{\@MSSG@DTR} +\def\@subjclass#1{\@MSSG@SBJCTCLSS} +%%----------------------------------------------------------------------------- +%% --> VARIOUS MACROS +%%----------------------------------------------------------------------------- +%................ ................ ................ ................ ................ +%---- (A) LATIN ABBREVIATIONS +%................ ................ ................ ................ ................ +\def\cf{\emph{cf.\/}}\def\ie{\emph{i.e.\/}}\def\etc{\emph{etc\/}} +\def\apriori{\emph{a priori\/}}\def\afortiori{\emph{a fortiori\/}} +\def\loccit{\emph{a loc. cit.\/}}\def\etal{\emph{et al.\/}} +\def\vg{\emph{v.g.\/}} +%................ ................ ................ ................ ................ +%---- (B) REFERENCES +%................ ................ ................ ................ ................ +\def\@Rref#1{\hbox{\rm \ref{#1}}} +\def\Rref#1{\@Rref{#1}} +%................ ................ ................ ................ ................ +%---- (C) NEWTHEOREM AND ENVIRONMENTS +%................ ................ ................ ................ ................ +%------------------- +\theoremstyle{plain} +%------------------- +\newtheorem{thrm}{Theorem}[section] +\newtheorem{lmm}[thrm]{Lemma} +\newtheorem{crllr}[thrm]{Corollary} +\newtheorem{prpstn}[thrm]{Proposition} +\newtheorem{crtrn}[thrm]{Criterion} +\newtheorem{lgrthm}[thrm]{Algorithm} +%------------------------ +\theoremstyle{definition} +%------------------------ +\newtheorem{dfntn}[thrm]{Definition} +\newtheorem{cnjctr}[thrm]{Conjecture} +\newtheorem{xmpl}[thrm]{Example} +\newtheorem{prblm}[thrm]{Problem} +\newtheorem{rmrk}[thrm]{Remark} +\newtheorem{nt}[thrm]{Note} +\newtheorem{clm}[thrm]{Claim} +\newtheorem{smmr}[thrm]{Summary} +\newtheorem{cs}[thrm]{Case} +\newtheorem{bsrvtn}[thrm]{Observation} +% +%------------------- +\theoremstyle{plain} +%------------------- +\newenvironment{acknowledgement}{\par\addvspace{17pt}\small\rmfamily\noindent}{\par\addvspace{6pt}} +%................ ................ ................ ................ ................ +%---- (D) MACROS FOR MATHEMATICS +%................ ................ ................ ................ ................ +\def\xQuaternion{\mathbb{H}} \def\xC{\mathbb{C}} \def\xR{\mathbb{R}} +\def\xQ{\mathbb{Q}} \def\xZ{\mathbb{Z}} \def\xN{\mathbb{N}} +\def\xP{\mathbb{P}} \def\xA{\mathbb{A}} +%-- +\def\xCzero{{\rm C}^{0}} +\def\xCone{{\rm C}^{1}} +\def\xCtwo{{\rm C}^{2}} +\def\xCinfty{{\rm C}^{\infty}} +\def\xCn#1{{\rm C}^#1} +%-- +\def\xHzero{{\rm H}^{0}} +\def\xHone{{\rm H}^{1}} +\def\xHtwo{{\rm H}^{2}} +\def\xHinfty{{\rm H}^{\infty}} +\def\xHn#1{{\rm H}^#1} +% +\def\xWzero{{\rm W}^{0}} +\def\xWone{{\rm W}^{1}} +\def\xWtwo{{\rm W}^{2}} +\def\xWinfty{{\rm W}^{\infty}} +\def\xWn#1{{\rm W}^#1} +% +\def\xLzero{{\rm L}^{0}} +\def\xLone{{\rm L}^{1}} +\def\xLtwo{{\rm L}^{2}} +\def\xLinfty{{\rm L}^{\infty}} +\def\xLn#1{{\rm L}^#1} +%-- +\def\xDif{{\rm D}} +\def\xdif{\,{\rm d}} +%-- +\def\xdrv#1#2{\frac{{\rm d}#1}{{\rm d}#2}}% "d#1 over d#2" +\def\xDrv#1#2{\frac{{\rm d}}{{\rm d}#2}#1}% "d over d#2 #1" +%-- +\def\xker{\mathop{\rm ker\,}\nolimits} +\def\xcoker{\mathop{\rm coker\,}\nolimits} +\def\xim{\mathop{\rm im\,}\nolimits} +\def\xcoim{\mathop{\rm coim\,}\nolimits} +\def\xdim{\mathop{\rm dim\,}\nolimits} +\def\xcodim{\mathop{\rm codim\,}\nolimits} +\def\xtr{\mathop{\rm tr\,}\nolimits} +\def\xHom{\mathop{\rm Hom\,}\nolimits} +\def\xExt{\mathop{\rm Ext\,}\nolimits} +\def\xTor{\mathop{\rm Tor\,}\nolimits} +%-- +\def\xGL{\mathop{\rm GL\,}\nolimits} +\def\xSL{\mathop{\rm SL\,}\nolimits} +\def\xPSL{\mathop{\rm PSL\,}\nolimits} +\def\xSO{\mathop{\rm SO\,}\nolimits} +\def\xSU{\mathop{\rm SU\,}\nolimits} +% +\def\xProof{ + \normalfont + \medskip + {\noindent\itshape Proof.\hspace*{6pt}\ignorespaces}} +% +\def\enddoc@text{\ifx\@empty\@translators \else\@settranslators\fi + \ifx\@empty\@editor \else\@seteditor\\\fi + \ifx\@empty\@date \else\@setdate\fi} +% +% +\endinput diff --git a/main.tex b/main.tex new file mode 100644 index 0000000..9192540 --- /dev/null +++ b/main.tex @@ -0,0 +1,129 @@ +\documentclass{ita} +\usepackage{graphicx} +\usepackage{dsfont} +\usepackage{stmaryrd} +\usepackage[font=footnotesize]{subfig} +\usepackage{ifthen} +\usepackage{color} +\usepackage{algorithm2e} +\usepackage[hyperfirst=true,nogroupskip,nonumberlist,xindy]{glossaries} + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Définitions personnelles +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +\definecolor{bleuclair}{rgb}{0.75,0.75,1.0} +\newcommand{\ANNOT}[1]{ + ~\linebreak + \centerline{ + {\Huge{\danger}} + \large\fcolorbox{black}{bleuclair}{ + \begin{minipage}[h]{.8\linewidth} + #1 + \end{minipage} + } + {\Huge{\danger}} + } +} + +% \theoremstyle{plain} +% \theoremheaderfont{\normalfont\bfseries\sc} +% \theorembodyfont{\slshape} +% \theoremsymbol{\ensuremath{\diamondsuit}} +% \theoremprework{\bigskip} +% \theoremseparator{.} +\newtheorem{Def}{\underline{Définition}} +\newtheorem{Lemma}{\underline{Lemme}} +\newtheorem{Theo}{\underline{Théorème}} +% \theoremheaderfont{\sc} +% \theorembodyfont{\upshape} +% \theoremstyle{nonumberplain} +% \theoremseparator{} +% \theoremsymbol{\rule{1ex}{1ex}} +\newtheorem{Proof}{Preuve :} +\newtheorem{xpl}{Exemple illustratif :} + +\newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}} +%\newcommand{\ie}{\textit{i.e.}} +\newcommand{\Nats}[0]{\ensuremath{\mathbb{N}}} +\newcommand{\R}[0]{\ensuremath{\mathbb{R}}} +\newcommand{\Z}[0]{\ensuremath{\mathbb{Z}}} +\newcommand{\Bool}[0]{\ensuremath{\mathds{B}}} +\newcommand{\rel}[0]{\ensuremath{{\mathcal{R}}}} +\newcommand{\Gall}[0]{\ensuremath{\mathcal{G}}} + + +\newcommand{\JFC}[1]{\begin{color}{green}\textit{}\end{color}} +\newcommand{\CG}[1]{\begin{color}{blue}\textit{}\end{color}} +\newcommand{\og}[0]{``} +\newcommand{\fg}[1]{''} + + + + +\makeglossaries +\loadglsentries{glossaire} + + +\title{XXX} + +\begin{document} + +\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} +This paper extends the results presented in~\cite{bcgr11ip} +and~\cite{chgw14oip} 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. + At the practical level, we show that the algorithm that builds strongly + connected iteration graphs, with doubly stochastic Markov matrix, has a + reduced mixing time. +\end{abstract} + +\section{Introduction} +\input{intro} + +\section{Préliminaires} +\label{section:chaos} +\input{sdd} + +\section{Caractérisation des systèmes dynamiques booléens chaotiques} +\label{section:caracterisation} +\input{cs} + + +\section{Application à la génération de nombres pseudo-aléatoires} +\label{section:genpa} +\input{exp} + + +\section{Expérimentations} +\label{section:expes} +\input{nist} + +\section{Conclusion} +\input{conclusion} + +%\acknowledgements{...} + +\appendix%\begin{annex} + \section{Preuve de continuité de $G_f$ dans $(\mathcal{X},d)$} + \label{anx:cont} + \input{annexecontinuite} + + +\printglossaries + +\bibliography{biblio} + +\end{document} diff --git a/markov.bib b/markov.bib new file mode 100644 index 0000000..9b5189b --- /dev/null +++ b/markov.bib @@ -0,0 +1,390 @@ +@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", +} + + diff --git a/nist.tex b/nist.tex new file mode 100644 index 0000000..7e196e6 --- /dev/null +++ b/nist.tex @@ -0,0 +1,143 @@ +% Soit $e_i$ le $i^{\textrm{ème}}$ vecteur de la base canonique de $\R^{2^{n}}$. +% Chacun des éléments $v_j$, $1 \le j \le 2^n$, +% du vecteur $e_i M_f^t$ représente la probabilité +% d'être dans la configuration $j$ après $t$ étapes du processus de Markov +% associé à $\Gamma(f)$ en partant de la configuration $i$. +% Le nombre \linebreak $\min \{ +% t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4} +% \}$ représente le plus petit nombre d'itérations où la distance de +% ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^n})$ +% -- autrement dit, où la déviation par rapport à la distribution uniforme -- +% est inférieure +% à $10^{-4}$. En prenant le max pour tous les $e_i$, on obtient une valeur pour +% $b$. Ainsi, on a +% $$ +% b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} +% \{ +% \min \{ +% t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4} +% \} +% \}. +% $$ + +\begin{table}[table:functions]{Fonctions avec matrices DSCC et le plus faible temps de mélange.} + \begin{center} + \begin{scriptsize} + \begin{tabular}{|c|l|c|c|} + \hline + fonction & $f(x)$, $f(x)$ pour $x \in [0,1,2,\hdots,2^n-1]$ & $b$ & $b'$ \\ + \hline + $f^{*4}$ & [13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8] & 15 & 32 \\ + \hline + $f^{*5}$ & [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, & 13 & 43 \\ + & 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4] & & \\ + \hline + $f^{*6}$ & [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33, & 9 & 50 \\ + & 49, 15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1, & & \\ + & 40, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, & & \\ + & 16, 24, 13, 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32] & & \\ + \hline + $f^{*7}$ & [111, 94, 93, 116, 122, 114, 125, 88, 87, 126, 119, 84, 123, & 8 & 57 \\ + & 98, 81, 120, 109, 106, 105, 110, 99, 107, 104, 108, 101, 70, & & \\ + & 117, 96, 67, 102, 113, 64, 79, 30, 95, 124, 83, 91, 121, 24, & & \\ + & 23, 118, 69, 20, 115, 90, 17, 112, 77, 14, 73, 78, 74, 10, 72, & & \\ + & 76, 103, 6, 71, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59, & & \\ + & 56, 48, 53, 38, 37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42, & & \\ + & 46, 45, 41, 35, 34, 39, 52, 43, 50, 32, 36, 29, 28, 61, 92, & & \\ + & 26, 18, 89, 25, 19, 86, 85, 4, 27, 2, 16, 80, 31, 12, 15, 8, & & \\ + & 3, 11, 13, 9, 5, 22, 21, 68, 7, 66, 65, 1] & & \\ + \hline + $f^{*8}$ &[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180,& 7 & 63 \\ + & 227, 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, &&\\ + & 229, 166, 165, 244, 163, 242, 241, 192, 215, 220, 205, 216, &&\\ + & 218, 222, 221, 208, 213, 210, 212, 214, 219, 211, 217, 209, &&\\ + & 239, 202, 207, 140, 139, 234, 193, 204, 135, 196, 199, 132, &&\\ + & 194, 130, 225, 200, 159, 62, 185, 252, 59, 250, 169, 56, 191,&&\\ + & 246, 245, 52, 243, 50, 176, 48, 173, 238, 189, 44, 235, 42, &&\\ + & 137, 184, 231, 38, 37, 228, 35, 226, 177, 224, 151, 156, 141,&&\\ + & 152, 154, 158, 157, 144, 149, 146, 148, 150, 155, 147, 153, &&\\ + & 145, 175, 206, 143, 136, 11, 142, 129, 8, 7, 198, 197, 4, 195, &&\\ + & 2, 161, 160, 255, 124, 109, 108, 122, 126, 125, 112, 117, 114, &&\\ + & 116, 100, 123, 98, 97, 113, 79, 106, 111, 110, 99, 74, 121, 120,&&\\ + & 71, 118, 103, 101, 115, 66, 65, 104, 127, 90, 89, 94, 83, 91, 81,&&\\ + & 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72, 107, 78, 105, &&\\ + & 64, 69, 102, 68, 70, 75, 67, 73, 96, 55, 58, 45, 188, 51, 186, 61, &&\\ + & 40, 119, 182, 181, 53, 179, 54, 33, 49, 15, 174, 47, 60, 171, && \\ + & 46, 57, 32, 167, 6, 36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19,&&\\ + & 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, &&\\ + &138, 41, 12, 39, 134, 133, 5, 131, 34, 9, 128]&&\\ + \hline + \end{tabular} + \end{scriptsize} + \end{center} +\end{table} + +Le tableau~\ref{table:functions} reprend les fonctions qui ont été générées +selon la méthode détaillée dans~\cite{chgw14oip} correspondant à ce qui est +présenté en section~\ref{section:genmat}. Pour chaque nombre $n=3$, $4$, $5$ +,$6$, tous les cycles hamiltoniens non isomorphes ont été générés. Pour les +valeur de $n=7$ et $8$, seules $10^{5}$ configurations ont été évaluées. Parmi +toutes les fonctions obtenues en enlevant du $n$-cube ces cycles, n'ont été +retenues que celles qui minimisaient le temps de mélange relatif à une valeur de +$\epsilon$ fixée à $10^{-8}$. Ce nombre d'itérations est stocké dans la troisième +colonne sous la variable $b$. La variable $b'$ reprend le temps de mélange pour +l'algorithme $\chi_{\textit{14Secrypt}}$~\cite{chgw14oip}. + +Un premier résultat est que ce nouvel algorithme réduit grandement le nombre +d'itérations suffisant pour obtenir une faible déviation par rapport à une +distribution uniforme. On constate de plus que ce nombre semble décroître avec +le nombre d'éléments alors qu'il augmentait dans l'approche précédente. + +La qualité des séquences aléatoires a été évaluée à travers la suite +de tests statistiques développée pour les générateurs de nombres +pseudo-aléatoires par le +\emph{National Institute of Standards and Technology} (NIST). + Pour les 15 tests, le seuil $\alpha$ est fixé à $1\%$: + une valeur + qui est plus grande que $1\%$ signifie + que la chaîne est considérée comme aléatoire avec une confiance de $99\%$. + Le tableau~\ref{fig:TEST} donne une vision synthétique de toutes + les expérimentations. +L'expérience a montré notamment que toutes ces fonctions +passent avec succès cette batterie de tests. + +%%%%%%%%% Relancer pour n=6, n=7, n=8 +%%%%%%%%% Recalculer le MT +%%%%%%%%% Regenerer les 10^6 bits +%%%%%%%%% Evaluer sur NIST + +\begin{table}[fig:TEST]{Test de NIST réalisé sur les fonctions $f^*$ détaillées au tableau~\ref{table:functions}.} + \centering + \begin{scriptsize} + \begin{tabular}{|*{5}{c|}} + \hline +Test & $f^{*4}$ & $f^{*5}$ & $f^{*6}$ & $f^{*7}$ \\ \hline +Fréquence (Monobit) & 0.025 (0.99) & 0.066 (1.0) & 0.319 (0.99) & 0.001 (1.0) \\ \hline +Fréquence / bloc & 0.401 (0.99) & 0.867 (1.0) & 0.045 (0.99) & 0.085 (0.99) \\ \hline +Somme Cumulé* & 0.219 (0.995) & 0.633 (1.0) & 0.635 (1.0) & 0.386 (0.99) \\ \hline +Exécution & 0.964 (0.98) & 0.699 (0.99) & 0.181 (0.99) & 0.911 (0.98) \\ \hline +Longue exécution dans un bloc & 0.137 (0.99) & 0.964 (1.0) & 0.145 (0.99) & 0.162 (0.98) \\ \hline +Rang & 0.616 (0.99) & 0.678 (1.0) & 0.004 (1.0) & 0.816 (1.0) \\ \hline +Fourier rapide & 0.048 (0.99) & 0.637 (0.97) & 0.366 (0.99) & 0.162 (0.99) \\ \hline +Patron sans superposition* & 0.479 (0.988) & 0.465 (0.989) & 0.535 (0.989) & 0.499 (0.989) \\ \hline +Patron avec superposition & 0.897 (1.0) & 0.657 (0.97) & 0.897 (0.98) & 0.236 (0.99) \\ \hline +Statistiques universelles & 0.991 (0.98) & 0.657 (0.98) & 0.102 (0.98) & 0.719 (0.98) \\ \hline +Entropie approchée (m=10) & 0.455 (1.0) & 0.964 (1.0) & 0.162 (1.0) & 0.897 (0.98) \\ \hline +Suite aléatoire * & 0.372 (0.993) & 0.494 (0.986) & 0.243 (0.992) & 0.258 (0.993) \\ \hline +Suite aléatoire variante * & 0.496 (0.989) & 0.498 (0.992) & 0.308 (0.983) & 0.310 (0.999) \\ \hline +Série* (m=10) & 0.595 (0.995) & 0.289 (0.975) & 0.660 (0.995) & 0.544 (0.99) \\ \hline +Complexité linaire & 0.816 (1.0) & 0.897 (0.98) & 0.080 (0.98) & 0.798 (1.0) \\ \hline + \end{tabular} + \end{scriptsize} +\end{table} + +Enfin, nous avons également débuté une campagne de tests complémentaires de +notre générateur aléatoire, utilisant les trois \emph{crush tests} (small, +normal et big) proposés dans la bibliothèque TestU01~\cite{LEcuyerS07}. Les +premiers résultats que nous obtenons sont très encourageants puisque la fonction +$f^{*4}$ passe avec succès tous les tests du small crush. + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "main" +%%% End: diff --git a/retardprng.tex b/retardprng.tex new file mode 100644 index 0000000..d6985d0 --- /dev/null +++ b/retardprng.tex @@ -0,0 +1,58 @@ +Nous avons vu comment construire un générateur de nombre pseudo-aléatoires en +utilisant un système booléen en mode chaotique. Cependant, cela nécessite une +contrainte forte sur le graphe d'itérations de la fonction associée, qui doit +être fortement connexe. Nous étudions dans cette partie une méthode permettant +de relâcher un peu les contraintes sur les fonctions $f_i$ en enrichissant le +système initial de façon à modéliser la notion de \emph{retards} entre éléments. + +\subsection{Les retards dans les systèmes dynamiques} +\label{sec:retards} + +La notion de retard provient initialement du besoin de prendre en compte les +délais de transfert d'information entre les éléments d'un système. Lorsque l'on +se place dans le contexte général, ces délais peuvent eux-mêmes varier dans le +temps. On décrit donc le retard de l'élément $j$ par rapport à l'élément $i$ à +l'instant $t$ par $r_j^i(t)$. Ainsi, l'information reçue de $j$ en $i$ à $t$ a +été générée à l'instant (ou itération) $s_j^i(t)=t-r_j^i(t)$. On en déduit que +la mise à jour de l'élément $i$ de l'instant $t$ à $t+1$ s'écrit : +\begin{equation*} + x_i(t+1) = f_i(x_1^{s_1^i(t)},x_2^{s_2^i(t)},\dots,x_i^t,\dots,x_{n-1}^{s_{n-1}^i(t)},x_n^{s_n^i(t)}) +\end{equation*} +On constate que même si le modèle le permet, on ne met généralement pas de délai +entre l'élément $i$ et lui-même car cela n'a pas d'intérêt pratique fort. + +Plusieurs travaux sur les systèmes à retards (\cite{Mie75, Rob86, BT89, BC02, + TNN2006}) ont montré que l'une des influences majeures des retards sur la +dynamique du système est d'augmenter le nombre de transitions possibles entre +les états. En d'autres termes, cela revient à augmenter la connexité du graphe +d'itérations, ce qui est justement la propriété recherchée. + +Cependant, une difficulté majeure dans notre contexte de génération de nombres +pseudo-aléatoires vient du fait que les retards induisent une dépendance du +système à son \emph{historique} plus ancien que la seule itération précédente. +Cela empêche le recours aux chaînes de Markov classiques pour établir les +preuves que les propriétés nécessaires à un bon générateur sont vérifiées. + +Afin de contourner cet obstacle, nous proposons ici une méthode simple +permettant de simuler des retards dans un système booléen chaotique. + +\subsection{Simulation de retards dans un système booléen chaotique} +\label{sec:simuRets} + +Soit un système booléen à $n$ éléments dont la dynamique chaotique est décrite +par $G_f$. Nous proposons d'étendre ce système afin d'y incorporer des retards +simulés. Le principe consiste à ajouter un n{\oe}ud intermédiaire au niveau de +chaque interaction entre deux éléments différents (les arcs $(i,s,j)$ t.q $i\ne +j$) du graphe d'interactions. Ainsi, si l'on considère l'arc $(i,s,j)$ du graphe +initial, alors cet arc sera remplacé dans le nouveau graphe par les arcs +$(i,+,k)$ et $(k,s,j)$, avec $x_k$ un nouvel élément booléen du système ayant +pour fonction d'évolution $f_k(x)=x_i$. De plus, les occurrences de l'élément +$x_i$ dans la fonction $f_j(x)$ seront remplacées par $x_k$. On note que l'arc +allant de $i$ à $k$ est systématiquement positif alors que l'arc allant de $k$ à +$j$ conserve le signe $s$ de l'ancien arc $(i,s,j)$. + + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "main" +%%% End: diff --git a/sdd.tex b/sdd.tex new file mode 100644 index 0000000..fc48a65 --- /dev/null +++ b/sdd.tex @@ -0,0 +1,299 @@ +Cette section énonce les notions fondamentales relatives aux systèmes dynamiques +booléens et à la mesure du chaos. Le formalisme des systèmes dynamiques +booléens est donné en section~\ref{sub:sdd}, suivi des méthodes de déduction des +graphes d'itérations (section~\ref{sub:grIter}). +% et d'interactions +%(section~\ref{sub:sdd:inter}). +% La notion de retards est présentée en +% section~\ref{sub:sdd:retards}. +Enfin, une distance sur l'espace $\llbracket 1;n\rrbracket^{\Nats}\times +\Bool^n$ est définie en section~\ref{sub:metric}, qui permet ensuite d'établir +la nature chaotique des systèmes dynamiques booléens, abordée en +section~\ref{section:caracterisation}. + +\subsection{Système dynamique booléen}\label{sub:sdd} + +Soit $n$ un entier naturel. Un système dynamique booléen est +défini à partir d'une fonction booléenne: +\[ +f:\Bool^n\to\Bool^n,\qquad x=(x_1,\dots,x_n)\mapsto f(x)=(f_1(x),\dots,f_n(x)), +\] +et un {\emph{schéma itératif}} ou encore \emph{mode de mise à jour} qui peut +être parallèle, séquentiel ou asynchrone%, et intégrer ou non des retards +. À partir d'une configuration initiale $x^0\in\Bool^n$, la suite $(x^{t})^{t + \in \Nats}$ des configurations du système est construite selon l'un des +schémas suivants : +\begin{itemize} +\item \textbf{Schéma parallèle synchrone :} basé sur la relation de récurrence + $x^{t+1}=f(x^t)$. Tous les $x_i$, $1 \le i \le n$, sont ainsi mis à jour à + chaque itération en utilisant l'état global précédent du système ($x^t$). +\item \textbf{Schéma séquentiel synchrone :} basé sur une mise à jour successive + des différents éléments du système, selon un ordre défini. Le mode séquentiel + de référence est basé sur la séquence ordonnée des éléments, de 1 à $n$. +\item \textbf{Schéma asynchrone :} cette terminologie a plusieurs acceptations + dans la littérature, mais celle qui reste la plus répandue, et que nous + retenons ici, consiste à ne modifier qu'un élément $i$, $1 \le i \le n$, à + chaque itération. Le choix de l'élément qui est modifié à chaque itération est + défini par une suite. Lorsque cette suite est strictement cyclique (sans + occurrences multiples dans le motif) sur l'ensemble des éléments $\{1,\ldots + n\}$, alors on retrouve le comportement du mode séquentiel synchrone. +\item \textbf{Schéma chaotique:} dans ce schéma, ce n'est plus un seul élément + qui est modifié à chaque itération, mais une partie des éléments de + $\{1,\ldots n\}$. Dans le premier cas particulier où c'est un singleton + $\{k\}$, $1 \le k \le n$, qui est modifié à chaque itération, on retrouve le + mode asynchrone, et si la séquence des singletons est ordonnée et cyclique, + alors on retrouve le mode séquentiel. Dans le second cas particulier où c'est + $\{1, \ldots, n\}$ qui est modifié à chaque itération, on retrouve le mode + parallèle. Ce mode généralise donc les trois autres modes précédents. + Plus formellement, à la $t^{\textrm{ème}}$ + itération, seuls les éléments de la partie + $s_{t} \in \mathcal{P}(\{1, \ldots, n\})$ sont mis à + jour. La suite $S = \left(s_t\right)_{t \in \mathds{N}}$ est une séquence + de sous-ensembles + de $\{ 1, \ldots,n \}$ appelée \emph{stratégie}. + Dans ce mode opératoire, on définit la fonction\linebreak + $F_f:~\mathcal{P}(\{1, \ldots, n\}) \times \Bool^{n} \rightarrow \Bool^n$ par + \[ + F_f(s,x)_i=\left\{ + \begin{array}{l} + f_i(x) \textrm{ si $i \in s$;}\\ + x_i \textrm{ sinon.} + \end{array}\right. + \] + Dans le schéma des itérations chaotiques, pour une configuration initiale + $x^0\in\Bool^n$ et une stratégie $S = \left(s_t\right)_{t \in \mathds{N}} +\in \mathcal{P}(\{1, \ldots, n\})^{\Nats}$, + les + configurations $x^t$ sont définies par la récurrence + \begin{equation}\label{eq:asyn} + x^{t+1}=F_f(s_t,x^t). + \end{equation} + Soit alors $G_f$ une fonction de $\mathcal{P}(\{1, \ldots, n\})^{\Nats}\times\Bool^n$ + dans lui-même définie par + \[ + G_f(S,x)=(\sigma(S),F_f(s_0,x)), + \] + où $\forall t\in\Nats,\sigma(S)_t=s_{t+1}$. + En d'autres termes la fonction $\sigma$ \emph{décale} + la stratégie fournie en argument d'un élément vers la gauche en supprimant + l'élément de tête. + Les itérations parallèles de $G_f$ depuis un point initial + $X^0=(S,x^0)$ décrivent la même orbite que les + itérations chaotiques de $f$ induites par $x^0$ et la stratégie + $S$. +\end{itemize} + +\subsection{Graphe d'itérations chaotiques}\label{sub:grIter} + +Soit $f$ une fonction de $\Bool^n$ dans lui-même. +Le {\emph{graphe des itérations chaotiques}} associé à $f$ est le +graphe orienté $\Gamma(f)$ défini ainsi: +l'ensemble de ses sommets est $\Bool^n$ et pour chaque $x\in\Bool^n$ et +$s\in \mathcal{P}(\{1, \ldots, n\})$, le graphe $\Gamma(f)$ +contient un arc de $x$ vers $F_f(s,x)$. +La relation entre $\Gamma(f)$ et $G_f$ est claire: il existe un +chemin de $x$ à $x'$ dans $\Gamma(f)$ si et seulement s'il existe une +stratégie $S$ telle que les itérations parallèles $G_f$ à partir +du point $(S,x)$ mènent à un point $(.,x')$. + +Dans ce qui suit, et par souci de concision, le terme \emph{graphe des itérations} +est une abréviation de graphe des itérations chaotiques. +La figure~\ref{fig:xplgraphIter} donne deux exemples de graphes d'itérations +pour les fonctions $g$ et $h$ définies dans $\Bool^2$, qui sont reprises tout au long +de cet article. + +\begin{figure}[ht] + \begin{center} + \subfloat[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[width=\columnwidth]{images/g} + \end{center} + \end{minipage} + \label{fig:g:iter} + } + \subfloat[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[width=\columnwidth]{images/h} + \end{center} + \end{minipage} + \label{fig:h:iter} + } + \end{center} + \caption{Graphes d'itérations de fonctions booléennes dans $\Bool^2$.} + \label{fig:xplgraphIter} +\end{figure} + +% \subsection{Graphe d'interactions}\label{sub:sdd:inter} + +% Pour $x\in\Bool^n$ et $i\in\llbracket 1;n\rrbracket$, on nomme +% $\overline{x}^i$ la configuration obtenue en niant le +% $i^{\textrm{ème}}$ composant de $x$. En d'autres termes +% $\overline{x}^i=(x_1,\dots,\overline{x_i},\dots,x_n)$. +% Des interactions entre les composants du +% système peuvent être mémorisées +% dans la {\emph{matrice Jacobienne discrète}} $f'$. +% Celle-ci est définie comme étant la fonction qui à chaque +% configuration $x\in\Bool^n$ associe la matrice de taille +% $n\times n$ définie par : +% \[ +% f'(x)=(f'_{ij}(x)),\qquad +% f'_{ij}(x)=\frac{f_i(\overline{x}^j)-f_i(x)}{\overline{x}^j_j-x_j}\qquad (i,j\in\llbracket1;n\rrbracket). +% \] + +% On note que dans l'équation donnant la valeur de $f'_{ij}(x)$, les termes +% $f_i(\overline{x}^j)$, $f_i(x)$, $\overline{x}^j_j$ et $x_j$ sont considérés +% comme des entiers naturels égaux à $0$ ou à $1$ et que le calcul est effectué +% dans $\Z$. Cela est important car le signe des $f'_{ij}(x)$ nous donne une +% information supplémentaire sur la dynamique du système. + +% En outre, les interactions peuvent se représenter à l'aide d'un +% graphe $G(f)$ orienté et signé défini ainsi: +% l'ensemble des sommets est +% $\llbracket1;n\rrbracket$ et il existe un arc de $j$ à $i$ de signe +% $s\in\{-1,1\}$, noté $(j,s,i)$, si $f'_{ij}(x)=s$ pour au moins +% un $x\in\Bool^n$. +% On note que la présence de +% deux arcs de signes opposés entre deux sommets donnés +% est possible. + +% \begin{figure}%[t] +% \begin{center} +% \subfloat[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{ +% \begin{minipage}{0.40\textwidth} +% \begin{center} +% \includegraphics[height=3cm]{images/gp.pdf} +% \end{center} +% \end{minipage} +% \label{fig:g:inter} +% } +% \subfloat[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{ +% \begin{minipage}{0.40\textwidth} +% \begin{center} +% \includegraphics[height=3cm]{images/hp.pdf} +% \end{center} +% \end{minipage} +% \label{fig:h:inter} +% } \end{center} +% \caption{Graphes d'interactions de fonctions booléennes dans $\Bool^2$} +% \label{fig:xplgraphInter} +% \end{figure} + +% Soit $P$ une suite d'arcs de $G(f)$ de la forme +% \[ +% (i_1,s_1,i_2),(i_2,s_2,i_3),\ldots,(i_r,s_r,i_{r+1}). +% \] +% Alors, $P$ est dit un \emph{chemin} de $G(f)$ de longueur $r$ et de signe +% $\Pi_{i=1}^{r}s_i$ et $i_{r+1}$ est dit accessible depuis +% $i_1$. +% $P$ est un {\emph{circuit}} si $i_{r+1}=i_1$ et si les sommets +% $i_1$,\ldots $i_r$ sont deux à deux disjoints. +% Un sommet $i$ de $G(f)$ a une {\emph{boucle}} +% positive (resp. négative) , si $G(f)$ a un +% arc positif (resp. un arc négatif) de $i$ vers lui-même. + +% \subsection{Retards entre les éléments du système} +% \label{sub:sdd:retards} + +% La notion de retard provient initialement du besoin de prendre en compte les +% délais de transfert d'information entre les éléments du système. Lorsque l'on +% se place dans le contexte général, ces délais peuvent eux-mêmes varier dans le +% temps. On décrit donc le retard de l'élément $j$ par rapport à l'élément $i$ à +% l'instant $t$ par $r_j^i(t)$. Ainsi, l'information reçue de $j$ en $i$ à $t$ a +% été générée à l'instant (ou itération) $s_j^i(t)=t-r_j^i(t)$. On en déduit que +% la mise à jour de l'élément $i$ de l'instant $t$ à $t+1$ s'écrit : +% \begin{equation*} +% x_i(t+1) = f_i(x_1^{s_1^i(t)},x_2^{s_2^i(t)},\dots,x_i^t,\dots,x_{n-1}^{s_{n-1}^i(t)},x_n^{s_n^i(t)}) +% \end{equation*} +% On constate que même si le modèle le permet, on ne met généralement pas de délai +% entre l'élément $i$ et lui-même car cela n'a pas d'intérêt pratique fort. + +\subsection{Distance sur l'espace $\mathcal{P}(\{1, \ldots, n\})^{\Nats}\times \Bool^n$}\label{sub:metric} +Pour $A$ et $B$ deux ensembles de l'univers $\Omega$, +on rappelle la définition de l'opérateur +de \emph{différence ensembliste} symétrique : +\[ +A \Delta B = (A \cap \overline{B}) \cup (\overline{A} \cap B) +\] +où $\overline{B}$ désigne le complémentaire de $B$ dans $\Omega$. + +On considère l'espace $\mathcal{X}=\mathcal{P}(\{1, \ldots, n\})^{\Nats}\times +\Bool^n$ et +on définit la distance $d$ entre les points $X=(S,x)$ et +$X'=(S',x')$ de $\mathcal{X}$ par +\[ +d(X,X')= d_H(x,x')+d_S(S,S'),~\textrm{où}~ +\left\{ +\begin{array}{l} +\displaystyle{d_H(x,x')=\sum_{i=1}^n |x_i-x'_i|}\\[5mm] +\displaystyle{d_S(S,S')=\frac{9}{n}\sum_{t\in\Nats}\frac{|S_t \Delta S'_t|}{10^{t+1}}}. +\end{array} +\right.\,. +\] +On note que dans le calcul de $d_H(x,x')$ -- +appelée \gls{distanceHamming} (cf. glossaire) +entre $x$ et $x'$-- +les termes $x_i$ et $x'_i$ sont considérés comme des entiers naturels +égaux à $0$ ou à $1$ et que le calcul est effectué dans $\Z$. +On note aussi que le symbole $|.|$ est utilisé avec deux sémantiques +différentes dans ce calcul: +on somme des valeurs absolues dans la distance +de Hamming tandis que l'on somme des cardinalités d'ensemble dans +$d_S$. +De plus, la \gls{partieentiere} (cf. glossaire) +$\lfloor d(X,X')\rfloor$ est égale à $d_H(x,x')$ soit la distance +de Hamming entre $x$ et $x'$. +%D'autre part, $d(X,X')-\lfloor d(X,X')\rfloor=d_S(s,s')$ +%mesure la différence entre $s$ et $s'$. +On remarque que la partie décimale est inférieure à $10^{-l}$ si +et seulement si les $l$ premiers termes des deux stratégies sont égaux. +De plus, si la +$(l+1)^{\textrm{ème}}$ décimale +de $d_S(S,S')$ +n'est pas nulle, alors $s_l$ est différent de $s'_l$. + +La fonction $d$ est une somme de deux fonctions. +La fonction $d_H$ est la distance de Hamming; il est aussi établi que la +somme de deux distances est une distance. +Ainsi, pour montrer que $d$ est aussi une distance, il suffit +de montrer que $d_S$ en une aussi. + +Soit $S$, $S'$ et $S''$ trois parties de $\{1,\ldots,n\}$. +\begin{itemize} +\item De manière évidente, $d_s(S,S')$ est positive ou bien nulle si + et seulement si $S$ et $S'$ sont égales. +\item Comme la différence symétrique est commutative, la valeur de + $d_S(S,S')$ est égale à celle de $d_S(S',S)$. +\item On a enfin la succession d'éléments suivants: + $$ + \begin{array}{rcl} + S \Delta S' & = & (S \cap \overline{S'}) \cup (\overline{S} \cap S')\\ + & = & (S \cap \overline{S'} \cap S'' ) \cup (S \cap \overline{S'} \cap \overline{S''} ) \cup (\overline{S} \cap S'\cap S'') \cup (\overline{S} \cap S'\cap \overline{S''})\\ + & \subseteq & (S \cap \overline{S'} \cap S'' ) \cup (S \cap \overline{S'} \cap \overline{S''} ) \cup (\overline{S} \cap S'\cap S'') \cup (\overline{S} \cap S'\cap \overline{S''}) \cup \\ + & & (\overline{S} \cap \overline{S'} \cap S'') \cup (S \cap S' \cap \overline{S''} ) \cup (\overline{S} \cap \overline{S'} \cap S'') \cup (S \cap S' \cap \overline{S''})\\ + & = & (\overline{S'} \cap S'' ) \cup (S \cap \overline{S''} ) \cup (\overline{S} \cap S'') \cup (S'\cap \overline{S''}) \\ + & = & (S \Delta S'') \cup (S'' \Delta S') + \end{array} + $$ + On en déduit ainsi que +$|S \Delta S'| \le |S \Delta S''| + |S'' \Delta S'|$ et donc que +l'égalité triangulaire $d_S(S,S') \le d_S(S,S'') + d_S(S'',S')$ est établie. +\end{itemize} + +On peut démontrer que pour toute fonction booléenne $f$, +$G_f$ est continue sur $\mathcal{X}$ (cf.~annexe~\ref{anx:cont}). + +\subsection{Temps de mélange} +\label{sec:mixingtime} + +Le temps de mélange (\emph{mixing time})~\cite{LevinPeresWilmer2006}, est une +des métriques usuelles pour estimer la vitesse de convergence des lignes d'une +matrice de Markov vers une distribution spécifique. Elle est définie par le +nombre minimal d'itérations nécessaires pour obtenir une déviation inférieure à +un $\varepsilon$ donné pour chaque ligne de la matrice. + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "main" +%%% End: