ajout espace bib

[rairo15.git] / chaos.tex

diff --git a/chaos.tex b/chaos.tex
index 91b8717f107e292c4928b2a63fd622494c312bcf..d5ab5f94edc376ad4b7a09529fb1dd0d6d7f5511 100644 (file)
--- a/chaos.tex
+++ b/chaos.tex
@@ -40,41 +40,41 @@ This necessitates a rigorous proof, which is the aim of this section.
 Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f :
 \mathcal{X} \rightarrow \mathcal{X}$.
 
 Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f :
 \mathcal{X} \rightarrow \mathcal{X}$.
 

-\begin{Def}
+\begin{dfntn}

 The function $f$ is said to be \emph{topologically transitive} if, for any pair of open sets
 $U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq
 \varnothing$.
 The function $f$ is said to be \emph{topologically transitive} if, for any pair of open sets
 $U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq
 \varnothing$.

-\end{Def}
+\end{dfntn}

 
 

-\begin{Def}
+\begin{dfntn}

 An element $x$ is a \emph{periodic point} for $f$ of period $n\in \mathds{N}^*$
 if $f^{n}(x)=x$.% The set of periodic points of $f$ is denoted $Per(f).$
 An element $x$ is a \emph{periodic point} for $f$ of period $n\in \mathds{N}^*$
 if $f^{n}(x)=x$.% The set of periodic points of $f$ is denoted $Per(f).$

-\end{Def}
+\end{dfntn}

 
 

-\begin{Def}
+\begin{dfntn}

 $f$ is said to be \emph{regular} on $(\mathcal{X}, \tau)$ if the set of periodic
 points for $f$ is dense in $\mathcal{X}$: for any point $x$ in $\mathcal{X}$,
 any neighborhood of $x$ contains at least one periodic point (without
 necessarily the same period).
 $f$ is said to be \emph{regular} on $(\mathcal{X}, \tau)$ if the set of periodic
 points for $f$ is dense in $\mathcal{X}$: for any point $x$ in $\mathcal{X}$,
 any neighborhood of $x$ contains at least one periodic point (without
 necessarily the same period).

-\end{Def}
+\end{dfntn}

 
 
 
 

-\begin{Def}[Devaney's formulation of chaos~\cite{Devaney}]
+\begin{dfntn}[Devaney's formulation of chaos~\cite{Devaney}]

 The function $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and
 topologically transitive.
 The function $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and
 topologically transitive.

-\end{Def}
+\end{dfntn}

 
 The chaos property is strongly linked to the notion of ``sensitivity'', defined
 on a metric space $(\mathcal{X},d)$ by:
 
 
 The chaos property is strongly linked to the notion of ``sensitivity'', defined
 on a metric space $(\mathcal{X},d)$ by:
 

-\begin{Def}
+\begin{dfntn}

 \label{sensitivity} The function $f$ has \emph{sensitive dependence on initial conditions}
 if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any
 neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that
 $d\left(f^{n}(x), f^{n}(y)\right) >\delta $.
 
 The constant $\delta$ is called the \emph{constant of sensitivity} of $f$.
 \label{sensitivity} The function $f$ has \emph{sensitive dependence on initial conditions}
 if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any
 neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that
 $d\left(f^{n}(x), f^{n}(y)\right) >\delta $.
 
 The constant $\delta$ is called the \emph{constant of sensitivity} of $f$.

-\end{Def}
+\end{dfntn}

 
 Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is
 chaotic and $(\mathcal{X}, d)$ is a metric space, then $f$ has the property of
 
 Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is
 chaotic and $(\mathcal{X}, d)$ is a metric space, then $f$ has the property of


@@ -318,9 +318,9 @@ $$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \su
 
 
 Let us show that,
 
 
 Let us show that,

-\begin{proposition}
+\begin{prpstn}

 $d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.
 $d$ is a distance on $\mathcal{X}_{\mathsf{N},\mathcal{P}}$.

-\end{proposition}
+\end{prpstn}

 
 
 \begin{proof}
 
 
 \begin{proof}


@@ -342,10 +342,10 @@ definition of $d$. Then, as digits between positions $p+1$ and $p+n$ are null an
 Before being able to study the topological behavior of the general 
 chaotic iterations, we must first establish that:
 
 Before being able to study the topological behavior of the general 
 chaotic iterations, we must first establish that:
 

-\begin{proposition}
+\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)$.
  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{proposition}
+\end{prpstn}

 
 
 \begin{proof}
 
 
 \begin{proof}


@@ -433,11 +433,11 @@ since the function $f_0$ is equal to its inverse $f_0^{-1}$.
 \subsection{Proofs of chaos}
 
 We will show that,
 \subsection{Proofs of chaos}
 
 We will show that,

-\begin{proposition}
+\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)$.
 \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{proposition}
+\end{prpstn}

 
 
 \begin{proof}
 
 
 \begin{proof}


@@ -485,10 +485,10 @@ cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transiti
 
 
 We show now that,
 
 
 We show now that,

-\begin{proposition}
+\begin{prpstn}

 If $\Gamma_{\mathcal{P}}(f)$ is strongly connected, then $G_f$ is 
 regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
 If $\Gamma_{\mathcal{P}}(f)$ is strongly connected, then $G_f$ is 
 regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.

-\end{proposition}
+\end{prpstn}

 
 \begin{proof}
 Let $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. 
 
 \begin{proof}
 Let $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. 


@@ -508,15 +508,15 @@ 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
 \end{proof}
 
 $G_f$ being topologically transitive and regular, we can thus conclude that

-\begin{Theo}
+\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.
 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{Theo}
+\end{thrm}

 
 

-\begin{Corollary}
+\begin{crllr}

   The pseudorandom number generator $\chi_{\textit{14Secrypt}}$ is not chaotic
   on $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ for the negation function.
   The pseudorandom number generator $\chi_{\textit{14Secrypt}}$ is not chaotic
   on $(\mathcal{X}_{\mathsf{N},\{b\}},d)$ for the negation function.

-\end{Corollary}
+\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 
 \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 


@@ -524,3 +524,9 @@ and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is 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}
   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.
+
+
+ 
\ No newline at end of file