modif presentation

[16dcc.git] / chaos.tex

diff --git a/chaos.tex b/chaos.tex
index a82d57cf03021e14b0c5edef7ead4db15fc6f8f0..69eedb0b3b55c4504a2e8b8f0a88c29556172ca4 100644 (file)
--- a/chaos.tex
+++ b/chaos.tex
@@ -26,9 +26,9 @@ $\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$
 if and only if $\Gamma(f)$ is strongly connected.
 However, the corollary which would say that $\chi_{\textit{14Secrypt}}$ is chaotic 
 cannot be directly deduced since we do not output all the successive
 if and only if $\Gamma(f)$ is strongly connected.
 However, the corollary which would say that $\chi_{\textit{14Secrypt}}$ is chaotic 
 cannot be directly deduced since we do not output all the successive

-values of iterating $F_f$. Only a few of them is concerned and 
+values of iterating $F_f$. Only a few of them are concerned and 

 any subsequence of a chaotic sequence  is   not  necessarily  
 any subsequence of a chaotic sequence  is   not  necessarily  

-a   chaotic  sequence  too.
+a   chaotic  sequence  as well.

 This necessitates a rigorous proof, which is the aim of this section.
 Let us firstly recall the theoretical framework in which this research takes place.
 
 This necessitates a rigorous proof, which is the aim of this section.
 Let us firstly recall the theoretical framework in which this research takes place.
 


@@ -235,8 +235,8 @@ between finite sequences $u^0, u^1, \hdots, u^{v^0-1}$ and  $\check{u}^0, \check
 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}
 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: zeros are added on the left if needed).
-\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
+\item The $p$ first digits of $d(x,\check{x})$ are $|v^0-\check{v}^0|$ written in decimal numeration (and with $p$ digits: zeros are added on the left if needed).
+\item The next $n\times \max{(\mathcal{P})}$ digits aim at measuring how much $u^0, u^1, \hdots, u^{v^0-1}$ differ 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}
 digits are $|u^0-\check{u}^0|$. They are followed by 
 $|u^1-\check{u}^1|$ written with $n$ digits, etc.
 \begin{itemize}


@@ -288,7 +288,7 @@ and we use $p$ digits to code this difference ($\mathcal{P}$ being $\{1,2,11\}$,
 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: 
 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
+0600000000000000000000. Similarly, the first $\check{v}^0=2$ 

 terms in $\check{u}$ are represented by 0604000000000000000000, and the value of their
 digit per digit absolute difference is equal to 0004000000000000000000. These digits are concatenated to 01, and
 we start again with the remainder of the sequences.
 terms in $\check{u}$ are represented by 0604000000000000000000, and the value of their
 digit per digit absolute difference is equal to 0004000000000000000000. These digits are concatenated to 01, and
 we start again with the remainder of the sequences.


@@ -358,7 +358,7 @@ $\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})}$ blocs 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)$). 
 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})}$ blocs 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.
+\item The triangle inequality is obtained because the absolute value satisfies it as well.

  \end{itemize}
 \end{proof}
 
  \end{itemize}
 \end{proof}
 


@@ -396,7 +396,7 @@ This implies that:
 \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
 \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
+to 0, we can deduce that it is also the case 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}
 $G_f(x^n)_2$ is convergent to $G_f(x)_2$.
 \end{itemize}
 \end{proof}


@@ -421,22 +421,20 @@ which is indeed $\textit{CIPRNG}_f^2(u,(1)_{n \in \mathds{N}})$.
 
 \begin{figure}[ht]
   \centering
 
 \begin{figure}[ht]
   \centering

-  \begin{subfigure}[b]{0.45\textwidth}
-    \centering
-    \includegraphics[scale=0.85]{graphe1.pdf}
-    \caption{$\Gamma(f_0)$}
+  \subfigure[$\Gamma(f_0)$]{
+      \begin{minipage}{0.45\textwidth}
+        \centering
+        \includegraphics[scale=0.85]{graphe1.pdf}
+      \end{minipage}

     \label{graphe1}
     \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)$}
+    }
+    \subfigure[$\Gamma_{\{2,3\}}(f_0)$]{
+      \begin{minipage}{0.3\textwidth}
+        \centering
+          \includegraphics[scale=0.85]{graphe2.pdf}
+      \end{minipage}

     \label{graphe2}
     \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}
   \caption{Iterating $f_0:(x_1,x_2) \mapsto (\overline{x_1}, \overline{x_2})$}
   \label{fig:itg}
 \end{figure}


@@ -448,11 +446,12 @@ 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 
 Figure~\ref{fig:itg}.
 \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 
 Figure~\ref{fig:itg}.

