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

diff --git a/14Secrypt.tex b/14Secrypt.tex
index b2ae05d..a60e4ff 100644
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -13,13 +13,13 @@ graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graph
 arête sortante et une arête entrante.
 
 
-This aim of this section is to show 
-that finding DSSC matrices from a hypercube
-is a typical finite domain satisfaction 
-problem, classically denoted as 
-Constraint Logic Programming on Finite Domains (CLPFD). 
-This part is addressed in the first section. Next, we analyse the first
-results to provide a generation of DSSC matrices with small mixing times. 
+% This aim of this section is to show 
+% that finding DSSC matrices from a hypercube
+% is a typical finite domain satisfaction 
+% problem, classically denoted as 
+% Constraint Logic Programming on Finite Domains (CLPFD). 
+% This part is addressed in the first section. Next, we analyse the first
+% results to provide a generation of DSSC matrices with small mixing times. 
 
 \section{Programmation logique par contraintes sur des domaines finis}
 Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments. 
@@ -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}.
+