après remarques tof

[hdrcouchot.git] / annexePreuveDistribution.tex

diff --git a/annexePreuveDistribution.tex b/annexePreuveDistribution.tex
index 878b3170f013948a58ac33e53d1e43e2568b32ce..af03fed84a474785dbc7c8d940ce76452a21fdb4 100644 (file)
--- a/annexePreuveDistribution.tex
+++ b/annexePreuveDistribution.tex
@@ -1,4 +1,5 @@
- 
+
+\section{Chaînes de Markov associées à $\textsc{giu}(f)$}  

 Considérons le lemme technique suivant:
 \begin{lemma}\label{lem:stoc}
 Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\textsc{giu}(f)$, et  $M$  la matrice 
 Considérons le lemme technique suivant:
 \begin{lemma}\label{lem:stoc}
 Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\textsc{giu}(f)$, et  $M$  la matrice 


@@ -8,7 +9,7 @@ Alors $M$ est une matrice stochastique régulière si et seulement si
 $\textsc{giu}(f)$ est fortement connexe.
 \end{lemma}
 
 $\textsc{giu}(f)$ est fortement connexe.
 \end{lemma}
 

-\begin{Proof}  
+\begin{proof}  

 On remarque tout d'abord que $M$ 
 est une matrice stochastique par construction.
 Supposons $M$ régulière. 
 On remarque tout d'abord que $M$ 
 est une matrice stochastique par construction.
 Supposons $M$ régulière. 


@@ -28,22 +29,11 @@ on peut conclure que, si
 $k$ est le plus petit multiple commun de $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^n \rrbracket  \}$ alors
 $\forall i,j  \in \llbracket  1, 2^n \rrbracket,  \check{M}_{ij}^{k}>0$. 
 Ainsi, $\check{M}$ et donc $M$ sont régulières.
 $k$ est le plus petit multiple commun de $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^n \rrbracket  \}$ alors
 $\forall i,j  \in \llbracket  1, 2^n \rrbracket,  \check{M}_{ij}^{k}>0$. 
 Ainsi, $\check{M}$ et donc $M$ sont régulières.

-\end{Proof}
-
-Ces résultats permettent formuler et de prouver le théorème suivant:
-
-\begin{theorem}
-  Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{giu}(f)$ son 
-  graphe d'itérations , $\check{M}$ sa matrice d'adjacence
-  et $M$ une matrice  $2^n\times 2^n$  définie comme dans le lemme précédent.
-  Si $\textsc{giu}(f)$ est fortement connexe, alors 
-  la sortie du générateur de nombres pseudo aléatoires détaillé par 
-  l'algorithme~\ref{CI Algorithm} suit une loi qui 
-  tend vers la distribution uniforme si 
-  et seulement si  $M$ est une matrice doublement stochastique.
-\end{theorem}
-
-\begin{Proof}
+\end{proof}
+
+Ces résultats permettent formuler et de prouver le théorème annoncé.
+\PrngCIUniforme*
+\begin{proof}

   $M$ est une matrice stochastique régulière (Lemme~\ref{lem:stoc}) 
   qui a un unique vecteur de probabilités stationnaire
   (Théorème \ref{th}).
   $M$ est une matrice stochastique régulière (Lemme~\ref{lem:stoc}) 
   qui a un unique vecteur de probabilités stationnaire
   (Théorème \ref{th}).


@@ -53,14 +43,13 @@ Ces résultats permettent formuler et de prouver le théorème suivant:
   la somme des valeurs de chaque colonne de $M$  est 1, 
   \textit{i.e.} si et seulement si 
   $M$ est  doublement  stochastique.
   la somme des valeurs de chaque colonne de $M$  est 1, 
   \textit{i.e.} si et seulement si 
   $M$ est  doublement  stochastique.

-\end{Proof}
-
+\end{proof}

 
 

