X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/103fee06d77ee199f8956ccb0747b45676c834e5..46fc71ad146f83c82660e358a1a1bc2ccc0f00e6:/14Secrypt.tex

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}.
+