X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/c8b7da5a49ee32f19091be950c39633b20b344e3..006d3c5dcaf6d769591b2496d592e87066b0ec42:/intro.tex?ds=sidebyside diff --git a/intro.tex b/intro.tex index 6460412..097d514 100644 --- a/intro.tex +++ b/intro.tex @@ -1,65 +1,65 @@ -L'exploitation de \og systèmes chaotiques\fg{} pour générer des séquences -pseudo-aléatoires est un sujet actif de recherche~\cite{915396,915385,5376454}. -Ces systèmes sont choisis principalement -en raison de leur imprévisibilité et de leur sensibilité aux conditions initiales. +L'exploitation de \og systèmes chaotiques\fg{} pour générer des séquences +pseudo-aléatoires est un sujet actif de recherche~\cite{915396,915385,5376454}. +Ces systèmes sont choisis principalement +en raison de leur imprévisibilité et de leur sensibilité aux conditions initiales. -Souvent les travaux se limitent à itérer une fonction paramétrée +Souvent les travaux se limitent à itérer une fonction paramétrée \emph{chaotique} comme la fonction logistique~\cite{915396,915385}, ou encore -celle du chat d'Arnold~\cite{5376454}\ldots Il reste à trouver les paramètres -optimaux permettant d'éviter les attracteurs de telles fonctions et garantissant -que les séquences de nombres produits suivent une loi de distribution uniforme. -Pour vérifier la qualité des sorties produites il est usuel de soumettre les -PRNG (Pseudo-Random Number Generator) à des tests statistiques tels +celle du chat d'Arnold~\cite{5376454}\ldots Il reste à trouver les paramètres +optimaux permettant d'éviter les attracteurs de telles fonctions et garantissant +que les séquences de nombres produits suivent une loi de distribution uniforme. +Pour vérifier la qualité des sorties produites il est usuel de soumettre les +PRNG (Pseudo-Random Number Generator) à des tests statistiques tels DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10} et TestU01~\cite{LEcuyerS07}. -Dans son acception vulgarisée, -la notion de chaos est souvent réduite à celle de forte sensibilité +Dans son acception vulgarisée, +la notion de chaos est souvent réduite à celle de forte sensibilité aux conditions initiales (le fameux \og \emph{effet papillon}\fg{}): -une fonction continue $k$ définie sur un espace métrique +une fonction continue $k$ définie sur un espace métrique est dite \emph{fortement sensible aux conditions initiales} si pour tout point $x$ et pour toute valeur positive $\epsilon$ il est possible de trouver un point $y$, arbitrairement proche de $x$, et un entier $t$ tels que la distance entre les -$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 +$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}, +\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 +$\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 +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. +présenté ici généralise ce dernier article en changeant le domaine d'itération, +et donc de métrique. L'algorithme obtenu possède les même propriétés théoriques +mais un temps de mélange plus réduit. -% Pour décrire un peu plus précisément le principe de -% la génération pseudo-aléatoire, considérons l'espace booléen +% Pour décrire un peu plus précisément le principe de +% la génération pseudo-aléatoire, considérons l'espace booléen % $\Bool=\{0,1\}$ % muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\bullet}$ \fg{} -% définies par les tableaux ci-dessous: +% définies par les tableaux ci-dessous: % \begin{center} % \begin{tabular}{|c|c|c|} @@ -90,64 +90,64 @@ mais un temps de m % \end{center} -% La fonction itérée est -% une fonction $f$ de $\Bool^n$ dans lui-même qui à +% La fonction itérée est +% une fonction $f$ de $\Bool^n$ dans lui-même qui à % un mot binaire $x = (x_1,\ldots,x_n)$ % associe le mot $(f_1(x),\ldots, f_n(x))$. -% Un exemple de fonction de $\Bool^n$ dans lui-même -% est la fonction négation -% définie par +% Un exemple de fonction de $\Bool^n$ dans lui-même +% est la fonction négation +% définie par % $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. -% Le principe itératif, basé sur le mode opératoire dit \emph{asynchrone}, est le -% suivant: à chaque itération $t$, on choisit un indice $i$ entre $1$ et $n$, et -% le mot $x^t = (x_1^t,\ldots,x_n^t)$ est remplacé par $x^{t+1} = (x_1^t,\ldots , +% Le principe itératif, basé sur le mode opératoire dit \emph{asynchrone}, est le +% suivant: à chaque itération $t$, on choisit un indice $i$ entre $1$ et $n$, et +% le mot $x^t = (x_1^t,\ldots,x_n^t)$ est remplacé par $x^{t+1} = (x_1^t,\ldots , % x_{i-1}^t, f_i(x^t), x_{i+1}^t,\ldots, x_n^t)$. -% Au bout d'un nombre $N$ d'itérations, si la fonction (notée $G_f$ dans ce -% document) que l'on peut associer à l'algorithme décrit ci-dessus a de \og -% \emph{bonnes}\fg{} propriétés chaotiques, le mot $x^N$ doit être \og \emph{très -% différent}\fg{} de $x^0$ de façon à sembler ne plus dépendre de $x_0$. En -% effet, pour un générateur aléatoire, il faut que la structure de $x^N$ semble -% être due au hasard; pour une application cryptographique, il faut qu'il soit -% matériellement impossible (dans les conditions techniques actuelles) de -% retrouver $x^0$ à partir de $x^N$. +% Au bout d'un nombre $N$ d'itérations, si la fonction (notée $G_f$ dans ce +% document) que l'on peut associer à l'algorithme décrit ci-dessus a de \og +% \emph{bonnes}\fg{} propriétés chaotiques, le mot $x^N$ doit être \og \emph{très +% différent}\fg{} de $x^0$ de façon à sembler ne plus dépendre de $x_0$. En +% effet, pour un générateur aléatoire, il faut que la structure de $x^N$ semble +% être due au hasard; pour une application cryptographique, il faut qu'il soit +% matériellement impossible (dans les conditions techniques actuelles) de +% retrouver $x^0$ à partir de $x^N$. % Tous les mots de $\Bool^n$ peuvent constituer les $2^n$ sommets d'un % \gls{graphoriente} (cf. glossaire) dans lequel un arc relie deux sommets $x$ et -% $x'$ s'il existe une itération de l'algorithme de génération qui permet de -% passer directement de $x$ à $x'$. Ce graphe est appelé le \emph{graphe d'itérations} et +% $x'$ s'il existe une itération de l'algorithme de génération qui permet de +% passer directement de $x$ à $x'$. Ce graphe est appelé le \emph{graphe d'itérations} et % nous montrons ici que si l'on a un \gls{graphfortementconnexe} (cf. glossaire), % alors la fonction $G_f$ est transitive, donc chaotique. -% Enfin, un bon générateur aléatoire se doit de +% Enfin, un bon générateur aléatoire se doit de % fournir des nombres selon une \gls{distributionuniforme} (cf. glossaire). -% La dernière partie de cet article donne, -% dans le cas où le graphe d'itérations est fortement connexe, -% une condition nécessaire et suffisante pour que -% cette propriété soit satisfaite. +% La dernière partie de cet article donne, +% dans le cas où le graphe d'itérations est fortement connexe, +% une condition nécessaire et suffisante pour que +% cette propriété soit satisfaite. -% Le chaos a été appliqué à des domaines variés en +% Le chaos a été appliqué à des domaines variés en % informatique, comme les fonctions de hachage, -% la stéganographie, la génération de nombres pseudo -% aléatoires\ldots -% Toutes ces applications exploitent les propriétés définissant des -% fonctions chaotiques et énoncées par Devaney, telles que la -% transitivité, la régularité et la sensibilité aux conditions initiales. - - -% Les systèmes dynamiques \emph{chaotiques} sont des processus itératifs -% définis par une fonction chaotique $f$ d'un domaine $E$ dans lui-même. -% En démarrant d'un état quelconque $x$ du sytème, -% nommé par la suite \emph{configuration}, -% le système construit la séquence $x$, $f(x)$, $f^2(x)$, $f^3(x)$, \dots -% où $f^k(x)$ est le $k^{\textrm{ème}}$ itéré de $f$ en $x$. +% la stéganographie, la génération de nombres pseudo +% aléatoires\ldots +% Toutes ces applications exploitent les propriétés définissant des +% fonctions chaotiques et énoncées par Devaney, telles que la +% transitivité, la régularité et la sensibilité aux conditions initiales. + + +% Les systèmes dynamiques \emph{chaotiques} sont des processus itératifs +% définis par une fonction chaotique $f$ d'un domaine $E$ dans lui-même. +% En démarrant d'un état quelconque $x$ du sytème, +% nommé par la suite \emph{configuration}, +% le système construit la séquence $x$, $f(x)$, $f^2(x)$, $f^3(x)$, \dots +% où $f^k(x)$ est le $k^{\textrm{ème}}$ itéré de $f$ en $x$. % La plupart des applications informatiques dite \og chaotiques \fg{} -% sont basées sur des processus itératifs de la forme $x^{n+1} = f(x^n)$ -% où $f$ est la fonction \emph{tente} avec $x^0 = 0,4001$ (donnée à la figure~\ref{fig:iter:tent}) -% ou la fonction \emph{logistique} avec $\mu = 3,45$ et $x^0 = 0,1$ (donnée à la figure~\ref{fig:iter:log}) -% connues pour être chaotiques dans $\R$. +% sont basées sur des processus itératifs de la forme $x^{n+1} = f(x^n)$ +% où $f$ est la fonction \emph{tente} avec $x^0 = 0,4001$ (donnée à la figure~\ref{fig:iter:tent}) +% ou la fonction \emph{logistique} avec $\mu = 3,45$ et $x^0 = 0,1$ (donnée à la figure~\ref{fig:iter:log}) +% connues pour être chaotiques dans $\R$. % \begin{figure}[hb] % \begin{center} @@ -168,80 +168,80 @@ mais un temps de m % \label{fig:iter:log} % } % \end{center} -% \caption{Systèmes itératifs basés sur des fonctions chaotiques dans $\R$ \label{fig:iter}} +% \caption{Systèmes itératifs basés sur des fonctions chaotiques dans $\R$ \label{fig:iter}} % \end{figure} -% Cependant il n'a pas été établi que des fonctions prouvées -% comme étant chaotiques sur $\R$ le restent sur les nombres à virgule flottante, -% qui est le domaine d'interprétation informatique des réels. -% On souhaite ainsi éviter une éventuelle perte des propriétés de chaos -% lors de l'exécution des programmes implémentant ces fonctions. -% Ce document présente pour cela l'alternative suivante: -% à partir d'une fonction booléenne, $f: \Bool^n \rightarrow \Bool^n$, -% où $\Bool$ est le domaine des booléens $\{0,1\}$, on +% Cependant il n'a pas été établi que des fonctions prouvées +% comme étant chaotiques sur $\R$ le restent sur les nombres à virgule flottante, +% qui est le domaine d'interprétation informatique des réels. +% On souhaite ainsi éviter une éventuelle perte des propriétés de chaos +% lors de l'exécution des programmes implémentant ces fonctions. +% Ce document présente pour cela l'alternative suivante: +% à partir d'une fonction booléenne, $f: \Bool^n \rightarrow \Bool^n$, +% où $\Bool$ est le domaine des booléens $\{0,1\}$, on % construit une fonction $G_f : \llbracket 1 ; n \rrbracket^{\Nats} \times \Bool^n$, -% où $\llbracket 1 ; n \rrbracket$ est l'ensemble des entiers -% $\{1, 2, \hdots, n\}$ et on itère celle-ci. -% Comme $f$ est discrète, $G_f$ l'est aussi et les résultats théoriques -% obtenus sur $G_f$, notamment sa chaoticité, sont maintenus durant -% l'implémentation. -% Un exemple de fonction booléenne de $\Bool^n$ dans lui-même est la fonction négation -% définie par +% où $\llbracket 1 ; n \rrbracket$ est l'ensemble des entiers +% $\{1, 2, \hdots, n\}$ et on itère celle-ci. +% Comme $f$ est discrète, $G_f$ l'est aussi et les résultats théoriques +% obtenus sur $G_f$, notamment sa chaoticité, sont maintenus durant +% l'implémentation. +% Un exemple de fonction booléenne de $\Bool^n$ dans lui-même est la fonction négation +% définie par % $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. -% De plus, plutôt que de trouver des exemples de telles fonctions $f$, et de prouver -% (\textit{a posteriori}) la chaoticité de $G_f$, on peut penser à caractériser -% les fonctions engendrant systématiquement des fonctions chaotiques. -% Ce document présente une telle caractérisation -% qui s'exprime sur le graphe des itérations asynchrones -% de la fonction booléenne $f$, qui est, intuitivement, le graphe -% de toutes les itérations possibles de la fonction. -% Cette situation se réduit en un problème portant sur des graphes à $2^n$ +% De plus, plutôt que de trouver des exemples de telles fonctions $f$, et de prouver +% (\textit{a posteriori}) la chaoticité de $G_f$, on peut penser à caractériser +% les fonctions engendrant systématiquement des fonctions chaotiques. +% Ce document présente une telle caractérisation +% qui s'exprime sur le graphe des itérations asynchrones +% de la fonction booléenne $f$, qui est, intuitivement, le graphe +% de toutes les itérations possibles de la fonction. +% Cette situation se réduit en un problème portant sur des graphes à $2^n$ % sommets. -% Ainsi pour étendre l'applicabilité de cette caractérisation, on s'intéresse +% Ainsi pour étendre l'applicabilité de cette caractérisation, on s'intéresse % au graphe des interactions de $f$, qui, intuitivement, -% représente les dépendances entre les $f_i$, $1\le i \le n$ et les $i$ -% et qui ne contient que $n$ sommets (et qui est à comparer aux $2^n$ +% représente les dépendances entre les $f_i$, $1\le i \le n$ et les $i$ +% et qui ne contient que $n$ sommets (et qui est à comparer aux $2^n$ % sommets. -% Sur ce graphe on exprime des conditions garantissant la chaoticité de la fonction $G_f$. -% Ainsi, toutes les fonctions $G_f$ engendrées à partir d'un graphe -% d'interactions de $f$ aux propriétés \textit{ad hoc} seront chaotiques. +% Sur ce graphe on exprime des conditions garantissant la chaoticité de la fonction $G_f$. +% Ainsi, toutes les fonctions $G_f$ engendrées à partir d'un graphe +% d'interactions de $f$ aux propriétés \textit{ad hoc} seront chaotiques. -% Se pose enfin l'applicabilité des fonctions $G_f$ à la génération -% de nombres pseudo aléatoires, l'aléa étant intuitivement +% Se pose enfin l'applicabilité des fonctions $G_f$ à la génération +% de nombres pseudo aléatoires, l'aléa étant intuitivement % une notion proche de celle du chaos. -% Pour aborder cette classe de problèmes, on remarque que l'on doit au moins -% garantir que l'ensemble des valeurs retournées par l'algorithme suit -% une loi uniforme, propriété qui n'est pas imposée d'un point de vue topologique. -% Ce document montre que cette contrainte peut s'exprimer à nouveau sur le graphe des itérations asynchrones de $f$ -% et qu'on peut ainsi filtrer les bons candidats à la génération de nombres pseudo aléatoires. -% Cette idée est validée après évaluation -% des générateurs de nombres pseudo aléatoires +% Pour aborder cette classe de problèmes, on remarque que l'on doit au moins +% garantir que l'ensemble des valeurs retournées par l'algorithme suit +% une loi uniforme, propriété qui n'est pas imposée d'un point de vue topologique. +% Ce document montre que cette contrainte peut s'exprimer à nouveau sur le graphe des itérations asynchrones de $f$ +% et qu'on peut ainsi filtrer les bons candidats à la génération de nombres pseudo aléatoires. +% Cette idée est validée après évaluation +% des générateurs de nombres pseudo aléatoires % sur une batterie de tests. -% Le reste de ce document est organisé comme suit. -% La section~\ref{section:chaos} présente ce qu'est un système dynamique discret booléen itérant une fonction $f$. -% La chaoticité de la fonction engendrée $G_f$ est caractérisée en +% Le reste de ce document est organisé comme suit. +% La section~\ref{section:chaos} présente ce qu'est un système dynamique discret booléen itérant une fonction $f$. +% La chaoticité de la fonction engendrée $G_f$ est caractérisée en % section~\ref{sec:charac}. -% Des conditions suffisantes pour obtenir cette chaoticité sont présentées en +% Des conditions suffisantes pour obtenir cette chaoticité sont présentées en % section~\ref{sec:sccg}. -% L'application à la génération de nombres pseudo aléatoires est formalisée, -% les fonctions dont l'image est uniformément distribuée sur le domaine sont -% caractérisées et les générateurs sont évalués en section~\ref{sec:prng}. - -Dans la section suivante, nous rappelons les notions élémentaires sur les -systèmes booléens. La section~\ref{section:caracterisation} présente les -définitions théoriques liées au chaos. Ensuite, une application de ces résultats -à la génération de nombres pseudo-aléatoires est proposée en -section~\ref{section:genpa} ainsi qu'une méthode permettant d'obtenir des -matrices d'itérations doublement stochastiques en -section~\ref{section:genmat}. Enfin, en section~\ref{section:expes} la qualité -du PRNG obtenu est éprouvée avec les tests standards du domaine. +% L'application à la génération de nombres pseudo aléatoires est formalisée, +% les fonctions dont l'image est uniformément distribuée sur le domaine sont +% caractérisées et les générateurs sont évalués en section~\ref{sec:prng}. + +Dans la section suivante, nous rappelons les notions élémentaires sur les +systèmes booléens. La section~\ref{section:caracterisation} présente les +définitions théoriques liées au chaos. Ensuite, une application de ces résultats +à la génération de nombres pseudo-aléatoires est proposée en +section~\ref{section:genpa} ainsi qu'une méthode permettant d'obtenir des +matrices d'itérations doublement stochastiques en +section~\ref{section:genmat}. Enfin, en section~\ref{section:expes} la qualité +du PRNG obtenu est éprouvée avec les tests standards du domaine. %%% Local Variables: