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.
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}
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.
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}
\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}
\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}
\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}
$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^{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)$.
$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}
\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}
\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}
