X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/3759a997c005ffb313be135f98820410cb6061b4..ac26aa33009d503bf9c04a2b00244c5bf723e694:/15RairoGen.tex

diff --git a/15RairoGen.tex b/15RairoGen.tex
index a57e19f..c1cf7d3 100644
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -8,16 +8,70 @@ comme un gÃ©nÃ©rateur alÃ©atoire.
 
 Ce chapitre  prÃ©sente donc une application directe
 de la thÃ©orie dÃ©veloppÃ©e ci-avant
-Ã  la gÃ©nÃ©ration de nombres pseudo alÃ©atoires. 
+Ã  la gÃ©nÃ©ration de nombres pseudo-alÃ©atoires. 
+La section~\ref{sec:PRNG:chaos:autres} prÃ©sente un Ã©tat de l'art (incomplet) de l'exploitation de 
+fonctions au comportement chaotique pour obtenir des PRNGs.
 La section~\ref{sub:prng:algo} 
-prÃ©sente tout d'abord l'algorithme de PRNG. La contrainte de  
+prÃ©sente ensuite l'algorithme de PRNG. La contrainte de  
 distribution uniforme de la sortie est discutÃ©e dans cette section.
-La chaoticitÃ© du gÃ©nÃ©rateur est ensuite Ã©tudiÃ©e en 
+La chaoticitÃ© du gÃ©nÃ©rateur est  Ã©tudiÃ©e en 
 section~\ref{prng:unaire:chaos}.
 La section~\ref{sub:prng:algo}  a Ã©tÃ© publiÃ©e Ã  ~\cite{bcgw11:ip,bcgr11:ip}.
 
+\section{Quelques PRNGs basÃ©s sur des fonctions aux itÃ©rations chaotiques}\label{sec:PRNG:chaos:autres}
+
+Les PRNGs chaotiques (CPRNGs) sont des gÃ©nÃ©rateurs non linÃ©aires dÃ©finis par 
+$x_0 \in \mathbb{R}$ et $x_{t+1} = f(x_t)$, oÃ¹  $f$ est une fonction au comportement chaotique.
+Les raisons qui expliquent l'intÃ©rÃªt de telles fonctions sont naturellement la sensibilitÃ© aux conditions initiales, 
+leur imprÃ©visibilitÃ©\ldots Cependant, comme l'ordinateur sur lequel elles s'exÃ©cutent a une prÃ©cision finie, 
+les gÃ©nÃ©rateurs qui les embarquent peuvent avoir des pÃ©riodes arbitrairement courtes, 
+ne pas fournir de sortie selon une distribution uniforme\ldots
+D'un point de vue cryptographique, ces CPRNGs sont critiquables~\cite{wiggins2003introduction}.
+RÃ©duire ces critiques est l'objectif de nombreux travaux de recherche reportÃ©s ci dessous.
+
+
+Parmi les suites simples classiquement embarquÃ©es dans les CPRNGs, on trouve principalement
+la suite logistique et 
+la suite de HÃ©non. La suite logistique~\cite{may1976simple} est dÃ©finie de $[0;1]$ dans lui mÃªme par $x_{t+1} = r \times x_t(1-x_t)$ 
+avec $x_0 \in [0;1]$ et $3,57<r<4,0$.
+La suite de HÃ©non~\cite{henon1976two} de $A \times B$ dans lui mÃªme, avec $A$ et $B$ deux sous-ensembles de $\R$, 
+est dÃ©finie par  
+$x_{t+1} = (1-a x_t^2)+y_t$  et $y_{t+1}= bx_{t+1}$, oÃ¹ $a$ et $b$ sont les paramÃ¨tres canoniques. 
+Pour $a=1,4$, $b=0,3$, $A=[-1,5;1,5]$ et $B=-[0,4;0,4]$ le comportement de cette suite est chaotique.
+
+La suite logistique est utilisÃ©e dans l'article~\cite{dabal2011chaos} dans lequel 
+les auteurs utilisent une reprÃ©sentation des rÃ©els Ã  virgule fixe.
+Les auteurs de~\cite{dabal2012fpga} comparent leur implantation de la suite logistique avec celle 
+de la suite de HÃ©non. 
+Les auteurs de~\cite{6868789} ont exploitÃ© la rÃ©Ã©criture de la suite logistique sous la forme
+$x_{t+1} = (r \times x_t)-(r \times x_t^2)$ et la possibilitÃ© de parallÃ©liser ceci 
+pour accroÃ®tre la frÃ©quence du PRNG.   
+Les auteurs de~\cite{liu2008improved} proposent de coupler deux suites logistiques,
+chacune Ã©tant paramÃ©trÃ©e diffÃ©remment ($x_0$, $r_1$ et  $y_0$, $r_2$ respectivement). L'idÃ©e principale 
+est de modifier iterrativement le paramÃ¨tre $r_2$ Ã  l'aide des itÃ©rÃ©s de $x_t$.
+Quant aux auteurs de~\cite{merahcoupling13}, ils couplent la suite logistique et celle de HÃ©non. 
+La premiÃ¨re suite sert Ã  sÃ©lectionner les Ã©lÃ©ments parmi ceux gÃ©nÃ©rÃ©s par la seconde.
+Les auteurs de~\cite{mao2006design}, combinent spatialement $L$ suites logistiques 
+et construisent ainsi $x_t(0)$, \dots, $x_t(L-1)$ selon l'Ã©quation suivante:
+\begin{equation}
+x_{t+1}(i) = 
+(1- \varepsilon) f(x_t(i)) + 
+\frac{\varepsilon}{2} 
+(f(x_t(i-1)) + f(x_t(i+1))),
+\label{eq:cml}
+\end{equation}
+\noindent oÃ¹ 
+$i \in \dfrac{\Z}{L\Z}$,
+$f$ est une adaptation de la suite logistique au cas discret,
+la graine $(X_0(0),\dots, X_0(L-1))$ et la pondÃ©ration $\varepsilon$ sont fournies par l'utilisateur.
+ 
+Certaines Ã©quations diffÃ©rentielles ont Ã©tÃ© Ã  la base de PRNGs chaotiques. 
+On pense aux Ã©quations de Lorenz~\cite{Lorenz1963}, Ã  celles de RÃ¶ssler~\cite{Rossler1976397}\ldots
+Celles-ci ont par exemple embarquÃ©es dans les PRNG dans les articles~\cite{Silva:2009:LLP:1592409.1592411}
+et~\cite{mansingka2013fibonacci} respectivement.
 
