chapitre chaos repris

[hdrcouchot.git] / annexePreuvePRNGchotique.tex

\subsection{A metric on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$}

We define a distance $d$ on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$ as follows. 
Consider 
$x=(e,s)$ and $\check{x}=(\check{e},\check{s})$ in 
$\mathcal{X}_{\mathsf{N},\mathcal{P}} = \mathds{B}^\mathsf{N} \times \mathds{S}_{\mathsf{N},\mathcal{P}} $,
where $s=(u,v)$ and $\check{s}=(\check{u},\check{v})$ are in $ \mathds{S}_{\mathsf{N},\mathcal{P}} = 
\mathcal{S}_{\llbracket 1, \mathsf{N} \rrbracket} \times \mathcal{S}_\mathcal{P}$. 
\begin{itemize}
\item $e$ and $\check{e}$ are integers belonging in $\llbracket 0, 2^{\mathsf{N}-1} \rrbracket$. The Hamming distance
on their binary decomposition, that is, the number of dissimilar binary digits, constitutes the integral
part of $d(X,\check{X})$.
\item The fractional part is constituted by the differences between $v^0$ and $\check{v}^0$, followed by the differences
between finite sequences $u^0, u^1, \hdots, u^{v^0-1}$ and  $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$, followed by 
 differences between $v^1$ and $\check{v}^1$, followed by the differences
between $u^{v^0}, u^{v^0+1}, \hdots, u^{v^1-1}$ and  $\check{u}^{\check{v}^0}, \check{u}^{\check{v}^0+1}, \hdots, \check{u}^{\check{v}^1-1}$, etc.
More precisely, let $p = \lfloor \log_{10}{(\max{\mathcal{P}})}\rfloor +1$ and $n = \lfloor \log_{10}{(\mathsf{N})}\rfloor +1$.
\begin{itemize}
\item The $p$ first digits of $d(x,\check{x})$ is $|v^0-\check{v}^0|$ written in decimal numeration (and with $p$ digits).
\item The next $n\times \max{(\mathcal{P})}$ digits aim at measuring how much $u^0, u^1, \hdots, u^{v^0-1}$ differs from $\check{u}^0, \check{u}^1, \hdots, \check{u}^{\check{v}^0-1}$. The $n$ first
digits are $|u^0-\check{u}^0|$. They are followed by 
$|u^1-\check{u}^1|$ written with $n$ digits, etc.
\begin{itemize}
\item If
$v^0=\check{v}^0$, then the process is continued until $|u^{v^0-1}-\check{u}^{\check{v}^0-1}|$ and the fractional
part of $d(X,\check{X})$ is completed by 0's until reaching
$p+n\times \max{(\mathcal{P})}$ digits.
\item If $v^0<\check{v}^0$, then the $ \max{(\mathcal{P})}$  blocs of $n$
digits are $|u^0-\check{u}^0|$, ..., $|u^{v^0-1}-\check{u}^{v^0-1}|$,
$\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digits), followed by 0's if required.
\item The case $v^0>\check{v}^0$ is dealt similarly.
\end{itemize}
\item The next $p$ digits are $|v^1-\check{v}^1|$, etc.
\end{itemize}
\end{itemize}




