]> AND Private Git Repository - hdrcouchot.git/blobdiff - 15RairoGen.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
la veille
[hdrcouchot.git] / 15RairoGen.tex
index 432991fb638780d70496df8040141d53282eeb99..6832d33b0bc2c5aeb337274a438e1a220745248d 100644 (file)
@@ -8,16 +8,82 @@ 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,  
+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.
+
+René Lozi a aussi étudié la construction de PRNGs en couplant 
+des suites de Lozi~\cite{espinelrojas:hal-00622989} (qui sont une variation des suites de Hénon: $x^2_t$ est remplacé par $| x_t|$),
+la suite tente~\cite{DBLP:journals/ijbc/Lozi12} et en extrayant des 
+sous-suites pour construire la sortie du PRNG~\cite{lozi:hal-00813087}. 
+
 
-\section{ Nombres pseudo aléatoires construits par itérations unaires}\label{sub:prng:algo}
+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}
 
 
 
@@ -44,8 +110,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,10 +122,10 @@ 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 a ce générateur embarqué.
+Notre approche vise a donner des propriétés de chaos à ce générateur embarqué.
 
 
 % \textit{Random}$(l)$. 
@@ -97,11 +163,11 @@ Notre approche vise a donner des propriétés de chaos a ce générateur embarqu
 
 Nous avons vu au chapitre~\ref{chap:carachaos} que 
 $G_{f_u}$ est chaotique dans l'espace $\mathcal{X}_u$ 
-si et seulement le graphe d'itérations $\textsc{giu}(f)$ 
+si et seulement si le graphe d'itérations $\textsc{giu}(f)$ 
 est fortement connexe.
 Pour $b=1$, l'algorithme itère la fonction $F_{f_u}$.
 
-Pour simuler au mieux l'aléa, un bon générateur de nombre pseudo-aléatoires
+Pour simuler au mieux l'aléa, un bon générateur de nombres pseudo-aléatoires
 se doit de fournir  des nombres selon une distribution uniforme.
 Regardons comment l'uniformité de la distribution 
 contraint la fonction $f$ à itérer.
@@ -118,7 +184,7 @@ si  la propriété suivante est établie:
 $$\exists k \in \mathds{N}^\ast, \forall i,j \in \llbracket 1; n \rrbracket, M_{ij}^k>0.$$
 
 On énonce le théorème classique suivant liant les 
-vecteur de probabilités 
+vecteurs de probabilités 
 et les chaînes de Markov.
 
 
@@ -139,8 +205,8 @@ 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.
-Soit alors $g$ et $h$ deux fonctions  de $\Bool^2$
+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)$.
 Leurs graphes d'interactions donnés en figure \ref{fig:g:inter} et \ref{fig:h:inter}
@@ -149,7 +215,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 +349,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 
@@ -294,16 +360,16 @@ de valeurs  soit suffisamment grand de sorte que
 le vecteur d’état de la chaîne de Markov
 ait une distribution suffisamment proche de la distribution uniforme.
 
-On énonce directement le théorème suivant dont la preuve est donnée en annexes~\ref{anx:generateur}.
+On énonce directement le théorème suivant dont la preuve est donnée en annexe~\ref{anx:generateur}.
 
 \begin{restatable}[Uniformité de la sortie de l'algorithme~\ref{CI Algorithm}]{theorem}{PrngCIUniforme}\label{thm:prng:u}
-  Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son 
+  Soit $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$, $\textsc{giu}(f)$ son 
   graphe d'itérations , $\check{M}$ sa matrice d'adjacence
   et $M$ une matrice  $2^n\times 2^n$  
   définie par 
-  $M = \dfrac{1}{n} \check{M}$.
+  $M = \dfrac{1}{\mathsf{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,22 +391,22 @@ 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}}$. 
-Chacun des éléments $v_j$, $1 \le j \le 2^n$, 
+Soit $e_i$ le $i^{\textrm{ème}}$ vecteur de la base canonique de $\R^{2^{\mathsf{N}}}$. 
+Chacun des éléments $v_j$, $1 \le j \le 2^{\mathsf{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 
 associé à $\textsc{giu}(f)$ en partant de la configuration $i$.   
 Le nombre $\min \{
  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
 \}$ représente le plus petit nombre d'itérations où la distance de 
-ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^n})$
+ce vecteur au vecteur $\pi=(\frac{1}{2^{\mathsf{N}}},\ldots,\frac{1}{2^{\mathsf{N}}})$
 -- autrement dit, où la déviation par rapport à la distribution uniforme --
  est inférieure 
 à $10^{-4}$. En prenant le max pour tous les $e_i$, on obtient une valeur pour
  $b$. 
 Ainsi, on a 
 \begin{equation}
-b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} 
+b = \max\limits_{i \in \llbracket 1, 2^{\mathsf{N}} \rrbracket} 
 \left\{
 \min \left\{
  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
@@ -431,7 +497,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.
@@ -473,12 +539,12 @@ $F_{{f_u},p_i} :  \mathds{B}^\mathsf{N} \times [\mathsf{N}]^{p_i}
 \rightarrow \mathds{B}^\mathsf{N}$ définie par
 
 $$
-F_{f_u,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1}))  \mapsto 
+F_{f_u,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1}))  = 
 F_{f_u}(\hdots (F_{f_u}(F_{f_u}(x,u^0), u^1), \hdots), u^{p_i-1}).
 $$
 
 
