From: Jean-François Couchot <couchot@couchot.iut-bm.univ-fcomte.fr>
Date: Wed, 22 Jul 2015 12:36:47 +0000 (+0200)
Subject: avant chgt de salle
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/commitdiff_plain/46fc71ad146f83c82660e358a1a1bc2ccc0f00e6?ds=sidebyside;hp=-c

avant chgt de salle
---

46fc71ad146f83c82660e358a1a1bc2ccc0f00e6
diff --git a/14Secrypt.tex b/14Secrypt.tex
index b2ae05d..e160bc3 100644
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -528,3 +528,45 @@ Sans entrer dans les détails de la preuve, on remarque que le calcul
 de cette borne ne tient pas en compte le fait qu'on préfère enlever des 
 chemins hamiltoniens équilibrés. 
 En intégrant cette contrainte, la borne supérieure pourrait être réduite.
+
+\section{Et les itérations généralisées?}
+Le chaptire précédent a présenté un algorithme de 
+PRNG construit à partir d'itérations unaires. 
+On pourrait penser que cet algorithme est peu efficace puisqu'il 
+dispose d'une fonction $f$ de $\Bool^n$ dans lui même mais il ne modifie à 
+chaque itération qu'un seul élément de $[n]$.
+On pourrait penser à un algorithme basé sur les itérations généralisées, 
+c'est-à-dire qui modifierait une partie des éléments de $[n]$ à chaque 
+itération.
+C'est l'algorithme~\ref{CI Algorithm:prng:g}.
+
+\begin{algorithm}[h]
+%\begin{scriptsize}
+\KwIn{une fonction $f$, un nombre d'itérations $b$, 
+une configuration initiale $x^0$ ($n$ bits)}
+\KwOut{une configuration $x$ ($n$ bits)}
+$x\leftarrow x^0$\;
+$k\leftarrow b $\;
+\For{$i=1,\dots,k$}
+{
+$s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$\;
+$x\leftarrow{F_{f_g}(s,x)}$\;
+}
+return $x$\;
+%\end{scriptsize}
+\caption{PRNG basé sur les itérations généralisées.}
+\label{CI Algorithm:prng:g}
+\end{algorithm}
+
+Par rapport à l'algorithme~\ref{CI Algorithm} seule 
+la ligne $s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$ est différente.
+Dans celle-ci la fonction  $\textit{Set}   :    \{1,\ldots,2^n\}   \rightarrow
+\mathcal{P}(\{1,\ldots   n\})$   retourne  l'ensemble   dont   la   fonction
+caractéristique  serait  représentée par  le  nombre  donné  en argument.
+Par exemple, pour $n=3$, l'ensemble $\textit{Set}(6)$ vaudraitt $\{3,2\}$.
+On remarque aussi que l'argument de la fonction  $\textit{Random}$
+passe de $n$ à $2^n$.
+
+Dans ce qui suit, on va étudier cet algorithme comparativement à 
+l'algorithme~\ref{CI Algorithm}.
+
diff --git a/15RairoGen.tex b/15RairoGen.tex
index fe1c034..a1b6b23 100644
--- a/15RairoGen.tex
+++ b/15RairoGen.tex
@@ -46,8 +46,7 @@ $x\leftarrow{F_{f_u}(s,x)}$\;
 }
 return $x$\;
 %\end{scriptsize}
-\caption{Algorithme de génération de nombres pseudo aléatoires 
-à l'aide de la fonction chaotique $G_f$}
+\caption{PRNG basé sur les itérations unaires.}
 \label{CI Algorithm}
 \end{algorithm}
 
diff --git a/main.tex b/main.tex
index 071ab50..4ef11c8 100644
--- a/main.tex
+++ b/main.tex
@@ -221,7 +221,7 @@ On montre qu'on a des résultats similaires.
 \chapter{Caractérisation des générateurs chaotiques}
 \input{15RairoGen}
 
-\chapter{Engendrer une classe de générateurs}
+\chapter{Les générateurs issus des codes de Gray}
 \input{14Secrypt}