From: Christophe Guyeux Date: Fri, 13 Mar 2015 15:44:07 +0000 (+0100) Subject: Début de l'intro X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/7adee4533e3b5462c283ce03d98ef5c440600e42 Début de l'intro --- diff --git a/intro.tex b/intro.tex index 097d514..cb79a58 100644 --- a/intro.tex +++ b/intro.tex @@ -1,60 +1,59 @@ -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,bcgr11:ip}, -$\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip} et -$\chi_{\textit{14Secrypt}}$ \cite{chgw14oip} où \textit{CI} signifie -\emph{Chaotic Iterations}. - -Dans~\cite{bcgr11:ip} nous avons tout d'abord prouvé que pour établir la nature -chaotique de l'algorithme $\textit{CIPRNG}_f^1$, il est nécessaire et suffisant -que le graphe des itérations asynchrones soit fortement connexe. Nous avons -ensuite prouvé que pour que la sortie de cet algorithme suive une loi de -distribution uniforme, il est nécessaire et suffisant que la matrice de Markov -associée à ce graphe soit doublement stochastique. Nous avons enfin établi des -conditions suffisantes pour garantir la première propriété de connexité. Parmi -les fonctions générées, on ne retenait ensuite que celles qui vérifiait la -seconde propriété. Dans~\cite{chgw14oip}, nous avons proposé une démarche -algorithmique permettant d'obtenir directement un graphe d'itérations fortement -connexe et dont la matrice de Markov est doublement stochastique. Le travail -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. - +The exploitation of chaotic systems to generate pseudorandom sequences is +an hot topic~\cite{915396,915385,5376454}. Such systems are fundamentally +chosen due to their unpredictable character and their sensibility to initial conditions. + +% 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,bcgr11:ip}, +% $\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip} et +% $\chi_{\textit{14Secrypt}}$ \cite{chgw14oip} où \textit{CI} signifie +% \emph{Chaotic Iterations}. +% +% Dans~\cite{bcgr11:ip} nous avons tout d'abord prouvé que pour établir la nature +% chaotique de l'algorithme $\textit{CIPRNG}_f^1$, il est nécessaire et suffisant +% que le graphe des itérations asynchrones soit fortement connexe. Nous avons +% ensuite prouvé que pour que la sortie de cet algorithme suive une loi de +% distribution uniforme, il est nécessaire et suffisant que la matrice de Markov +% associée à ce graphe soit doublement stochastique. Nous avons enfin établi des +% conditions suffisantes pour garantir la première propriété de connexité. Parmi +% les fonctions générées, on ne retenait ensuite que celles qui vérifiait la +% seconde propriété. Dans~\cite{chgw14oip}, nous avons proposé une démarche +% algorithmique permettant d'obtenir directement un graphe d'itérations fortement +% connexe et dont la matrice de Markov est doublement stochastique. Le travail +% 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\}$ @@ -234,15 +233,15 @@ mais un temps de mélange plus réduit. % 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. - +% 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 diff --git a/main.tex b/main.tex index b0f9c8a..2c42373 100644 --- a/main.tex +++ b/main.tex @@ -98,7 +98,7 @@ \begin{abstract} -This paper is dedicated to the desgin of chaotic random generators +This paper is dedicated to the design of chaotic random generators and extends previous works proposed by some of the authors. We propose a theoretical framework proving both the chaotic properties and that the limit distribution is uniform. @@ -110,7 +110,7 @@ the classical statsitcal tests. \maketitle \section{Introduction} -%\input{intro} +\input{intro} \section{\uppercase{Preliminaries}}\label{sec:preliminaries} \input{preliminaries}