-\section{ Nombres pseudo alÃ©atoires construits par itÃ©rations unaires}\label{sub:prng:algo}
+
+\section{ Nombres pseudo-alÃ©atoires construits par itÃ©rations unaires}\label{sub:prng:algo}
 
 
 
@@ -44,8 +98,8 @@ return $x$\;
 \end{algorithm}
 
 \subsection{Algorithme d'un gÃ©nÃ©rateur}
-On peut penser Ã  construire un gÃ©nÃ©rateur de nombres pseudo 
-alÃ©atoires comme dans l'algorithme~\ref{CI Algorithm} donnÃ© ci-dessous.
+On peut penser Ã  construire un gÃ©nÃ©rateur de nombres 
+pseudo-alÃ©atoires comme dans l'algorithme~\ref{CI Algorithm} donnÃ© ci-dessous.
 
 
 Celui-ci prend en entrÃ©e: une fonction $f$;
@@ -56,7 +110,7 @@ la fonction $F_{f_u}$ (Ã©quation~\ref{eq:iterations:unaires}
 vue au chapitre~\ref{chap:carachaos}) et correspondant 
 Ã  des itÃ©rations unaires.
 En interne, il exploite un algorithme de gÃ©nÃ©ration
-de nombres pseudo alÃ©atoires donnÃ© en paramÃ¨tre.
+de nombres pseudo-alÃ©atoires donnÃ© en paramÃ¨tre.
 Cela peut Ãªtre n'importe quel PRNG (XORshift, Mersenne-Twister) dont la 
 sortie est uniformÃ©ment distribuÃ©e.
 Notre approche vise a donner des propriÃ©tÃ©s de chaos Ã  ce gÃ©nÃ©rateur embarquÃ©.
@@ -139,7 +193,7 @@ et les chaÃ®nes de Markov.
 
 Montrons sur un exemple jouet Ã  deux Ã©lÃ©ments 
 que ce thÃ©orÃ¨me permet de vÃ©rifier si la sortie d'un gÃ©nÃ©rateur de 
-nombres pseudo alÃ©atoires est uniformÃ©ment distribuÃ©e ou non.
+nombres pseudo-alÃ©atoires est uniformÃ©ment distribuÃ©e ou non.
 Soient alors $g$ et $h$ deux fonctions  de $\Bool^2$
 dÃ©finies par $g(x_1,x_2)=(\overline{x_1},x_1.\overline{x_2}) $
 et $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$.
@@ -149,7 +203,7 @@ Leurs graphes d'itÃ©rations
 sont donc fortement connexes, ce que l'on peut vÃ©rifier aux figures~\ref{fig:g:iter} 
 et~\ref{fig:h:iter}.
 \textit{A priori}, ces deux fonctions pourraient Ãªtre intÃ©grÃ©es
-dans un gÃ©nÃ©rateur de nombres pseudo alÃ©atoires. Montrons que ce n'est pas le cas pour $g$ et 
+dans un gÃ©nÃ©rateur de nombres pseudo-alÃ©atoires. Montrons que ce n'est pas le cas pour $g$ et 
 que cela l'est pour $h$.
 
 
@@ -283,10 +337,10 @@ Alors d'aprÃ¨s le thÃ©orÃ¨me~\ref{th},
 pour n'importe quel vecteur initial de probabilitÃ©s $\pi^0$, on a 
 $\lim_{k \to \infty} \pi^0 M^k_g = \pi_g$ et 
 $\lim_{k \to \infty} \pi^0 M^k_h = \pi_h$. 
-Ainsi la chaÃ®ne de Markov associÃ© Ã  $h$ tend vers une 
+Ainsi la chaÃ®ne de Markov associÃ©e Ã  $h$ tend vers une 
 distribution uniforme, contrairement Ã  celle associÃ©e Ã  $g$.
 On en dÃ©duit que $g$ ne devrait pas Ãªtre itÃ©rÃ©e dans 
-un gÃ©nÃ©rateur de nombres pseudo alÃ©atoires.
+un gÃ©nÃ©rateur de nombres pseudo-alÃ©atoires.
 Au contraire, 
 $h$ devrait pouvoir Ãªtre embarquÃ©e dans l'algorithme~\ref{CI Algorithm}, 
 pour peu que le nombre $b$ d'itÃ©rations entre deux mesures successives 
@@ -303,7 +357,7 @@ On Ã©nonce directement le thÃ©orÃ¨me suivant dont la preuve est donnÃ©e en annex
   dÃ©finie par 
   $M = \dfrac{1}{n} \check{M}$.
   Si $\textsc{giu}(f)$ est fortement connexe, alors 
-  la sortie du gÃ©nÃ©rateur de nombres pseudo alÃ©atoires dÃ©taillÃ© par 
+  la sortie du gÃ©nÃ©rateur de nombres pseudo-alÃ©atoires dÃ©taillÃ© par 
   l'algorithme~\ref{CI Algorithm} suit une loi qui 
   tend vers la distribution uniforme si 
   et seulement si  $M$ est une matrice doublement stochastique.
@@ -325,7 +379,7 @@ Expliquons enfin comment a Ã©tÃ© calculÃ© le nombre de la troisiÃ¨me
 colonne utilisÃ© comme le paramÃ¨tre $b$ 
 dans l'algorithme~\ref{CI Algorithm}.
 
-Soit $e_i$ le $i^{\textrm{Ã¨me}}$ vecteur la base canonique de $\R^{2^{n}}$. 
+Soit $e_i$ le $i^{\textrm{Ã¨me}}$ vecteur de la base canonique de $\R^{2^{n}}$. 
 Chacun des Ã©lÃ©ments $v_j$, $1 \le j \le 2^n$, 
 du vecteur $e_i M_f^t$ reprÃ©sente la probabilitÃ© 
 d'Ãªtre dans la configuration $j$ aprÃ¨s $t$ Ã©tapes du processus de Markov 
@@ -431,7 +485,7 @@ $\mathcal{F}_{16}$ &14, 15, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
 
 La qualitÃ© des sÃ©quences alÃ©atoires a Ã©tÃ© Ã©valuÃ©e Ã  travers la suite 
 de tests statistiques dÃ©veloppÃ©e pour les gÃ©nÃ©rateurs de nombres 
-pseudo alÃ©atoires par le 
+pseudo-alÃ©atoires par le 
 \emph{National Institute of Standards and Technology} (NIST).
 L'expÃ©rience a montrÃ© notamment que toutes ces fonctions
 passent avec succÃ¨s cette batterie de tests.
@@ -758,6 +812,8 @@ est fortement connexe.
 % \end{proof}
 
 
+
+
 \section{Conclusion}
 Ce chapitre a proposÃ© un algorithme permettant de construire un 
 PRNG chaotique Ã  partir d'un PRNG existant. Pour ce faire, il est nÃ©cessaire 