-The Figure~\ref{graphe1} shows what happens when 
-displaying each iteration result.
-On the contrary, Figure~\ref{graphe2} illustrates the behaviors
-when always applying either 2 or 3 modifications before generating results. 
-Notice that here, orientations of arcs are not necessary 
+Figure~\ref{graphe1} shows what happens when each iteration result  
+is displayed .
+On the contrary, Figure~\ref{graphe2} illustrates what happens when  2 or 3 modifications 
+are systematically applied 
+before results are generated. 
+Notice that here, the orientations of arcs are not necessary 

 since the function $f_0$ is equal to its inverse $f_0^{-1}$. 
 \end{xpl}
 
 since the function $f_0$ is equal to its inverse $f_0^{-1}$. 
 \end{xpl}
 


@@ -481,7 +480,7 @@ $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.
 $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}$,
+Let $k_1$ be 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}),
  $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}),


@@ -495,22 +494,29 @@ $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}$,...
 
 $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, \dots, u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, \dots, a_0^{|a_0|}, a_1^0, \dots, $ \linebreak 
-$a_1^{|a_1|},\dots, a_{k_2}^0, \dots, a_{k_2}^{|a_{k_2}|},$  
- $\check{u}^0, \check{u}^1, \dots),(v^0, \dots, v^{k_1},|a_0|, \dots,$\linebreak
- $|a_{k_2}|,\check{v}^0, \check{v}^1, \dots)))$. So $y\in \mathcal{B}(x,\varepsilon)$
+Let
+
+\begin{eqnarray*}
+y&=&(e,(
+(u^0, \dots, u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, \dots, a_0^{|a_0|}, a_1^0, \dots, 
+a_1^{|a_1|},\dots, a_{k_2}^0, \dots, a_{k_2}^{|a_{k_2}|},
+ \check{u}^0, \check{u}^1, \dots), \\
+&&\qquad(v^0, \dots, v^{k_1},|a_0|, \dots,
+ |a_{k_2}|,\check{v}^0, \check{v}^1, \dots))).
+\end{eqnarray*}
+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$.
  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}}$
+Thus, it is impossible to find $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$

 and $n\in \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}
 
 
 and $n\in \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,
+We now show  that,

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


@@ -537,7 +543,7 @@ is a periodic point in the neighborhood $\mathcal{B}(x,\varepsilon)$ of $x$.
 
 $G_f$ being topologically transitive and regular, we can thus conclude that
 \begin{thrm}
 
 $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
+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}
 
 and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is strongly connected.
 \end{thrm}
 


@@ -547,9 +553,9 @@ and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is strongly connected.
 \end{crllr}
 \begin{proof}
   In this context, $\mathcal{P}$ is the singleton $\{b\}$.
 \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 
+  If $b$ is even, no vertex $e$ of $\Gamma_{\{b\}}(f_0)$ can reach 

   its neighborhood and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected. 
   its neighborhood and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected. 

-  If $b$ is odd, any vertex $e$ of $\Gamma_{\{b\}}(f_0)$ cannot reach itself 
+  If $b$ is odd, no vertex $e$ of $\Gamma_{\{b\}}(f_0)$ can reach itself 

   and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected.
 \end{proof}
 
   and thus $\Gamma_{\{b\}}(f_0)$ is not strongly connected.
 \end{proof}
 


@@ -581,11 +587,11 @@ and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ is strongly connected.
 \end{table}
 The objective of this section is to evaluate the statistical performance of the 
 proposed CIPRNG method, by comparing the effects of its application on well-known
 \end{table}
 The objective of this section is to evaluate the statistical performance of the 
 proposed CIPRNG method, by comparing the effects of its application on well-known

-but defective generators. We considered during experiments the following PRNGs:
+but defective generators. We considered during the experiments the following PRNGs:

 linear congruential generator (LCG), multiple recursive generators (MRG)
 add-with-carry (AWC), subtract-with-borrow (SWB), shift-with-carry (SWC)
 Generalized Feedback Shift Register (GFSR), and nonlinear inversive generator.
 linear congruential generator (LCG), multiple recursive generators (MRG)
 add-with-carry (AWC), subtract-with-borrow (SWB), shift-with-carry (SWC)
 Generalized Feedback Shift Register (GFSR), and nonlinear inversive generator.

-A general overview and a recall of design of these famous generators 
+A general overview and a reminder of these  generators 

 can be found, for instance, in the documentation of the TestU01 statistical
 battery of tests~\cite{LEcuyerS07}. For each studied generator, we have compared
 their scores according to both NIST~\cite{Nist10} and DieHARD~\cite{Marsaglia1996}
 can be found, for instance, in the documentation of the TestU01 statistical
 battery of tests~\cite{LEcuyerS07}. For each studied generator, we have compared
 their scores according to both NIST~\cite{Nist10} and DieHARD~\cite{Marsaglia1996}