-on construit l'espace 
+On construit l'espace 
  $\mathcal{X}_{\mathsf{N},\mathcal{P}}=  \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}}$, où
 $\mathds{S}_{\mathsf{N},\mathcal{P}}=
 [\mathsf{N}]^{\Nats}\times 
@@ -504,7 +570,7 @@ sur la seconde.
 Ainsi, les  sorties  $(y^0, y^1, \hdots )$ produites par le générateur détaillé dans 
 l'algorithme~\ref{CI Algorithm}
 sont les premiers  composants des itérations $X^0 = (x^0, (u,v))$ et $\forall n \in \mathds{N}, 
-X^{n+1} = G_{f_u,\mathcal{P}}(X^n)$ dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ où
+X^{n+1} = G_{f_u,\mathcal{P}}(X^{\mathsf{N}})$ dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ où
 $G_{f_u,\mathcal{P}}$  est définie par:
 
 
@@ -528,7 +594,7 @@ où $s=(u,v)$ et $\check{s}=(\check{u},\check{v})$ sont dans $ \mathds{S}_{\math
 \mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. 
 \begin{enumerate}
 \item $e$ et $\check{e}$ sont des entiers appartenant à $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. 
-La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ sur entre les 
+La distance de Hamming $d_{\mathds{B}^\mathsf{N}}$ entre les 
 décompositions binaires de $e$ et de $\check{e}$ (\textit{i.e.}, le 
 le nombre de bits qu'elles ont de différent) constitue 
 la partie entière de $d(X,\check{X})$.
@@ -558,7 +624,7 @@ jusqu'à atteindre
 $p+n\times \max{(\mathcal{P})}$ éléments.
 \item Si $v^0<\check{v}^0$, alors les $ \max{(\mathcal{P})}$  blocs de $n$
 éléments sont $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$,
-$\check{u}^{v^0}$ (sur $n$ éléments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ éléments), suivi par des 0, si besoin.
+$\check{u}^{v^0}$ (sur $n$ éléments), ..., $\check{u}^{\check{v}^0-1}$ (sur $n$ éléments), suivis par des 0, si besoin.
 \item Le cas $v^0>\check{v}^0$ est similaire, et donc omis
 \end{enumerate}
 \item Les $p$ suivants sont $|v^1-\check{v}^1|$, etc.
@@ -615,7 +681,7 @@ On prend alors le $v^0=1$ premier terme de $u$,
 chaque terme étant codé sur $n=2$ éléments, soit 06.
 Comme on itère au plus $\max{(\mathcal{P})}$ fois, 
 on complète cette valeur par des 0 de sorte que 
-la chaîne obtenue a $n\times \max{(\mathcal{P})}=22$ éléments, soit:
+la chaîne obtenue ait $n\times \max{(\mathcal{P})}=22$ éléments, soit:
 0600000000000000000000. 
 De manière similaire, les $\check{v}^0=2$ premiers
 termes de $\check{u}$ sont représentés par 
@@ -652,7 +718,7 @@ la séquence.
 
 
 
-On a la proposition suivante, qui est démontrée en annexes~\ref{anx:generateur}.
+On a la proposition suivante, qui est démontrée en annexe~\ref{anx:generateur}.
 
 
 \begin{restatable}[Une distance dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$]{theorem}{distancedsxnp}
@@ -722,12 +788,12 @@ $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ déjà détail
 
 Le graphe $\textsc{giu}_{\{1\}}(h)$ a déjà été donné à la figure~\ref{fig:h:iter}.
 Les graphes $\textsc{giu}_{\{2\}}(h)$, $\textsc{giu}_{\{3\}}(h)$  et
-$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnés aux figure~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}. 
+$\textsc{giu}_{\{2,3\}}(h)$ sont respectivement donnés aux figures~\ref{fig:h2prng}, ~\ref{fig:h3prng} et ~\ref{fig:h23prng}. 
 Le premier (respectivement le second) 
 illustre le comportement du générateur lorsque qu'on itère exactement 
 2 fois (resp. 3 fois) puis qu'on affiche le résultat.
 Le dernier donnerait le comportement d'un générateur qui s'autoriserait 
-à itérer en interne systématiquement 2 ou trois fois avant de retourner un résultat.
+à itérer en interne systématiquement 2 ou 3 fois avant de retourner un résultat.
 
 \end{xpl}
 
@@ -735,12 +801,12 @@ Le dernier donnerait le comportement d'un générateur qui s'autoriserait
 \subsection{le PRNG de l'algorithme~\ref{CI Algorithm} est chaotique sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}
 
 Le théorème suivant, similaire à ceux dans $\mathcal{X}_u$ et dans $\mathcal{X}_g$
-est prouvé en annexes~\ref{anx:generateur}.
+est prouvé en annexe~\ref{anx:generateur}.
 
-\begin{restatable}[Conditions pour la choticité de $G_{f_u,\mathcal{P}}$]{theorem}{thmchoticitgfp}
+\begin{restatable}[Conditions pour la chaoticité de $G_{f_u,\mathcal{P}}$]{theorem}{thmchoticitgfp}
 La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 
  $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si 
-le graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ 
+le graphe d'itérations $\textsc{giu}_{\mathcal{P}}(f)$ 
 est fortement connexe.
 \end{restatable}
 % On alors corollaire suivant 
@@ -758,6 +824,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