X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/3fc31015143d2bab7226a54390f3e1c5eba8f4d5..1991bb9a2fa344a1bc72ce3222b43bec10ff2f34:/chaos.tex?ds=inline diff --git a/chaos.tex b/chaos.tex index a82d57c..69eedb0 100644 --- 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 -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 -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. @@ -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} -\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} @@ -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: -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. @@ -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)$). -\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} @@ -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 -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} @@ -421,22 +421,20 @@ which is indeed $\textit{CIPRNG}_f^2(u,(1)_{n \in \mathds{N}})$. \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} - \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} - \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} @@ -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}. -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} @@ -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. -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}), @@ -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}$,... -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$. -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} -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)$. @@ -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} -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} @@ -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\}$. - 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. - 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} @@ -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 -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. -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}