\begin{xpl}
Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=3$), and that
$s=\left\{
\begin{array}{l}
u=\underline{6,} ~ \underline{11,5}, ...\\
v=1,2,...
\end{array}
\right.$
while
$\check{s}=\left\{
\begin{array}{l}
\check{u}=\underline{6,4} ~ \underline{1}, ...\\
\check{v}=2,1,...
\end{array}
\right.$.

So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$
Indeed, the $p=2$ first digits are 01, as $|v^0-\check{v}^0|=1$, 
and we use $p$ digits to code this difference ($\mathcal{P}$ being $\{1,2,11\}$, this difference can be equal to 10). We then take the $v^0=1$ first terms of $u$, each term being coded in $n=2$ digits, that is, 06. As we can iterate
at most $\max{(\mathcal{P})}$ times, we must complete this
value by some 0's in such a way that the obtained result
has $n\times \max{(\mathcal{P})}=22$ digits, that is: 
0600000000000000000000. Similarly, the $\check{v}^0=2$ first
terms in $\check{u}$ are represented by 0604000000000000000000, and the absolute value of their
difference is equal to 0004000000000000000000. These digits are concatenated to 01, and
we start again with the remainder of the sequences.
\end{xpl}


\begin{xpl}
Consider now that $\mathsf{N}=9$, and $\mathcal{P}=\{2,7\}$, and that

$s=\left\{
\begin{array}{l}
u=\underline{6,7,} ~ \underline{4,2,} ...\\
v=2,2,...
\end{array}
\right.$
while
$\check{s}=\left\{
\begin{array}{l}
\check{u}=\underline{4, 9, 6, 3, 6, 6, 7,} ~ \underline{9, 8}, ...\\
\check{v}=7,2,...
\end{array}
\right.$

So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.5173633305600000...$, as $|v^0-\check{v}^0|=5$, $|4963667-6700000| = 1736333$, $|v^1-\check{v}^1|=0$,
and $|9800000-4200000| = 5600000$.
\end{xpl}



$d$ can be more rigorously written as follows:
$$d(x,\check{x})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})+d_{\mathds{B}^\mathsf{N}}(e,\check{e}),$$
where: % $p=\max \mathcal{P}$ and:
\begin{itemize}
\item $d_{\mathds{B}^\mathsf{N}}$ is the Hamming distance,
\item $\forall s=(u,v), \check{s}=(\check{u},\check{v}) \in \mathcal{S}_{\mathsf{N},\mathcal{P}}$,\newline 
$$\begin{array}{rcl}
 d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) &= &
   \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} 
   \bigg(|v^k - \check{v}^k|  \\
   & & + \left| \sum_{l=0}^{v^k-1} 
       \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{(l+1)n}} -
       \sum_{l=0}^{\check{v}^k-1} 
       \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{(l+1)n}} \right| \bigg)
\end{array}
$$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.$$
\end{itemize}


Let us show that,
\begin{prpstn}
$d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
\end{prpstn}


\begin{proof}
 $d_{\mathds{B}^\mathsf{N}}$ is the Hamming distance. We will prove that 
 $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ is a distance
too, thus $d$ will also be a distance, being the sum of two distances.
 \begin{itemize}
\item Obviously, $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})\geqslant 0$, and if $s=\check{s}$, then 
$d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$. Conversely, if $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=0$, then 
$\forall k \in \mathds{N}, v^k=\check{v}^k$ due to the 
definition of $d$. Then, as digits between positions $p+1$ and $p+n$ are null and correspond to $|u^0-\check{u}^0|$, we can conclude that $u^0=\check{u}^0$. An extension of this result to the whole first $n \times \max{(\mathcal{P})}$ bloc leads to $u^i=\check{u}^i$, $\forall i \leqslant v^0=\check{v}^0$, and by checking all the $n \times \max{(\mathcal{P})}$ blocs, $u=\check{u}$.
 \item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}$ is clearly symmetric 
($d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s})=d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\check{s},s)$). 
\item The triangle inequality is obtained because the absolute value satisfies it too.
 \end{itemize}
\end{proof}


Before being able to study the topological behavior of the general 
chaotic iterations, we must first establish that:

\begin{prpstn}
 For all $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, the function $G_f$ is continuous on 
$\left( \mathcal{X},d\right)$.
\end{prpstn}


\begin{proof}
We will show this result by using the sequential continuity. Consider a
sequence $x^n=(e^n,(u^n,v^n)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}^\mathds{N}$ such
that $d(x^n,x) \longrightarrow 0$, for some $x=(e,(u,v))\in
\mathcal{X}_{\mathsf{N},\mathcal{P}}$. We will show that
$d\left(G_f(x^n),G_f(x)\right) \longrightarrow 0$.
Remark that $u$ and $v$ are sequences of sequences.

