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

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