]> AND Private Git Repository - hdrcouchot.git/blob - talk/gclth2.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
ajout du dossier talk
[hdrcouchot.git] / talk / gclth2.tex
1 \begin{theorem}[Théorème 2]
2 La période de la suite produite par le générateur congruentiel linéaire est $m-1$ si %et seulement si 
3 \begin{enumerate}
4 \item\label{item:gcl2:c1}  $x_0$ n'est pas nul;
5 \item\label{item:gcl2:c2}  $m$ est un nombre premier;
6 \item\label{item:gcl2:c4}  $a$ est d'ordre ${m-1}$
7 \end{enumerate}
8 \end{theorem}
9
10
11 \begin{theorem}[Théorème 3]
12 Soit $m$ un nombre premier. On peut toujours trouver $a$ d'ordre $m-1$,
13 $1 \le a \le m-1$.
14 \end{theorem}
15
16
17 \begin{exampleblock}{Analyse de l'exemple de la Figure~2}
18 On a $m=181$ et $a=19\times80\times125 \equiv 131 \mod 181$ et 
19
20 \begin{enumerate}
21 \item  $x_0=1$ n'est pas nul;
22 \item  $m=181$ est un nombre premier;
23 \item 
24 \begin{itemize}
25 \begin{footnotesize}
26 \item 19 est d'ordre $4$, 80 est d'ordre $9$ et 125 est d'ordre $5$;
27 \item 4, 5 et 9 premiers entre eux $\leadsto$ $a=19\times80\times125$ est d'ordre 180;
28 \end{footnotesize}
29 \end{itemize}
30 \end{enumerate}
31 La période d'un tel générateur est 180. 
32 \end{exampleblock}
33
34
35