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 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.

% 
% 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\}$
% 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: 
