X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/8defa47ac283c6ce000d76eba1c1ad62b4a8bd38..refs/heads/master:/15RairoGen.tex?ds=sidebyside diff --git a/15RairoGen.tex b/15RairoGen.tex index f2b9243..6832d33 100644 --- a/15RairoGen.tex +++ b/15RairoGen.tex @@ -5,106 +5,172 @@ a de \og bonnes\fg{} propriétés chaotiques, le mot $x^b$ devrait \og sembler ne plus dépendre\fg{} de $x^0$. On peut penser à exploiter une de ces fonctions $G_f$ comme un générateur aléatoire. -Enfin, un bon générateur aléatoire se doit de -fournir des nombres selon une {distributionuniforme} -La suite de ce document donnera, -dans le cas où le graphe d'itérations est fortement connexe, -une condition nécessaire est suffisante pour que -cette propriété soit satisfaite. - - -Cette section présente une application directe de la théorie développée ci-avant -à la génération de nombres pseudo aléatoires. -On présente tout d'abord le générateur -basé sur des fonctions chaotiques (section~\ref{sub:prng:algo}), -puis comment intégrer la contrainte de distributionuniforme -de la sortie -dans le choix de la fonction à itérer (section~\ref{sub:prng:unif}). -L'approche est évaluée dans la dernière section. -\JFC{plan à revoir} + +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 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 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 é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,570.$$ -On énonce enfin le théorème suivant liant les -vecteurDeProbabilite -et les chaineDeMarkov: +On énonce le théorème classique suivant liant les +vecteurs de probabilités +et les chaînes de Markov. -\begin{Theo}\label{th} + +\begin{theorem}\label{th} Si $M$ est une matrice stochastique régulière, alors $M$ possède un unique vecteur stationnaire de probabilités $\pi$ ($\pi.M = \pi$). - De plus, si $\pi^0$ est un {vecteurDeProbabilite} + De plus, si $\pi^0$ est un {vecteur de probabilités} et si on définit la suite $(\pi^{k})^{k \in \Nats}$ par $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$ - alors la {chaineDeMarkov} $\pi^k$ + alors la {chaîne de Markov} $\pi^k$ converge vers $\pi$ lorsque $k$ tend vers l'infini. -\end{Theo} +\end{theorem} 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} vérifient les hypothèses du théorème~\ref{th:Adrien}. Leurs graphes d'itérations -sont donc fortement connexes, ce que l'on a pu déjà vérifier aux figures -\ref{fig:g:iter} et \ref{fig:h:iter}. +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$. + + + + + + + +\begin{figure}%[t] + \begin{center} + \subfigure[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[height=4cm]{images/g.pdf} + \end{center} + \end{minipage} + \label{fig:g:iter} + } + \subfigure[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[height=4cm]{images/h.pdf} + \end{center} + \end{minipage} + \label{fig:h:iter} + } \end{center} + \caption{Graphes des itérations unaires + de fonctions booléennes dans $\Bool^2$} + \label{fig:xplgraphIter} + \end{figure} + + + + + + + + + +\begin{figure}%[t] + \begin{center} + \subfigure[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[height=3cm]{images/gp.pdf} + \end{center} + \end{minipage} + \label{fig:g:inter} + } + \subfigure[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[height=3cm]{images/hp.pdf} + \end{center} + \end{minipage} + \label{fig:h:inter} + } \end{center} + \caption{Graphes d'interactions de fonctions booléennes dans $\Bool^2$} + \label{fig:xplgraphInter} + \end{figure} + + + + + + Comme le générateur \textit{Random} possède une sortie uniformément distribuée, la stratégie est uniforme sur $\llbracket 1, 2 \rrbracket$, et donc, -pour tout sommet de $\Gamma(g)$ et de $\Gamma(h)$, +pour tout sommet de $\textsc{giu}(g)$ et de $\textsc{giu}(h)$, chaque arc sortant de ce sommet a, parmi l'ensemble des arcs sortant de ce sommet, une probabilité $1/2$ d’être celui qui sera traversé. -En d'autres mots, $\Gamma(g)$ est le graphe orienté d'une chaîne de Markov. -Il est facile de vérifier que la {matriceDeTransitions} +En d'autres mots, $\textsc{giu}(g)$ est le graphe orienté d'une chaîne de Markov. +Il est facile de vérifier que la matrice de transitions d'un tel processus est $M_g = \frac{1}{2} \check{M}_g$, -où $\check{M}_g$ est la {matriceDAdjacence} donnée en -figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$. +où $\check{M}_g$ est la matrice d' adjacence donnée en +figure~\ref{fig:g:incidence} (voir ci-après), et de manière similaire pour $M_h$. \begin{figure}[h] \begin{center} - \subfloat[$\check{M}_g $.]{ + \subfigure[$\check{M}_g $.]{ \begin{minipage}{0.25\textwidth} \begin{center} % \vspace{-3cm} @@ -184,7 +316,7 @@ figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$. \end{minipage} \label{fig:g:incidence} } - \subfloat[$\check{M}_h $.]{ + \subfigure[$\check{M}_h $.]{ \begin{minipage}{0.25\textwidth} \begin{center} $\left( @@ -217,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 @@ -228,73 +360,30 @@ 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 annexe~\ref{anx:generateur}. -Considérons le lemme technique suivant: -\begin{Lemma}\label{lem:stoc} -Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\Gamma(f)$, et $M$ la matrice -$2^n\times 2^n$ définie par -$M = \frac{1}{n}\check{M}$. -Alors $M$ est une matrice stochastique régulière si et seulement si -$\Gamma(f)$ est fortement connexe. -\end{Lemma} - -\begin{Proof} -On remarque tout d'abord que $M$ -est une matrice stochastique par construction. -Supposons $M$ régulière. -Il existe donc $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket -1; 2^n \rrbracket$. L'inégalité $\check{M}_{ij}^k>0$ est alors établie. -Puisque $\check{M}_{ij}^k$ est le nombre de chemins de $i$ à $j$ de longueur $k$ -dans $\Gamma(f)$ et puisque ce nombre est positif, alors -$\Gamma(f)$ est fortement connexe. - -Réciproquement si $\Gamma(f)$ -est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut être construit pour atteindre $j$ depuis $i$ en au plus $2^n$ étapes. -Il existe donc -$k_{ij} \in \llbracket 1, 2^n \rrbracket$ tels que $\check{M}_{ij}^{k_{ij}}>0$. -Comme tous les multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que -$\check{M}_{ij}^{l\times k_{ij}}>0$, -on peut conclure que, si -$k$ est le plus petit multiple commun de $\{k_{ij} \big/ i,j \in \llbracket 1, 2^n \rrbracket \}$ alors -$\forall i,j \in \llbracket 1, 2^n \rrbracket, \check{M}_{ij}^{k}>0$. -Ainsi, $\check{M}$ et donc $M$ sont régulières. -\end{Proof} - -Ces résultats permettent formuler et de prouver le théorème suivant: - -\begin{Theo} - Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son +\begin{restatable}[Uniformité de la sortie de l'algorithme~\ref{CI Algorithm}]{theorem}{PrngCIUniforme}\label{thm:prng:u} + 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 comme dans le lemme précédent. - Si $\Gamma(f)$ est fortement connexe, alors - la sortie du générateur de nombres pseudo aléatoires détaillé par + et $M$ une matrice $2^n\times 2^n$ + définie par + $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 l'algorithme~\ref{CI Algorithm} suit une loi qui tend vers la distribution uniforme si et seulement si $M$ est une matrice doublement stochastique. -\end{Theo} -\begin{Proof} - $M$ est une matrice stochastique régulière (Lemme~\ref{lem:stoc}) - qui a un unique vecteur de probabilités stationnaire - (Théorème \ref{th}). - Soit $\pi$ défini par - $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$. - On a $\pi M = \pi$ si et seulement si - la somme des valeurs de chaque colonne de $M$ est 1, - \textit{i.e.} si et seulement si - $M$ est doublement stochastique. -\end{Proof} - - -\subsection{Expérimentations} - -On considère le graphe d'interactions $G(f)$ donné en figure~\ref{fig:G}. -Il vérifie le théorème~\ref{th:Adrien}: -toutes les fonctions $f$ possédant un tel graphe d'interactions -ont un graphe d'itérations $\Gamma(f)$ fortement connexe. -Pratiquement, un algorithme simple de satisfaction de contraintes -a trouvé 520 fonctions $f$ non isomorphes de graphe d'interactions $G(f)$, -dont seulement 16 d'entre elles possédent une matrice doublement stochastique. +\end{restatable} + +\subsection{Quelques exemples} + +On considère le graphe d'interactions $\Gamma(f)$ donné +en figure~\ref{fig:G}. C'est le même qui a été présenté +à la section~\ref{sec:11FCT}. +On a vu qu'il y avait 520 fonctions $f$ non isomorphes de graphe d'interactions $\Gamma(f)$. + +Seulement 16 d'entre elles possèdent une matrice doublement stochastique. La figure~\ref{fig:listfonction} explicite ces 16 fonctions en définissant les images des éléments de la liste 0, 1, 2,\ldots, 14, 15 en respectant l'ordre. @@ -302,31 +391,37 @@ 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é à $\Gamma(f)$ en partant de la configuration $i$. +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 -$$ -b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} -\{ -\min \{ + $b$. +Ainsi, on a +\begin{equation} +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} -\} -\}. -$$ +\right\} +\right\}. +\label{eq:mt:ex} +\end{equation} + +\noindent Par la suite, ce nombre sera appelé \emph{temps de mélange}. + + \begin{figure}%[h] \begin{center} - \subfloat[Graphe d'interactions]{ + \subfigure[Graphe d'interactions]{ \begin{minipage}{0.20\textwidth} \begin{center} \includegraphics[width=3.5cm]{images/Gi.pdf} @@ -334,7 +429,7 @@ $$ \end{minipage} \label{fig:G} }\hfill - \subfloat[Fonctions doublement stochastiques]{ + \subfigure[Fonctions doublement stochastiques]{ \begin{minipage}{0.75\textwidth} \begin{scriptsize} \begin{center} @@ -402,60 +497,341 @@ $\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). -% Pour les 15 tests, le seuil $\alpha$ est fixé à $1\%$: -% une valeur -% qui est plus grande que $1\%$ signifie -% que la chaîne est considérée comme aléatoire avec une confiance de $99\%$. -% Le tableau~\ref{fig:TEST} donne une vision synthétique de toutes -% les expérimentations. L'expérience a montré notamment que toutes ces fonctions passent avec succès cette batterie de tests. +Pour conclure cette section, on remarque que le générateur de nombres pseudo-aléatoires +a été prouvé chaotique pour $b=1$, \textit{i.e.}, lorsqu'il y a une sortie pour chaque itération. +Ceci est difficilement compatible avec la volonté d'avoir une sortie uniformément distribuée: +se rapprocher de cette distribution nécessite en effet un nombre plus élevé +d'itérations $b$ entre chaque sortie. Par exemple, dans l'exemple précédent, il est nécessaire +d'itérer au moins 42 fois entre chaque sortie pour suivre une loi uniforme à $10^{-4}$ près. +Montrer que les sous-séquences de suites chaotiques ainsi générées demeurent chaotiques +est l'objectif de la section suivante. + + +\section{Un PRNG basé sur des itérations unaires qui est chaotique }\label{prng:unaire:chaos} + +Cette section présente un espace métrique adapté au générateur de nombres pseudo-aléatoires +présenté à l'algorithme~\ref{CI Algorithm} et prouve ensuite que la fonction qu'il représente +est chaotique sur cet espace. +\subsection{Un espace $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ pour le PRNG de l'algorithme~\ref{CI Algorithm}} -% \begin{table}[th] -% \begin{scriptsize} -% \begin{tabular}{|*{17}{c|}} -% \hline -% {Propriété}& $\mathcal{F}_{1}$ &$\mathcal{F}_{2}$ &$\mathcal{F}_{3}$ &$\mathcal{F}_{4}$ &$\mathcal{F}_{5}$ &$\mathcal{F}_{6}$ &$\mathcal{F}_{7}$ &$\mathcal{F}_{8}$ &$\mathcal{F}_{9}$ &$\mathcal{F}_{10}$ &$\mathcal{F}_{11}$ &$\mathcal{F}_{12}$ &$\mathcal{F}_{13}$ &$\mathcal{F}_{14}$ &$\mathcal{F}_{15}$ &$\mathcal{F}_{16}$ \\ -% \hline -% Fréquence &77.9 &15.4 &83.4 &59.6 &16.3 &38.4 &20.2 &29.0 &77.9 &21.3 &65.8 &85.1 &51.4 &35.0 &77.9 &92.4 \\ -% \hline -% Fréquence / bloc &88.3 &36.7 &43.7 &81.7 &79.8 &5.9 &19.2 &2.7 &98.8 &1.0 &21.3 &63.7 &1.4 &7.6 &99.1 &33.5 \\ -% \hline -% Somme cummulée &76.4 &86.6 &8.7 &66.7 &2.2 &52.6 &20.8 &80.4 &9.8 &54.0 &73.6 &80.1 &60.7 &79.7 &76.0 &44.7 \\ -% \hline -% Exécution &5.2 &41.9 &59.6 &89.8 &23.7 &76.0 &77.9 &79.8 &45.6 &59.6 &89.8 &2.4 &96.4 &10.9 &72.0 &11.5 \\ -% \hline -% Longue exécution &21.3 &93.6 &69.9 &23.7 &33.5 &30.4 &41.9 &43.7 &30.4 &17.2 &41.9 &51.4 &59.6 &65.8 &11.5 &61.6 \\ -% \hline -% Rang &1.0 &41.9 &35.0 &45.6 &51.4 &20.2 &31.9 &83.4 &89.8 &38.4 &61.6 &4.0 &21.3 &69.9 &47.5 &95.6 \\ -% \hline -% Fourrier Rapide &40.1 &92.4 &97.8 &86.8 &43.7 &38.4 &76.0 &57.5 &36.7 &35.0 &55.4 &57.5 &86.8 &76.0 &31.9 &7.6 \\ -% \hline -% Sans superposition &49.0 &45.7 &50.5 &51.0 &48.8 &51.2 &51.6 &50.9 &50.9 &48.8 &45.5 &47.3 &47.0 &49.2 &48.6 &46.4 \\ -% \hline -% Avec Superposition &27.6 &10.9 &53.4 &61.6 &16.3 &2.7 &59.6 &94.6 &88.3 &55.4 &76.0 &23.7 &47.5 &91.1 &65.8 &81.7 \\ -% \hline -% Universelle &24.9 &35.0 &72.0 &51.4 &20.2 &74.0 &40.1 &23.7 &9.1 &72.0 &4.9 &13.7 &14.5 &1.8 &93.6 &65.8 \\ -% \hline -% Entropie approchée &33.5 &57.5 &65.8 &53.4 &26.2 &98.3 &53.4 &63.7 &38.4 &6.7 &53.4 &19.2 &20.2 &27.6 &67.9 &88.3 \\ -% \hline -% Suite aléatoire &29.8 &35.7 &40.9 &36.3 &54.8 &50.8 &43.5 &46.0 &39.1 &40.8 &29.6 &42.0 &34.8 &33.8 &63.0 &46.3 \\ -% \hline -% Suite aléatoire variante &32.2 &40.2 &23.0 &39.6 &47.5 &37.2 &56.9 &54.6 &53.3 &31.5 &23.0 &38.1 &52.3 &57.1 &47.7 &40.8 \\ -% \hline -% Série &56.9 &58.5 &70.4 &73.2 &31.3 &45.9 &60.8 &39.9 &57.7 &21.2 &6.4 &15.6 &44.7 &31.4 &71.7 &49.1 \\ -% \hline -% Complexité linéaire &24.9 &23.7 &96.4 &61.6 &83.4 &49.4 &49.4 &18.2 &3.5 &76.0 &24.9 &97.2 &38.4 &38.4 &1.1 &8.6 \\ -% \hline -% \end{tabular} -% \end{scriptsize} -% \caption{Test de NIST réalisé sur des instances de générateurs}\label{fig:TEST} -% \end{table} +Introduisons tout d'abord $\mathcal{P} \subset \mathds{N}$ un ensemble fini non vide de cardinalité +$\mathsf{p} \in \mathds{N}^\ast$. +Intuitivement, c'est le nombre d'itérations qu'il est autorisé de faire. +On ordonne les $\mathsf{p}$ éléments de $\mathcal{P}$ comme suit: +$\mathcal{P} = \{ p_1, p_2, \hdots, p_\mathsf{p}\}$ +et $p_1< p_2< \hdots < p_\mathsf{p}$. +Dans l'algorithme~\ref{CI Algorithm}, +$\mathsf{p}$ vaut 1 et $p_1=b$. +Cet algorithme peut être vu comme $b$ compostions de la fonction $F_{f_u}$. +Ceci peut cependant se généraliser à $p_i$, $p_i \in \mathcal{P}$, +compositions fonctionnelles de $F_{f_u}$. +Ainsi, pour chaque $p_i \in \mathcal{P}$, on construit la fonction +$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})) = +F_{f_u}(\hdots (F_{f_u}(F_{f_u}(x,u^0), u^1), \hdots), u^{p_i-1}). +$$ + + +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 +\mathcal{P}^{\Nats}$. +Chaque élément de l'espace est une paire où le premier élément est +un $\mathsf{N}$-uplet de $\Bool^{\mathsf{N}}$ (comme dans $\mathcal{X}_u$). +Le second élément est une paire $((u^k)_{k \in \Nats},(v^k)_{k \in \Nats})$ de suites infinies. +La suite $(v^k)_{k \in \Nats}$ définit combien d'itérations sont exécutées au temps $k$ entre deux sorties. +La séquence $(u^k)_{k \in \Nats}$ définit quel élément est modifié (toujours au temps $k$). + +Définissons la fonction de décalage $\Sigma$ pour chaque élément de $\mathds{S}_{\mathsf{N},\mathcal{P}}$. +$$\begin{array}{cccc} +\Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow +&\mathds{S}_{\mathsf{N},\mathcal{P}} \\ +& \left((u^k)_{k \in \mathds{N}},(v^k)_{k \in \mathds{N}}\right) & \longmapsto & \left(\sigma^{v^0}\left((u^k)_{k \in \mathds{N}}\right),\sigma\left((v^k)_{k \in \mathds{N}}\right)\right). +\end{array} +$$ +En d'autres termes, $\Sigma$ reçoit deux suites $u$ et $v$ et +effectue $v^0$ décalage vers la droite sur la première et un décalage vers la droite +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^{\mathsf{N}})$ dans $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ où +$G_{f_u,\mathcal{P}}$ est définie par: + + + + +\begin{equation} +\begin{array}{cccc} +G_{f_u,\mathcal{P}} :& \mathcal{X}_{\mathsf{N},\mathcal{P}} & \longrightarrow & \mathcal{X}_{\mathsf{N},\mathcal{P}}\\ + & (e,(u,v)) & \longmapsto & \left( F_{f,v^0}\left( e, (u^0, \hdots, u^{v^0-1}\right), \Sigma (u,v) \right) . +\end{array} +\end{equation} + + + +\subsection{Une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$} + +On définit la fonction $d$ sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ comme suit: +Soit $x=(e,s)$ et $\check{x}=(\check{e},\check{s})$ dans +$\mathcal{X}_{\mathsf{N},\mathcal{P}} = \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}} $, +où $s=(u,v)$ et $\check{s}=(\check{u},\check{v})$ sont dans $ \mathds{S}_{\mathsf{N},\mathcal{P}} = +\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}}$ 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})$. +\item la partie décimale est construite à partir des différences entre +$v^0$ et $\check{v}^0$, suivie des différences entre les séquences finies +$u^0, u^1, \hdots, u^{v^0-1}$ et $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$, suivie par les différences entre $v^1$ et $\check{v}^1$, +suivie par les différences entre $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ et +$\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc. + +Plus précisément, soit +$p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ et +$n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$. +\begin{enumerate} +\item Les $p$ premiers éléments de $d(x,\check{x})$ sont $|v^0-\check{v}^0|$ + écrits en base 10 et sur $p$ indices; +\item les $n\times \max{(\mathcal{P})}$ éléments suivants servent + à évaluer de combien $u^0, u^1, \hdots, u^{v^0-1}$ diffère de + $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. + Les $n$ premiers éléments sont $|u^0-\check{u}^0|$. Il sont suivis de +$|u^1-\check{u}^1|$ écrits à l'aide de $n$ éléments, etc. +\begin{enumerate} +\item Si +$v^0=\check{v}^0$, +alors le processus se continue jusqu'à $|u^{v^0-1}-\check{u}^{\check{v}^0-1}|$ et la +partie décimale de $d(X,\check{X})$ est complétée par des 0 +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), 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. +\end{enumerate} +\end{enumerate} + + +La fonction $d$ peut se formaliser comme suit: +$$d(x,\check{x})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})+d_{\mathds{B}^\mathsf{N}}(e,\check{e}),$$ +où: % $p=\max \mathcal{P}$ and: +\begin{itemize} +\item $d_{\mathds{B}^\mathsf{N}}$ est la distance de Hamming, +\item $\forall s=(u,v), \check{s}=(\check{u},\check{v}) \in \mathcal{S}_{\mathsf{N},\mathcal{P}}$,\newline +$$\begin{array}{rcl} + d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) &= & + \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} + \bigg(|v^k - \check{v}^k| \\ + & & + \left| \sum_{l=0}^{v^k-1} + \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{(l+1)n}} - + \sum_{l=0}^{\check{v}^k-1} + \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{(l+1)n}} \right| \bigg) +\end{array} +$$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.$$ +\end{itemize} + + + +\begin{xpl} +On considère par exemple +$\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ ($\mathsf{p}$ vaut ainsi $3$), +et +$s=\left\{ +\begin{array}{l} +u=\underline{6,} ~ \underline{11,5}, ...\\ +v=1,2,... +\end{array} +\right.$ +avec +$\check{s}=\left\{ +\begin{array}{l} +\check{u}=\underline{6,4} ~ \underline{1}, ...\\ +\check{v}=2,1,... +\end{array} +\right.$. +Ainsi +\[ +d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = +0.01~0004000000000000000000~01~1005 \dots\] +En effet, les $p=2$ premiers éléments sont 01, c'est-à-dire +$|v^0-\check{v}^0|=1$, +et on utilise $p$ éléments pour représenter cette différence +(Comme $\mathcal{P}=\{1,2,11\}$, cette différence peut valoir 10). +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 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 +0604000000000000000000. +La valeur absolue de leur différence est égale à +0004000000000000000000. +Ces éléments sont concaténés avec 01. On peut construire alors le reste de +la séquence. +\end{xpl} + + +% \begin{xpl} +% On considère à présent que $\mathsf{N}=9$, que $\mathcal{P}=\{2,7\}$ et que +% $$s=\left\{ +% \begin{array}{l} +% u=\underline{6,7,} ~ \underline{4,2,} ...\\ +% v=2,2,... +% \end{array} +% \right.$$ +% avec +% $$\check{s}=\left\{ +% \begin{array}{l} +% \check{u}=\underline{4, 9, 6, 3, 6, 6, 7,} ~ \underline{9, 8}, ...\\ +% \check{v}=7,2,... +% \end{array} +% \right. +% $$ + +% Ainsi $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, +% puisque +% $|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$, +% et $|9800000-4200000| = 5600000$. +% \end{xpl} + + + +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} +$d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$. +\end{restatable} + + +\subsection{Le graphe $\textsc{giu}_{\mathcal{P}}(f)$ étendant $\textsc{giu}(f)$} + +A partir de $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$, on +définit le graphe orienté $\textsc{giu}_{\mathcal{P}}(f)$ de la manière suivante: +\begin{itemize} +\item les n{\oe}uds sont les $2^\mathsf{N}$ configurations de $\mathds{B}^\mathsf{N}$, +%\item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples +% having their elements in $\llbracket 1, \mathsf{N} \rrbracket $. +\item il y a un arc libellé $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ entre les n{\oe}uds $x$ et $y$ si et seulement si $p_i$ est un élément de +$\mathcal{P}$ (\textit{i.e.}, on peut itérer $p_i$ fois), et pour chaque +$k$, $0 \le k \le p_i-1$, on a + $u_k$ qui appartient à $[\mathsf{N}]$ et +$y=F_{f_u,p_i} (x, (u_0, \hdots, u_{p_i-1})) $. +\end{itemize} +Il n'est pas difficile de constater que $\textsc{giu}_{\{1\}}(f)$ est $\textsc{giu}(f)$. + + + + + +\begin{figure}%[t] + \begin{center} + \subfigure[$\textsc{giu}_{\{2\}}(h)$]{ + \begin{minipage}{0.30\textwidth} + \begin{center} + \includegraphics[scale=0.5]{images/h2prng} + \end{center} + \end{minipage} + \label{fig:h2prng} + } + \subfigure[$\textsc{giu}_{\{3\}}(h)$]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[scale=0.5]{images/h3prng} + \end{center} + \end{minipage} + \label{fig:h3prng} + } + \subfigure[$\textsc{giu}_{\{2,3\}}(h)$]{ + \begin{minipage}{0.40\textwidth} + \begin{center} + \includegraphics[scale=0.5]{images/h23prng} + \end{center} + \end{minipage} + \label{fig:h23prng} + } + + \end{center} + \caption{Graphes d'itérations $\textsc{giu}_{\mathcal{P}}(h)$ pour $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$} + %\label{fig:xplgraphIter} + \end{figure} + + + + +\begin{xpl} +On reprend l'exemple où $\mathsf{N}=2$ et +$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$ déjà détaillé +à la section~\ref{sub:prng:unif}. + +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 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 3 fois avant de retourner un résultat. + +\end{xpl} + + +\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 annexe~\ref{anx:generateur}. + +\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érations $\textsc{giu}_{\mathcal{P}}(f)$ +est fortement connexe. +\end{restatable} +% On alors corollaire suivant + +% \begin{corollary} +% Le générateur de nombre pseudo aléatoire détaillé +% à l'algorithme~\ref{CI Algorithm} +% n'est pas chaotique +% sur $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ pour la fonction négation. +% \end{corollary} +% \begin{proof} +% Dans cet algorithme, $\mathcal{P}$ est le singleton $\{b\}$. +% Que $b$ soit pair ou impair, $\textsc{giu}_{\{b\}}(f)$ +% n'est pas 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 +et suffisant que la fonction $f$ qui est itérée un nombre $b$ de fois +possède un $\textsc{giu}_{\{b\}}(f)$ fortement connexe et que sa matrice de Markov associée soit doublement stochastique. +Le chapitre suivant montre comment construire une telle fonction. + + +