As $d(x^n,x) \longrightarrow 0$, there exists 
$n_0\in\mathds{N}$ such that 
$d(x^n,x) < 10^{-(p+n \max{(\mathcal{P})})}$
(its $p+n \max{(\mathcal{P})}$ first digits are null). 
In particular, $\forall n \geqslant n_0, e^n=e$,
as the Hamming distance between the integral parts of
$x$ and $\check{x}$ is 0. Similarly, due to the nullity 
of the $p+n \max{(\mathcal{P})}$ first digits of 
$d(x^n,x)$, we can conclude that $\forall n \geqslant n_0$,
$(v^n)^0=v^0$, and that $\forall n \geqslant n_0$,
$(u^n)^0=u^0$, $(u^n)^1=u^1$, ..., $(u^n)^{v^0-1}=u^{v^0-1}$.
This implies that:
\begin{itemize}
\item $G_f(x^n)_1=G_f(x)_1$: they have the same
Boolean vector as first coordinate.
\item $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(\Sigma (u^n,v^n); \Sigma(u,v)) = 10^{p+n \max{(\mathcal{P})}} d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}((u^n,v^n); (u,v))$. As the right part of the equality tends
to 0, we can deduce that it is the case too for the left part of the equality, and so
$G_f(x^n)_2$ is convergent to $G_f(x)_2$.
\end{itemize}
\end{proof}



\subsection{$\Gamma_{\mathcal{P}}(f)$ as an extension of  $\Gamma(f)$}

Let $\mathcal{P}=\{p_1, p_2, \hdots, p_\mathsf{p}\}$.
We define the directed graph $\Gamma_{\mathcal{P}}(f)$ as follows.
\begin{itemize}
\item Its vertices are the $2^\mathsf{N}$ elements of $\mathds{B}^\mathsf{N}$.
\item Each vertex has $\displaystyle{\sum_{i=1}^\mathsf{p} \mathsf{N}^{p_i}}$ arrows, namely all the $p_1, p_2, \hdots, p_\mathsf{p}$ tuples 
  having their elements in $\llbracket 1, \mathsf{N} \rrbracket $.
\item There is an arc labeled $u_0, \hdots, u_{p_i-1}$, $i \in \llbracket 1, \mathsf{p} \rrbracket$ between vertices $x$ and $y$ if and only if 
$y=F_{f,p_i} (x, (u_0, \hdots, u_{p_i-1})) $.
\end{itemize}

It is not hard to see that the graph $\Gamma_{\{1\}}(f)$ is 
$\Gamma(f)$.

\begin{figure}[ht]
  \centering
  \begin{subfigure}[b]{0.45\textwidth}
    \centering
    \includegraphics[scale=0.85]{graphe1.pdf}
    \caption{$\Gamma(f_0)$}
    \label{graphe1}
  \end{subfigure}%
  ~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc.
  % (or a blank line to force the subfigure onto a new line)
  \begin{subfigure}[b]{0.3\textwidth}
    \centering  
    \includegraphics[scale=0.85]{graphe2.pdf}
    \caption{$\Gamma_{\{2,3\}}(f_0)$}
    \label{graphe2}
  \end{subfigure}
  ~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc.
  \caption{Iterating $f_0:(x_1,x_2) \mapsto (\overline{x_1}, \overline{x_2})$}
  \label{fig:itg}
\end{figure}


\begin{xpl}
Consider for instance $\mathsf{N}=2$, 
Let $f_0:\mathds{B}^2 \longrightarrow \mathds{B}^2$ be the negation function,
\textit{i.e.}, $f_0(x_1,x_2) = (\overline{x_1}, \overline{x_2})$, and consider
$\mathcal{P}=\{2,3\}$. The graphs of iterations are given in 
\textsc{Figure~\ref{fig:itg}}.
The \textsc{Figure~\ref{graphe1}} shows what happens when 
displaying each iteration result.
On the contrary, the \textsc{Figure~\ref{graphe2}} explicits the behaviors
when always applying 2 or 3 modification and next outputing results. 
Notice that here, orientations of arcs are not necessary 
since the function $f_0$ is equal to its inverse $f_0^{-1}$. 
\end{xpl}

\subsection{Proofs of chaos}

We will show that,
\begin{prpstn}
\label{prop:trans}
 $\Gamma_{\mathcal{P}}(f)$ is strongly connected if and only if $G_f$ is 
topologically transitive on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
\end{prpstn}


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

The next section shows how to generate functions and a iteration number $b$
such that $\Gamma_{\{b\}}$ is strongly connected.