+\section{Chaoticité de la fonction $G_{f_u,\mathcal{P}}$ dans
+$(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$}

 
 

-Montrons que
-\begin{lemma}
-$d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
-\end{lemma}
+Montrons le théorème
+\distancedsxnp*

 
 
 \begin{proof}
 
 
 \begin{proof}


@@ -74,10 +63,10 @@ $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$.
 Réciproquement si $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$, alors
 $\forall k \in \mathds{N}, v^k=\check{v}^k$ d'après la définition de $d$.
 Or les éléments entre les positions $p+1$ et  $p+n$ 
 Réciproquement si $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$, alors
 $\forall k \in \mathds{N}, v^k=\check{v}^k$ d'après la définition de $d$.
 Or les éléments entre les positions $p+1$ et  $p+n$ 

-sont nules et correspondent à $|u^0-\check{u}^0|$, 
+sont nulles et correspondent à $|u^0-\check{u}^0|$, 

 on peut conclure que $u^0=\check{u}^0$.
 On peut étendre ce résultat aux $n \times \max{(\mathcal{P})}$ premiers 
 on peut conclure que $u^0=\check{u}^0$.
 On peut étendre ce résultat aux $n \times \max{(\mathcal{P})}$ premiers 

-bloc engendrant $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$, 
+blocs engendrant $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$, 

 et en vérifiant tous les  $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$.
  \item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ est évidemment  symétrique 
 ($d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\check{s},s)$). 
 et en vérifiant tous les  $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$.
  \item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ est évidemment  symétrique 
 ($d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\check{s},s)$). 


@@ -88,94 +77,92 @@ aussi.
 
 
 
 
 
 

-\begin{theorem}
-La fonction $G_{f_u,\mathcal{P}}$ est chaotique sur 
- $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ si et seulement si 
-graphe d'itération $\textsc{giu}_{\mathcal{P}}(f)$ 
-est fortement connexe.
-\end{theorem}
+Montrons que: 
+\begin{lemma}
+Le graphe d'itérations $\textsc{giu}_{\mathcal{P}}(f)$ 
+est fortement connexe si et seulement si 
+la fonction $G_{f_u,\mathcal{P}}$ est topologiquement transitive sur
+$(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$. 
+\end{lemma}\label{prop:trans}

 
 \begin{proof}
 
 \begin{proof}

-Suppose that $\Gamma_{\mathcal{P}}(f)$ is strongly connected. 
-Let $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v})) 
-\in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$.
-We will find a point $y$ in the open ball $\mathcal{B}(x,\varepsilon )$ and
-$n_0 \in \mathds{N}$ such that $G_f^{n_0}(y)=\check{x}$: this strong transitivity
-will imply the transitivity property.
-We can suppose that $\varepsilon <1$ without loss of generality. 
-
-Let us denote by $(E,(U,V))$  the elements of $y$. As
-$y$ must be in $\mathcal{B}(x,\varepsilon)$ and  $\varepsilon < 1$,
-$E$ must be equal to $e$. Let $k=\lfloor \log_{10} (\varepsilon) \rfloor +1$.
-$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ must be lower than
-$\varepsilon$, so the $k$ first digits of the fractional part of 
-$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ are null.
-Let $k_1$ the smallest integer such that, if $V^0=v^0$, ...,  $V^{k_1}=v^{k_1}$,
- $U^0=u^0$, ..., $U^{\sum_{l=0}^{k_1}V^l-1} = u^{\sum_{l=0}^{k_1}v^l-1}$.
-Then $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))<\varepsilon$.
-In other words, any $y$ of the form $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}),
-(v^0, ..., v^{k_1}))$ is in $\mathcal{B}(x,\varepsilon)$.
-
-Let $y^0$ such a point and $z=G_f^{k_1}(y^0) = (e',(u',v'))$. $\Gamma_{\mathcal{P}}(f)$
-being strongly connected, there is a path between $e'$ and $\check{e}$. Denote
-by $a_0, \hdots, a_{k_2}$ the edges visited by this path. We denote by
-$V^{k_1}=|a_0|$ (number of terms in the finite sequence $a_1$),
-$V^{k_1+1}=|a_1|$, ..., $V^{k_1+k_2}=|a_{k_2}|$, and by 
+Supposons tout d'abord que  $G_{f_u,\mathcal{P}}$ fortement connexe.
+Soit $x=(e,(u,v)),\check{x}=(\check{e},(\check{u},\check{v})) 
+\in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ et $\varepsilon >0$.
+On cherche un point $y$ dans une boule ouverte $\mathcal{B}(x,\varepsilon )$ 
+et un nombre 
+$n_0 \in \mathds{N}$ tels que $G_{f_u,\mathcal{P}}^{n_0}(y)=\check{x}$: 
+Cette transitivité forte entraînera la propriété de transitivité classique.
+On peut supposer que $\varepsilon <1$ sans perte de généralité.
+
+Soit $(E,(U,V))$ les éléments de  $y$. Comme 
+$y$ doit appartenir à $\mathcal{B}(x,\varepsilon)$ et  $\varepsilon < 1$,
+$E$ est égal à $e$. 
+Soit $k=\lfloor \log_{10} (\varepsilon) \rfloor +1$.
+La distance $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ est inférieure à 
+$\varepsilon$: les  $k$ premiers éléments de la partie décimale de 
+$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))$ sont nuls.
+Soit $k_1$ le plus petit entier tel que, si $V^0=v^0$, ...,  $V^{k_1}=v^{k_1}$,
+alors $U^0=u^0$, ..., $U^{\sum_{l=0}^{k_1}V^l-1} = u^{\sum_{l=0}^{k_1}v^l-1}$.
+Alors $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u,v),(U,V))<\varepsilon$.
+En d'autres mots, chaque $y$ de la forme $(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}),
+(v^0, ..., v^{k_1}))$ est dans $\mathcal{B}(x,\varepsilon)$.
+
+Soit $y^0$ un tel point et $z=G_{f_u,\mathcal{P}}^{k_1}(y^0) = (e',(u',v'))$. 
+$G_{f_u,\mathcal{P}}$ étant fortement connexe,
+il existe un chemin entre $e'$ et $\check{e}$. 
+Soit $a_0, \hdots, a_{k_2}$ les arêtes visitées le long de ce chemin. 
+On fixe $V^{k_1}=|a_0|$ 
+(le nombre de termes dans la séquence finie $a_1$),
+$V^{k_1+1}=|a_1|$, ..., $V^{k_1+k_2}=|a_{k_2}|$, et 

 $U^{k_1}=a_0^0$, $U^{k_1+1}=a_0^1$, ..., $U^{k_1+V_{k_1}-1}=a_0^{V_{k_1}-1}$,
 $U^{k_1}=a_0^0$, $U^{k_1+1}=a_0^1$, ..., $U^{k_1+V_{k_1}-1}=a_0^{V_{k_1}-1}$,

-$U^{k_1+V_{k_1}}=a_1^{0}$, $U^{k_1+V_{k_1}+1}=a_1^{1}$,...
+$U^{k_1+V_{k_1}}=a_1^{0}$, $U^{k_1+V_{k_1}+1}=a_1^{1}$,\ldots

 
 

-Let $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 
+Soit $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 

  a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},$ \linebreak
  $\check{u}^0, \check{u}^1, ...),(v^0, ..., v^{k_1},|a_0|, ...,
  a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},$ \linebreak
  $\check{u}^0, \check{u}^1, ...),(v^0, ..., v^{k_1},|a_0|, ...,

- |a_{k_2}|,\check{v}^0, \check{v}^1, ...)))$. So $y\in \mathcal{B}(x,\varepsilon)$
- and $G_{f}^{k_1+k_2}(y)=\check{x}$.
+ |a_{k_2}|,\check{v}^0, \check{v}^1, ...)))$. 
+Ainsi
+ $y\in \mathcal{B}(x,\varepsilon)$
+ et $G_{f}^{k_1+k_2}(y)=\check{x}$.

  
  

- 
-Conversely, if $\Gamma_{\mathcal{P}}(f)$ is not strongly connected, then there are 
-2 vertices $e_1$ and $e_2$ such that there is no path between $e_1$ and $e_2$.
-That is, it is impossible to find $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$
-and $n \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$
-cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transitive.
+Réciproquement, si  $G_{f_u,\mathcal{P}}$ n'est pas fortement connexe,
+il y a donc deux n{\oe}uds 
+$e_1$ et $e_2$ sans chemins entre eux.
+Il n'est ainsi pas possible de trouver un couple $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$
+et $n \mathds{N}$ tel que  $G_{f_u,\mathcal{P}}^n(e,(u,v))_1=e_2$. 
+La boule ouverte  $\mathcal{B}(e_2, 1/2)$ ne peut ainsi pas être atteinte
+depuis n'importe quel voisins de $e_1$: 
+$G_{f_u,\mathcal{P}}$ n'est pas transitive.

 \end{proof}
 
 
 \end{proof}
 
 

-We show now that,
-\begin{prpstn}
-If $\Gamma_{\mathcal{P}}(f)$ is strongly connected, then $G_f$ is 
-regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
-\end{prpstn}
+Montrons maintenant que 
+\begin{lemma}
+Si $G_{f_u,\mathcal{P}}$ est fortement connexe, alors $G_{f_u,\mathcal{P}}$ est  
+régulière sur  $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
+\end{lemma}

 
 \begin{proof}
 
 \begin{proof}

-Let $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. 
-As in the proofs of Prop.~\ref{prop:trans}, let $k_1 \in \mathds{N}$ such
-that 
+Soit $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ et $\varepsilon >0$. 
+Comme dans la preuve du lemme~\ref{prop:trans}, soit $k_1 \in \mathds{N}$ tel
+que 

 $$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \mid \right.$$
 $$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\}
 \subset \mathcal{B}(x,\varepsilon),$$
 $$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \mid \right.$$
 $$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\}
 \subset \mathcal{B}(x,\varepsilon),$$

-and $y=G_f^{k_1}(e,(u,v))$. $\Gamma_{\mathcal{P}}(f)$ being strongly connected,
-there is at least a path from the Boolean state $y_1$ of $y$ and $e$.
-Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path.
-Then the point:
+et $y=G_{f_u,\mathcal{P}}^{k_1}(e,(u,v))$. 
+$G_{f_u,\mathcal{P}}$ étant fortement connexe,
+il existe au moins un chemin entre l'état booléen $y_1$ de $y$ et $e$.
+Nommons $a_0, \hdots, a_{k_2}$ les arêtes d'un tel chemin.
+Le point

 $$(e,((u^0, ..., u^{v^{k_1-1}},a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 
  a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},u^0, ..., u^{v^{k_1-1}},$$
 $$a_0^0, ...,a_{k_2}^{|a_{k_2}|}...),(v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,...))$$
 $$(e,((u^0, ..., u^{v^{k_1-1}},a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 
  a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},u^0, ..., u^{v^{k_1-1}},$$
 $$a_0^0, ...,a_{k_2}^{|a_{k_2}|}...),(v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,...))$$

-is a periodic point in the neighborhood $\mathcal{B}(x,\varepsilon)$ of $x$.
+est un point périodique dans le voisinage $\mathcal{B}(x,\varepsilon)$ de $x$.

 \end{proof}
 
 \end{proof}
 

-$G_f$ being topologically transitive and regular, we can thus conclude that
-\begin{thrm}
-The function $G_f$ is chaotic on $(\mathcal{X}_{\mathsf{N},\mathcal{P}},d)$ if
-and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is strongly connected.
-\end{thrm}
+$G_{f_u,\mathcal{P}}$ étant topologiquement transitive and régulière, 
+on peut démontrer le théorème:
+\thmchoticitgfp*
+

 
 

-\begin{crllr}
-  The pseudorandom number generator $\chi_{\textit{14Secrypt}}$ is not chaotic
-  on $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ for the negation function.
-\end{crllr}
-\begin{proof}
-  In this context, $\mathcal{P}$ is the singleton $\{b\}$.
-  If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach 
-  its neighborhood and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected. 
-  If $b$ is even, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach itself 
-  and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected.
-\end{proof}