ajout preuve chaos

[hdrcouchot.git] / annexePreuveDistribution.tex

 
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 
$2^n\times 2^n$  définie par
$M = \frac{1}{n}\check{M}$.
Alors $M$ est une matrice stochastique régulière si et seulement si
$\textsc{giu}(f)$ est fortement connexe.
\end{lemma}

\begin{Proof}  
On remarque tout d'abord que $M$ 
est une matrice stochastique par construction.
Supposons $M$ régulière. 
Il existe donc  $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket
1;  2^n  \rrbracket$. L'inégalité  $\check{M}_{ij}^k>0$  est alors établie.
Puisque $\check{M}_{ij}^k$ est le nombre de chemins de  $i$ à $j$ de longueur $k$
dans $\textsc{giu}(f)$ et puisque ce nombre est positif, alors 
$\textsc{giu}(f)$ est fortement connexe.

Réciproquement si $\textsc{giu}(f)$ 
est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut être construit pour atteindre  $j$  depuis $i$ en au plus $2^n$ étapes.
Il existe donc 
$k_{ij} \in \llbracket 1,  2^n \rrbracket$ tels que $\check{M}_{ij}^{k_{ij}}>0$.  
Comme tous les  multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que 
$\check{M}_{ij}^{l\times  k_{ij}}>0$, 
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.
\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}
  $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}).
  Soit $\pi$  défini par 
  $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$.
  On a  $\pi M = \pi$ si et seulement si
  la somme des valeurs de chaque colonne de $M$  est 1, 
  \textit{i.e.} si et seulement si 
  $M$ est  doublement  stochastique.
\end{Proof}



Montrons que
\begin{lemma}
$d$ est une distance sur $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
\end{lemma}


\begin{proof}
 $d_{\mathds{B}^\mathsf{N}}$ est la distance de Hamming.
 Prouvons que  
 $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ est aussi une distance;
$d$ sera ainsi une distance comme somme de deux distances.
 \begin{itemize}
\item De manière évidente, $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})\geqslant 0$, et si $s=\check{s}$, alors
$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$ 
sont nules 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 
bloc 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)$). 
\item l'inégalité triangulaire est établie puisque la valeur absolue la vérifie
aussi.
 \end{itemize}
\end{proof}



\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}

\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 
$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}$,...

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|},..., 
 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}$.
 
 
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.
\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}

\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 
$$\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:
$$(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$.
\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}

\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}