La génération algorithmique de nombres aléatoires
Author
Louis
Last Updated
4 years ago
License
Creative Commons CC BY 4.0
Abstract
TIPE 2016–2017
La génération algorithmique de nombres aléatoires : Utilisation à des fins de simulation
TIPE 2016–2017
La génération algorithmique de nombres aléatoires : Utilisation à des fins de simulation
\documentclass[10pt]{beamer}
\usetheme[
%%% option passed to the outer theme
% progressstyle=fixedCircCnt, % fixedCircCnt, movingCircCnt (moving is deault)
]{Feather}
% If you want to change the colors of the various elements in the theme, edit and uncomment the following lines
% Change the bar colors:
%\setbeamercolor{Feather}{fg=red!20,bg=red}
% Change the color of the structural elements:
%\setbeamercolor{structure}{fg=red}
% Change the frame title text color:
%\setbeamercolor{frametitle}{fg=blue}
% Change the normal text color background:
%\setbeamercolor{normal text}{fg=black,bg=gray!10}
%-------------------------------------------------------
% INCLUDE PACKAGES
%-------------------------------------------------------
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage[T1]{fontenc}
\usepackage{helvet}
\usepackage{minted}
%-------------------------------------------------------
% DEFFINING AND REDEFINING COMMANDS
%-------------------------------------------------------
% colored hyperlinks
\newcommand{\chref}[2]{
\href{#1}{{\usebeamercolor[bg]{Feather}#2}}
}
\definecolor{vert}{RGB}{22,150,50}
\definecolor{vert2}{RGB}{170,230,130}
\definecolor{bleu}{RGB}{50,100,255}
\definecolor{bleu2}{RGB}{180,200,240}
\definecolor{orange}{RGB}{200,100,0}
\definecolor{orange2}{RGB}{240,190,70}
\definecolor{rouge}{RGB}{180,10,0}
\definecolor{rouge2}{RGB}{250,200,190}
\beamerboxesdeclarecolorscheme{objectif}{vert}{vert2}
\beamerboxesdeclarecolorscheme{idee}{bleu}{bleu2}
\beamerboxesdeclarecolorscheme{explication}{orange}{orange2}
\beamerboxesdeclarecolorscheme{propriete}{rouge}{rouge2}
%-------------------------------------------------------
% INFORMATION IN THE TITLE PAGE
%-------------------------------------------------------
\title[] % [] is optional - is placed on the bottom of the sidebar on every slide
{ % is placed on the title page
\textbf{La génération algorithmique de nombres aléatoires}}
\subtitle[]
{
\textbf{Utilisation à des fins de simulation
}
}
\author[]
{Louis Guichard}
\institute[]
{
\textbf{TIPE 2016-2017}
}
\date{}
%-------------------------------------------------------
% THE BODY OF THE PRESENTATION
%-------------------------------------------------------
\begin{document}
%-------------------------------------------------------
% THE TITLEPAGE
%-------------------------------------------------------
{\1% % this is the name of the PDF file for the background
\begin{frame}[plain,noframenumbering] % the plain option removes the header from the title page, noframenumbering removes the numbering of this frame only
\titlepage % call the title page information from above
\end{frame}}
%----------- INTRO ------------
\section{Introduction}
\begin{frame}{Introduction}
\textbf{\underline{Thème du TIPE:}} Optimalité : choix, contraintes, hasard.
\medskip
\textbf{Pourquoi générer des nombres aléatoires?}
\begin{itemize}
\item \textit{Hasard} est synonyme d'\textit{imprévisible}
\item Deux principales utilités :
\begin{itemize}
\item Simuler des phénomènes imprévisibles
\item Protéger nos informations (cryptographie)
\end{itemize}
\end{itemize}
\bigskip
\textbf{Comment s'y prendre ?}
\begin{itemize}
\item Générateurs physiques
\begin{itemize}
\item Lent et difficile à mettre en place
\end{itemize}
\item Générateurs algorithmiques
\begin{itemize}
\item Procédé déterministe $\Rightarrow$ paradoxe
\end{itemize}
\end{itemize}
\medskip
\textbf{\underline{Problématique:}} Comment un algorithme peut-il générer une suite de nombres qu’on pourrait qualifier
d’aléatoire?
\end{frame}
%------ TABLE DES MATIERES ------------
\begin{frame}{Table des matières}{}
\tableofcontents
\end{frame}
%-----------------------------------
%---------- PREMIERE PARTIE --------
%-----------------------------------
\section{I - Validité des algorithmes}
%-------- 1) DEFINIR LE HASARD ----------------
\subsection{Définir le hasard}
\begin{frame}{Définir le hasard}
3 idées équivalentes :
\medskip
\begin{itemize}
\item \textbf{Martin-Löf} : une suite est aléatoire si elle ne possède aucune propriété exceptionnelle (1966).
\item \textbf{Schnorr} : une suite aléatoire est imprévisible (1971).
\item \textbf{Levin} et \textbf{Chaintin} : une suite aléatoire est incompressible (1974).
\end{itemize}
\bigskip
\textbf{Paradoxe de Borel} (antérieur aux définitions ci-dessus) : \\
Si on considère une suite aléatoire comme étant une suite n'ayant aucune propriété particulière, alors cela donne une caractéristique aux suites répondant à cette définition.
\bigskip
Si elles sont utilisées dans le domaine de la \textbf{simulation}, on retiendra qu'une suite aléatoire ne doit présenter \textbf{aucune propriété exceptionnelle}.
\end{frame}
%--------- 2) QUELQUES IDEES -------
\subsection{Quelques idées...}
%----------- 1ere idée ---------------
\begin{frame}{Quelques idées... }
\begin{beamerboxesrounded}[scheme=objectif,shadow=true]{Objectif} Confondre les suites générées avec des suites \textit{vraiment} aléatoires.
\end{beamerboxesrounded}
\medskip
\begin{beamerboxesrounded}[scheme=idee,shadow=true]{Première idée : Fréquence d'apparition des 0 et 1}
Soit $X$ une variable aléatoire définie par le nombre de zéros dans une série binaire de longueur $n$. \\
$X$ suit une loi binomiale de paramètre \(n\) et \(p = \frac{1}{2}\). \\
Si $n = 20$, on a donc \(P(6\leq X\leq 14) \simeq 0,96\).
\end{beamerboxesrounded}
\medskip
\begin{beamerboxesrounded}[scheme=objectif,shadow=true]{Distance d'une loi de probabilité à une autre}Considérons un $n$-échantillon sur $\left \{ 1, ..., k \right \}$. \\
Soit $p = (p_1, . . . , p_k)$ une loi de probabilité de référence sur cet ensemble et $q = (q_1, . . . , q_k)$ une autre loi de probabilité. \\
La distance euclidienne $\mathcal{D}$ de la loi de probabilité $p$ à la loi $q$ est définie par :
\(\mathcal{D}(p,q) = \sum_{i=1}^k |p_i - q_i|\)
\end{beamerboxesrounded}
\end{frame}
%------------ 2e idée ---------
\begin{frame}{Quelques idées...}
\textcolor{red}{\(u_{20} = (0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1)\)}
\medskip
\begin{beamerboxesrounded}[scheme=idee,shadow=true]{Deuxième idée : Fréquence des paires de 0}
Intuitivement, il semble peu probable de n'obtenir aucune paire de 0 consécutifs sur une série binaire de longueur 20. \\
On peut démontrer que la probabilité de n'obtenir aucune paire de 0 consécutifs dans une telle suite est inférieure à 2\%
\end{beamerboxesrounded}
\medskip
\begin{beamerboxesrounded}[scheme=objectif,shadow=true]{Distance entre deux 0 consécutifs}
Soit $X_i$ la variable aléatoire représentant la valeur du $i^{e}$ élément d'une liste pour $i \in [|1,n|]$. On introduit la variable aléatoire $D_i$ qui représente la distance entre le $i^{e}$ zéro de la liste et le $i+1^e$. Si les $X_i$ suivent une loi uniforme sur $\{0,1\}$, alors on a
\[\forall i \in [|1,p|] \text{, }P(D_i = 0) = \frac{1}{2} \text{ et } P(D_i = k) = \frac{1}{2^{k+1}}\]
\end{beamerboxesrounded}
\end{frame}
%----------- 3) KHI CARRE ---------
\subsection{Test du Khi-Carré}
\begin{frame}{Test du Khi-Carré}
\begin{beamerboxesrounded}[scheme=explication,shadow=true]{Problème}
En l'état, les deux tests précédents ne permettent que de comparer les résultats d'un algorithme à un autre. On ne peut pas dire qu'un algorithme est "bon", mais seulement qu'il est "meilleur qu'un autre".
\end{beamerboxesrounded}
\medskip
\begin{beamerboxesrounded}[scheme=objectif,shadow=true]{Intérêt du test} Le test du Khi-Carré est un test d'adéquation, qui permet de vérifier si une série de données suit une certaine loi de probabilité.
\end{beamerboxesrounded}
\medskip
\begin{beamerboxesrounded}[scheme=idee,shadow=true]{Principe du test}
Avec les mêmes notations que précédemment, on définit la distance
du $\chi^2$ par \[\chi^{2}_{n} (p,q) = {\sum_{i=1}^{k} \frac{(np_i - nq_i)^2}{np_i}} \]
\end{beamerboxesrounded}
\end{frame}
\begin{frame}{Test du Khi-Carré}
\begin{beamerboxesrounded}[scheme=explication,shadow=true]{Procédé}
\begin{itemize}
\item Choisir un risque $\alpha$ de rejeter à tort l'hypothèse $H_0$ : "l'échantillon suit la loi $p$".
\item A partir de la table du Khi-Carré, on détermine la borne $b_{\alpha}$ au-delà de laquelle le risque de rejeter à tort l'hypothèse $H_0$ est inférieur à celui choisi.
\item On rejette l'hypothèse $H_0$ si la valeur de \(\chi^{2}(p_{empirique},p_{théorique})\) est supérieure à la borne $b_{\alpha}$.
\end{itemize}
\end{beamerboxesrounded}
\includegraphics[width=\textwidth]{table.PNG}
\end{frame}
%--------- UTILISATION DU TEST
\begin{frame}{Utilisation du test du $\chi^2$}
\begin{beamerboxesrounded}[scheme=idee,shadow=true]{Idée 1 : Distance à la loi uniforme}
Le test du $\chi^2$ est un test d'adéquation. Il suffit donc de l'appliquer en calculant \(\chi^{2}(p,q) = \sum_{i=0}^k \frac{(np_i - nq_i)^2}{nq_i}\) où $p_i$ est la loi empirique et $q_i$ la loi théorique (\textit{ie}. la loi uniforme) pour vérifier l'hypothèse $H_0$ : "la suite est aléatoire".
\end{beamerboxesrounded}
\bigskip
\begin{beamerboxesrounded}[scheme=idee,shadow=true]{Idée 2 : Indépendance des valeurs}
La variable aléatoire $D_i$ définie précédemment, et représentant la distance entre 2 zéros consécutifs dans la suite, suit la loi $\forall k \in \mathbb{N}$, $P(D_i=k) = \frac{1}{2^{k+1}}$. On va une nouvelle fois calculer la distance du $\chi^2$ entre la loi empirique et la loi théorique.
\end{beamerboxesrounded}
\end{frame}
%------- EN PYTHON ------------------
\begin{frame}{En Python}
\inputminted{python}{khicarre.py}
\end{frame}
%-------------------------------------------------------
\section{II - Algorithmes}
%-------------------------------------------------------
\subsection{Carré Médian de Von Neumann}
\begin{frame}{Carré Médian de Von Neumann}
\begin{beamerboxesrounded}[scheme=idee,shadow=true]{Principe}
Très simple : on prend un nombre, on l'élève au carré, et les digits centraux constituent la sortie. Et on recommence. Par exemple : $1234^2 = 1 522 756$ puis $2275^2 = 5 175 625$ puis $7562^2 = ...$.
\end{beamerboxesrounded}
\medskip
{\footnotesize \inputminted{python}{neumann.py}}
\end{frame}
\begin{frame}{Carré Médian de Von Neumann}
\begin{beamerboxesrounded}[scheme=explication,shadow=true]{Problème}
\begin{itemize}
\item Si le nombre "du milieu" est '0000', l'algorithme ne renvoie plus que des '0000' ('0000' est un état absorbant).
\item Dès qu'on retombe sur un nombre déjà utilisé, l'algorithme tourne en boucle
\end{itemize}
Cet algorithme n'est donc pas capable de produire de longues séries de nombres aléatoires : sa\textbf{ période} est limitée. \\
De plus, la période dépend du premier nombre utilisé, appelé \textbf{graine}. Certaines graines risquent de moins bien fonctionner que d'autres.
\end{beamerboxesrounded}
\bigskip
\includegraphics[width=\textwidth]{testgraine.PNG}
\end{frame}
\begin{frame}{Carré Médian de Von Neumann}
{\footnotesize \inputminted{python}{neumanngraine.py}}
\begin{beamerboxesrounded}[scheme=explication,shadow=true]{Résultat}
En exécutant neumanngraine(10000), on obtient que la période la plus longue est de 167, et qu'elle est très inégale selon la graine choisie.
\end{beamerboxesrounded}
\end{frame}
%------ 2) GENERATEUR CONGRUENTIEL -------
\subsection{Générateurs congruentiels linéaires}
\begin{frame}{Générateurs congruentiels linéaires}
\begin{beamerboxesrounded}[scheme=objectif,shadow=true]{Générateur congruentiel linéaire}
Un \textbf{générateur congruentiel linéaire} produit une séquence de nombres pseudo-aléatoires à partir de la relation de récurrence
\[u_{n+1} = a u_n + b \text{ }mod\text{ }M\]
où $a$ est appelé le \textit{multiplicateur}, $b$ l'\textit{incrément} et $M$ le \textit{module}.
\end{beamerboxesrounded}
\smallskip
{\footnotesize \inputminted{python}{lcg.py}}
\end{frame}
\begin{frame}{Générateurs congruentiels linéaires}
\textcolor{red}{Prenons $a = 10$, $b = 5$, $M = 100$ et $X_0 = 10$. \\
La séquence générée par l'algorithme est $[5, 55, 55, 55, 55, ...]$} \\
\smallskip
\textcolor{red}{Avec $a = 25$, $b = 16$, $M = 256$ et $X_0 = 50$, la séquence générée par l'algorithme est $[50, 242, 178, 114, 50, 242, ...]$}
\medskip
\begin{beamerboxesrounded}[scheme=explication,shadow=true]{Graine et autres paramètres}
$55$ est un état absorbant pour cet algorithme, comme $0000$ l'était pour celui de Von Neumann. L'avantage d'un générateur congruentiel linéaire est que l'on peut jouer sur les paramètres $a$, $b$ et $M$ afin d'obtenir des séquences de meilleures qualités.
\end{beamerboxesrounded}
\medskip
\begin{beamerboxesrounded}[scheme=propriete,shadow=true]{Choix du module}
Les ordinateurs calculant naturellement en base binaire, on utilisera systématiquement un module du type $M = 2^k$.
\end{beamerboxesrounded}
\end{frame}
\begin{frame}{Générateurs congruentiels linéaires}
{\footnotesize \inputminted{python}{periode.py}}
\end{frame}
\begin{frame}{Générateurs congruentiels linéaires}
\includegraphics[width=\textwidth]{periodemax.PNG}
\bigskip
\begin{beamerboxesrounded}[scheme=explication,shadow=true]{Résultats}
On peut conjecturer que \[\left\{\begin{matrix}
a \equiv 1 [4]\\
b \text{ est impair}
\end{matrix}\right.
\Leftrightarrow \lambda = 2^m\]
\end{beamerboxesrounded}
\end{frame}
\begin{frame}{Démonstration}
\begin{beamerboxesrounded}[scheme=propriete,shadow=true]{Théorème}
Soit un générateur congruentiel linéaire de période $\lambda$ suivant la relation $u_{n+1} = au_n + b$ mod $M$. Alors :
\[\left\{\begin{matrix}
a \equiv 1 [4]\\
b \text{ est impair} \\
M = 2^m
\end{matrix}\right.
\Rightarrow \lambda = M\]
\end{beamerboxesrounded}
\bigskip
\underline{Lemme}: \\
Si $p$ est premier, alors $\forall k \in \mathbb{N}$ :
\(\left\{\begin{matrix}
x \equiv 1 [p^k]\\
x \not \equiv 1 [p^{k+1}]
\end{matrix}\right.
\Rightarrow
\left\{\begin{matrix}
x^p \equiv 1 [p^{k+1}]\\
x^p \not \equiv 1 [p^{k+2}]
\end{matrix}\right.\) \\
\end{frame}
\begin{frame}{Preuve de la lemme}
\underline{Preuve de la lemme: }\\
On peut écrire $x = 1 + qp^k$ où $q$ est un entier premier avec $p$. Alors : \\
$x^p = (1 + qp^k)^p = \sum_{i=0}^{p} \binom{p}{i} q^i p^{ik} = 1 + \binom{p}{1}q p^k + ... + \binom{p}{p-1} q^{(p-1)k} + q^p p^{kp}$ \\
D'où $x^p = 1 + q p^{k+1} (1 + \frac{1}{p} \binom{p}{2} q p^k + \frac{1}{p} \binom{p}{3} q^2 p^{2k} + ... + \frac{1}{p} \binom{p}{p} q^{p-1} p^{(p-1)k})$. \\
La quantité entre les parenthèses est un entier, et chaque terme entre les parenthèses à l'exception du premier est un multiple de $p$. Aussi, $\forall n \in [|2,p-1|]$, $p$ divise $\binom{p}{n}$. Ainsi, $\frac{1}{p} \binom{p}{n} q^{n-1} p^{(n-1)k}$ est divisible par $p^{(n-1)k}$. \\
De plus, le dernier terme $q^{p-1} p^{(p-1)k-1}$ est divisible par $p$ puisque $(p-1)k \geq 2$. \\
Donc $x^p \equiv 1 + q p^{k+1} [p^{k+2}]$.
\end{frame}
\begin{frame}{Démonstration}
On suppose que $b$ est impair, que $a \equiv 1[4]$ et que $M = 2^m$. Notons $\lambda$ la période du générateur. Les paramètres $a,b,M$ sont positifs.\\
$a \equiv 1$ $[4] \Leftrightarrow \exists q \in \mathbb{N}$ / $a = 4q + 1$ \\
Ainsi, $\exists q'$ impair, $k \geq 2$ / $a = 2^k q' + 1$ ($q'=1$ si $q$ pair, $q'=q$ sinon) \\
donc $a \equiv 1$ $[2^k]$ et $a \not \equiv 1$ $[2^{k+1}]$ avec $k \geq 2$. \\
En utilisant la lemme, on obtient
$\left\{\begin{matrix}
a^2 \equiv 1 [2^{k+1}]\\
a^2 \not \equiv 1 [2^{k+2}]
\end{matrix}\right.$ \\
Par récurrence, on a $\forall k' \geq k$ :
$\left\{\begin{matrix}
a^{2^{k'}} \equiv 1 [2^{k+k'}]\\
a^{2^{k'}} \not \equiv 1 [2^{k+k'+1}]
\end{matrix}\right.$ \\
De plus, $\frac{a^{2^{k'}}-1}{a-1} = \frac{q 2^{k+k'}}{q' 2^k} = \frac{q}{q'} 2^{k'} \equiv 0 [2^{k'}]$. \\
En particulier, $m >k$ donc $\frac{a^{2^{m}}-1}{a-1} \equiv 0 [2^{m}]$.
\end{frame}
\begin{frame}{Démonstration}
Le générateur a pour formule de récurrence $x_{n+1} = ax_n + b$ mod $M$. \\
Par récurrence, il vient $x_{n+k} = a^k x_n + \frac{a^k -1}{a-1} b$ mod $M$. \\
La période est de $\lambda$, ce qui se traduit par \\
$\forall n > M$, $x_n \equiv x_{n+\lambda} \equiv a^{\lambda} x_n + \frac{a^{\lambda} -1}{a-1} b \equiv \frac{a^k -1}{a-1}(x_n(a-1)+b)$ $[M]$. \\
Or, $b$ est impair et $a-1$ est pair donc $x_n(a-1)+b$ est impair. \\
Ainsi, $M = 2^m$ divise $\frac{a^{\lambda}-1}{a-1}$ et donc $\frac{a^{\lambda} -1}{a-1} \equiv 0 [2^{m}]$ \\
D'où, $\frac{a^{2^{m}}-1}{a-1} \equiv \frac{a^{\lambda} -1}{a-1} [2^{m}]$ et $a^{2^m} \equiv a^{\lambda} [2^m]$ et $\lambda$ divise $2^m$. \\
Ainsi, $\exists j \leq m$ | $\lambda = 2^j$. Si $j < m$, $\frac{a^{2^j}-1}{a-1} \not \equiv 0 [2^{j+1}]$. \\
A fortiori, $\frac{a^{2^j}-1}{a-1} \not \equiv 0$ mod $2^m$ donc $\lambda \not = 2^j$. \\
Donc $\lambda = 2^m$.
\end{frame}
\begin{frame}{Générateurs congruentiels linéaires}
Prenons, $a = 3 \times 4 + 1 = 13$, $b = 17$ et $M = 2^{10} = 1024$.
La formule de récurrence est alors \textcolor{red}{$u_{n+1} = 13 u_n + 17 \text{ }mod\text{ }1024$}.
\medskip
La période du générateur congruentiel linéaire ainsi parametré est 1024, \textbf{quelque soit la graine}.
\medskip
\begin{beamerboxesrounded}[scheme=explication,shadow=true]{Tests statistiques}
Il est maintenant temps d'utiliser les deux tests élaborés en première partie.
\end{beamerboxesrounded}
\medskip
{\footnotesize \inputminted{python}{convbin.py}}
\end{frame}
\begin{frame}{Générateurs congruentiels linéaires}
\begin{center}
{\footnotesize \inputminted{python}{testlcg2.py}}
\medskip
{\footnotesize \includegraphics[scale=0.7]{testtout.PNG}}
\medskip
{\footnotesize \includegraphics[scale=0.7]{table2.PNG}}
\end{center}
\end{frame}
\begin{frame}{Générateurs congruentiels linéaires}
\begin{center}
{\footnotesize \inputminted{python}{distance.py}}
\medskip
{\footnotesize \includegraphics[scale=0.7]{testtout2.PNG}}
\medskip
{\footnotesize \includegraphics[scale=0.7]{table3.PNG}}
\end{center}
\end{frame}
%------ 3) ALGO DE MERSENNE-TWISTER -----
\subsection{Algorithme de Mersenne-Twister}
\begin{frame}{Algorithme de Mersenne-Twister}
{\scriptsize \inputminted{python}{mersenne.py}}
\end{frame}
\begin{frame}{Analyse spectral}
\centering
{\includegraphics[scale=0.43]{spectral.PNG}} \\
{\small Générateur congruentiel linéaire ou algorithme Blum Blum Shub}
\medskip
{\includegraphics[scale=0.43]{spectral2.PNG}} \\
{\small Algorithme de Mersenne-Twister}
\end{frame}
%------------------------------------
%-----PARTIE 3 : CONCLUSION ---------
%------------------------------------
\section{III - Conclusion}
%------ COMPARAISON BBS ------------
\subsection{Comparaison avec le BBS}
\begin{frame}{Comparaison avec le BBS}
\begin{beamerboxesrounded}[scheme=objectif,shadow=true]{Algorithme de Blum Blum Shub}
L'algorithme de Blum Blum Shub est un générateur de nombres pseudo-aléatoires \textbf{cryptographiquement sûr}. Il génère une suite d'entiers selon la relation de récurrence $u_{n+1} = {u_n}^2$ $mod$ $M$.
\end{beamerboxesrounded}
\medskip
\begin{beamerboxesrounded}[scheme=explication,shadow=true]{Qualité du générateur}
L'algorithme de Blum Blum Shub a le même défaut que l'ensemble des générateurs congruentiels linéaires : il échoue au test spectral à des dimensions pourtant faibles (en général 2 ou 3).
\end{beamerboxesrounded}
\medskip
\begin{beamerboxesrounded}[scheme=propriete,shadow=true]{Conclusion}
Un générateur cryptographiquement sûr (ie. imprévisible en temps polynomial) peut ne pas réussir la plupart des tests statistiques que réussissent les bons générateurs. \\
Cryptographiquement sûr $\not \Rightarrow$ Aléatoire au sens de Martin-Löf \\
Mon binôme a constaté que la réciproque était fausse aussi.
\end{beamerboxesrounded}
\end{frame}
%-------------------------------
%--------- ANNEXES --------------
%-------------------------------
% --------------------------
{\1
\begin{frame}[plain,noframenumbering]
\finalpage{Merci de votre attention !}
\end{frame}}
\end{document}