relecture preuve PCH

[rairo15.git] / intro.tex

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: