X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/blobdiff_plain/7adee4533e3b5462c283ce03d98ef5c440600e42..0ed548dcbbb0d4580a211e1c8de4e76f4c4208ad:/intro.tex diff --git a/intro.tex b/intro.tex index cb79a58..dafa1cf 100644 --- a/intro.tex +++ b/intro.tex @@ -1,58 +1,50 @@ 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. +chosen due to their unpredictable character and their sensitiveness to initial conditions. +In most cases, these generators simply consist in iterating a chaotic function like +the logistic map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots +It thus remains to find optimal parameters in such functions so that attractors are +avoided, guaranteeing by doing so that generated numbers follow a uniform distribution. +In order to check the quality of the produced outputs, it is usual to test the +PRNGs (Pseudo-Random Number Generators) with statistical batteries like +the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite{LEcuyerS07}. + +In its general understanding, the chaos notion is often reduced to the strong +sensitiveness to the initial conditions (the well known ``butterfly effect''): +a continuous function $k$ defined on a metrical space is said +\emph{strongly sensitive to the initial conditions} if for all point +$x$ and all positive value $\epsilon$, it is possible to find another +point $y$, as close as possible to $x$, and an integer $t$ such that the distance +between the $t$-th iterates of $x$ and $y$, denoted by $k^t(x)$ and $k^t(y)$, +are larger than $\epsilon$. However, in his definition of chaos, Devaney~\cite{Devaney} +impose to the chaotic function two other properties called +\emph{transitivity} and \emph{regularity}. Functions evoked above have +been studied according to these properties, and they have been proven as chaotic on $\R$. +But nothing guarantees that such properties are preserved when iterating the functions +on floating point numbers, which is the domain of interpretation of real numbers $\R$ on +machines. + +To avoid this lack of chaos, we have previously presented some PRNGs that iterate +continuous functions $G_f$ on a discrete domain $\{ 1, \ldots, n \}^{\Nats} + \times \{0,1\}^n$, where $f$ is a Boolean function (\textit{i.e.}, $f : + \{0,1\}^n \rightarrow \{0,1\}^n$). These generators are +$\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11:ip}, +$\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip} and +$\chi_{\textit{14Secrypt}}$ \cite{chgw14oip} where \textit{CI} means +\emph{Chaotic Iterations}. +We have firstly proven in~\cite{bcgr11:ip} that, to establish the chaotic nature +of algorithm $\textit{CIPRNG}_f^1$, it is necessary and sufficient that the +asynchronous iterations are strongly connected. We then have proven that it is necessary +and sufficient that the Markov matrix associated to this graph is doubly stochastic, +in order to have a uniform distribution of the outputs. We have finally established +sufficient conditions to guarantee the first property of connectivity. Among the +generated functions, we thus considered for further investigations only the one that +satisfy the second property too. In~\cite{chgw14oip}, we have proposed an algorithmic +method allowing to directly obtain a strongly connected iteration graph having a doubly +stochastic Markov matrix. The research work presented here generalizes this latter article +by updating the iteration domain and the metric. The obtained algorithm owns the same +theoretical properties but with a reduced mixing time. + % % 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 @@ -223,6 +215,16 @@ chosen due to their unpredictable character and their sensibility to initial con % sur une batterie de tests. +The remainder of this article is organized as follows. The next section is devoted to +preliminaries, basic notations, and terminologies regarding asynchronous iterations. +Then, in Section~\ref{sec:proofOfChaos}, Devaney's definition of chaos is recalled +while the proofs of chaos of our most general PRNGs is provided. Section~\ref{sec:SCCfunc} shows how to generate functions and a number of iterations such that the iteration graph is strongly connected, making the +PRNG chaotic. The next section focus on examples of such graphs obtained by modifying the +hypercube, while Section~\ref{sec:prng} establishes the link between the theoretical study and +pseudorandom number generation. +This research work ends by a conclusion section, where the contribution is summarized and +intended future work is outlined. + % 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