From a17d0a6c41e0afab24e5a0c8c806533db3ad753a Mon Sep 17 00:00:00 2001 From: couturie Date: Wed, 19 Sep 2012 21:05:57 +0200 Subject: [PATCH] ajout des refs entre documents --- prng_gpu.tex | 1260 +++++++++++++++++++++++---------------------- supplementary.tex | 353 ++++++++++++- 2 files changed, 989 insertions(+), 624 deletions(-) diff --git a/prng_gpu.tex b/prng_gpu.tex index 0ab28a1..11a1d56 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -16,7 +16,6 @@ \usepackage{ctable} \usepackage{tabularx} \usepackage{multirow} - % Pour mathds : les ensembles IR, IN, etc. \usepackage{dsfont} @@ -26,6 +25,10 @@ \usepackage{graphicx} % Pour faire des sous-figures dans les figures \usepackage{subfigure} +\usepackage{xr-hyper} +\usepackage{hyperref} +\externaldocument[A-]{supplementary} + \newtheorem{notation}{Notation} @@ -719,576 +722,590 @@ only for chaotic iterations of the form presented in Definition use of more general chaotic iterations to generate pseudorandom numbers faster, does not deflate their topological chaos properties. -\subsection{Proofs of Chaos of the General Formulation of the Chaotic Iterations} -\label{deuxième def} -Let us consider the discrete dynamical systems in chaotic iterations having -the general form: $\forall n\in \mathds{N}^{\ast }$, $ \forall i\in -\llbracket1;\mathsf{N}\rrbracket $, -\begin{equation} - x_i^n=\left\{ -\begin{array}{ll} - x_i^{n-1} & \text{ if } i \notin \mathcal{S}^n \\ - \left(f(x^{n-1})\right)_{S^n} & \text{ if }i \in \mathcal{S}^n. -\end{array}\right. -\label{general CIs} -\end{equation} +%%RAF proof en supplementary, j'ai mis le theorem. +% A vérifier -In other words, at the $n^{th}$ iteration, only the cells whose id is -contained into the set $S^{n}$ are iterated. + \subsection{Proofs of Chaos of the General Formulation of the Chaotic Iterations} +\label{deuxième def} +The proof is given in Section~\ref{A-deuxième def} of the annex document. +%% \label{deuxième def} +%% Let us consider the discrete dynamical systems in chaotic iterations having +%% the general form: $\forall n\in \mathds{N}^{\ast }$, $ \forall i\in +%% \llbracket1;\mathsf{N}\rrbracket $, -Let us now rewrite these general chaotic iterations as usual discrete dynamical -system of the form $X^{n+1}=f(X^n)$ on an ad hoc metric space. Such a formulation -is required in order to study the topological behavior of the system. +%% \begin{equation} +%% x_i^n=\left\{ +%% \begin{array}{ll} +%% x_i^{n-1} & \text{ if } i \notin \mathcal{S}^n \\ +%% \left(f(x^{n-1})\right)_{S^n} & \text{ if }i \in \mathcal{S}^n. +%% \end{array}\right. +%% \label{general CIs} +%% \end{equation} -Let us introduce the following function: -\begin{equation} -\begin{array}{cccc} - \chi: & \llbracket 1; \mathsf{N} \rrbracket \times \mathcal{P}\left(\llbracket 1; \mathsf{N} \rrbracket\right) & \longrightarrow & \mathds{B}\\ - & (i,X) & \longmapsto & \left\{ \begin{array}{ll} 0 & \textrm{if }i \notin X, \\ 1 & \textrm{if }i \in X, \end{array}\right. -\end{array} -\end{equation} -where $\mathcal{P}\left(X\right)$ is for the powerset of the set $X$, that is, $Y \in \mathcal{P}\left(X\right) \Longleftrightarrow Y \subset X$. +%% In other words, at the $n^{th}$ iteration, only the cells whose id is +%% contained into the set $S^{n}$ are iterated. -Given a function $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, define the function: -$F_{f}: \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} -\longrightarrow \mathds{B}^{\mathsf{N}}$ -\begin{equation*} -\begin{array}{rll} - (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+f(E)_{j}.\overline{\chi(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket}% -\end{array}% -\end{equation*}% -where + and . are the Boolean addition and product operations, and $\overline{x}$ -is the negation of the Boolean $x$. -Consider the phase space: -\begin{equation} -\mathcal{X} = \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N} \times -\mathds{B}^\mathsf{N}, -\end{equation} -\noindent and the map defined on $\mathcal{X}$: -\begin{equation} -G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), %\label{Gf} %%RAPH, j'ai viré ce label qui existe déjà avant... -\end{equation} -\noindent where $\sigma$ is the \emph{shift} function defined by $\sigma -(S^{n})_{n\in \mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow (S^{n+1})_{n\in -\mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}$ and $i$ is the \emph{initial function} -$i:(S^{n})_{n\in \mathds{N}} \in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow S^{0}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)$. -Then the general chaotic iterations defined in Equation \ref{general CIs} can -be described by the following discrete dynamical system: -\begin{equation} -\left\{ -\begin{array}{l} -X^0 \in \mathcal{X} \\ -X^{k+1}=G_{f}(X^k).% -\end{array}% -\right. -\end{equation}% +%% Let us now rewrite these general chaotic iterations as usual discrete dynamical +%% system of the form $X^{n+1}=f(X^n)$ on an ad hoc metric space. Such a formulation +%% is required in order to study the topological behavior of the system. -Once more, a shift function appears as a component of these general chaotic -iterations. - -To study the Devaney's chaos property, a distance between two points -$X = (S,E), Y = (\check{S},\check{E})$ of $\mathcal{X}$ must be defined. -Let us introduce: -\begin{equation} -d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}), -\label{nouveau d} -\end{equation} -\noindent where $ \displaystyle{d_{e}(E,\check{E})} = \displaystyle{\sum_{k=1}^{\mathsf{N}% - }\delta (E_{k},\check{E}_{k})}$ is once more the Hamming distance, and -$ \displaystyle{d_{s}(S,\check{S})} = \displaystyle{\dfrac{9}{\mathsf{N}}% - \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}$, -%%RAPH : ici, j'ai supprimé tous les sauts à la ligne +%% Let us introduce the following function: +%% \begin{equation} +%% \begin{array}{cccc} +%% \chi: & \llbracket 1; \mathsf{N} \rrbracket \times \mathcal{P}\left(\llbracket 1; \mathsf{N} \rrbracket\right) & \longrightarrow & \mathds{B}\\ +%% & (i,X) & \longmapsto & \left\{ \begin{array}{ll} 0 & \textrm{if }i \notin X, \\ 1 & \textrm{if }i \in X, \end{array}\right. +%% \end{array} +%% \end{equation} +%% where $\mathcal{P}\left(X\right)$ is for the powerset of the set $X$, that is, $Y \in \mathcal{P}\left(X\right) \Longleftrightarrow Y \subset X$. + +%% Given a function $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, define the function: +%% $F_{f}: \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} +%% \longrightarrow \mathds{B}^{\mathsf{N}}$ +%% \begin{equation*} +%% \begin{array}{rll} +%% (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+f(E)_{j}.\overline{\chi(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket}% +%% \end{array}% +%% \end{equation*}% +%% where + and . are the Boolean addition and product operations, and $\overline{x}$ +%% is the negation of the Boolean $x$. +%% Consider the phase space: +%% \begin{equation} +%% \mathcal{X} = \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N} \times +%% \mathds{B}^\mathsf{N}, +%% \end{equation} +%% \noindent and the map defined on $\mathcal{X}$: +%% \begin{equation} +%% G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), %\label{Gf} %%RAPH, j'ai viré ce label qui existe déjà avant... +%% \end{equation} +%% \noindent where $\sigma$ is the \emph{shift} function defined by $\sigma +%% (S^{n})_{n\in \mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow (S^{n+1})_{n\in +%% \mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}$ and $i$ is the \emph{initial function} +%% $i:(S^{n})_{n\in \mathds{N}} \in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow S^{0}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)$. +%% Then the general chaotic iterations defined in Equation \ref{general CIs} can +%% be described by the following discrete dynamical system: %% \begin{equation} %% \left\{ -%% \begin{array}{lll} -%% \displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}% -%% }\delta (E_{k},\check{E}_{k})} \textrm{ is once more the Hamming distance}, \\ -%% \displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}% -%% \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}.% +%% \begin{array}{l} +%% X^0 \in \mathcal{X} \\ +%% X^{k+1}=G_{f}(X^k).% %% \end{array}% %% \right. -%% \end{equation} -where $|X|$ is the cardinality of a set $X$ and $A\Delta B$ is for the symmetric difference, defined for sets A, B as -$A\,\Delta\,B = (A \setminus B) \cup (B \setminus A)$. - - -\begin{proposition} -The function $d$ defined in Eq.~\ref{nouveau d} is a metric on $\mathcal{X}$. -\end{proposition} - -\begin{proof} - $d_e$ is the Hamming distance. We will prove that $d_s$ is a distance -too, thus $d$, as being the sum of two distances, will also be a distance. - \begin{itemize} -\item Obviously, $d_s(S,\check{S})\geqslant 0$, and if $S=\check{S}$, then -$d_s(S,\check{S})=0$. Conversely, if $d_s(S,\check{S})=0$, then -$\forall k \in \mathds{N}, |S^k\Delta {S}^k|=0$, and so $\forall k, S^k=\check{S}^k$. - \item $d_s$ is symmetric -($d_s(S,\check{S})=d_s(\check{S},S)$) due to the commutative property -of the symmetric difference. -\item Finally, $|S \Delta S''| = |(S \Delta \varnothing) \Delta S''|= |S \Delta (S'\Delta S') \Delta S''|= |(S \Delta S') \Delta (S' \Delta S'')|\leqslant |S \Delta S'| + |S' \Delta S''|$, -and so for all subsets $S,S',$ and $S''$ of $\llbracket 1, \mathsf{N} \rrbracket$, -we have $d_s(S,S'') \leqslant d_e(S,S')+d_s(S',S'')$, and the triangle -inequality is obtained. - \end{itemize} -\end{proof} - - -Before being able to study the topological behavior of the general -chaotic iterations, we must first establish that: - -\begin{proposition} - 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} - - -\begin{proof} -We use the sequential continuity. -Let $(S^n,E^n)_{n\in \mathds{N}}$ be a sequence of the phase space $% -\mathcal{X}$, which converges to $(S,E)$. We will prove that $\left( -G_{f}(S^n,E^n)\right) _{n\in \mathds{N}}$ converges to $\left( -G_{f}(S,E)\right) $. Let us remark that for all $n$, $S^n$ is a strategy, -thus, we consider a sequence of strategies (\emph{i.e.}, a sequence of -sequences).\newline -As $d((S^n,E^n);(S,E))$ converges to 0, each distance $d_{e}(E^n,E)$ and $d_{s}(S^n,S)$ converges -to 0. But $d_{e}(E^n,E)$ is an integer, so $\exists n_{0}\in \mathds{N},$ $% -d_{e}(E^n,E)=0$ for any $n\geqslant n_{0}$.\newline -In other words, there exists a threshold $n_{0}\in \mathds{N}$ after which no -cell will change its state: -$\exists n_{0}\in \mathds{N},n\geqslant n_{0}\Rightarrow E^n = E.$ - -In addition, $d_{s}(S^n,S)\longrightarrow 0,$ so $\exists n_{1}\in % -\mathds{N},d_{s}(S^n,S)<10^{-1}$ for all indexes greater than or equal to $% -n_{1}$. This means that for $n\geqslant n_{1}$, all the $S^n$ have the same -first term, which is $S^0$: $\forall n\geqslant n_{1},S_0^n=S_0.$ - -Thus, after the $max(n_{0},n_{1})^{th}$ term, states of $E^n$ and $E$ are -identical and strategies $S^n$ and $S$ start with the same first term.\newline -Consequently, states of $G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are equal, -so, after the $max(n_0, n_1)^{th}$ term, the distance $d$ between these two points is strictly less than 1.\newline -\noindent We now prove that the distance between $\left( -G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is convergent to -0. Let $\varepsilon >0$. \medskip -\begin{itemize} -\item If $\varepsilon \geqslant 1$, we see that the distance -between $\left( G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is -strictly less than 1 after the $max(n_{0},n_{1})^{th}$ term (same state). -\medskip -\item If $\varepsilon <1$, then $\exists k\in \mathds{N},10^{-k}\geqslant -\varepsilon > 10^{-(k+1)}$. But $d_{s}(S^n,S)$ converges to 0, so -\begin{equation*} -\exists n_{2}\in \mathds{N},\forall n\geqslant -n_{2},d_{s}(S^n,S)<10^{-(k+2)}, -\end{equation*}% -thus after $n_{2}$, the $k+2$ first terms of $S^n$ and $S$ are equal. -\end{itemize} -\noindent As a consequence, the $k+1$ first entries of the strategies of $% -G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are the same ($G_{f}$ is a shift of strategies) and due to the definition of $d_{s}$, the floating part of -the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $% -10^{-(k+1)}\leqslant \varepsilon $. - -In conclusion, -%%RAPH : ici j'ai rajouté une ligne -%%TOF : ici j'ai rajouté un commentaire -%%TOF : ici aussi -$ -\forall \varepsilon >0,$ $\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N} -,$ $\forall n\geqslant N_{0},$ -$ d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right) -\leqslant \varepsilon . -$ -$G_{f}$ is consequently continuous. -\end{proof} - - -It is now possible to study the topological behavior of the general chaotic -iterations. We will prove that, - -\begin{theorem} -\label{t:chaos des general} - The general chaotic iterations defined on Equation~\ref{general CIs} satisfy -the Devaney's property of chaos. -\end{theorem} - -Let us firstly prove the following lemma. +%% \end{equation}% -\begin{lemma}[Strong transitivity] -\label{strongTrans} - For all couples $X,Y \in \mathcal{X}$ and any neighborhood $V$ of $X$, we can -find $n \in \mathds{N}^*$ and $X' \in V$ such that $G^n(X')=Y$. -\end{lemma} +%% Once more, a shift function appears as a component of these general chaotic +%% iterations. -\begin{proof} - Let $X=(S,E)$, $\varepsilon>0$, and $k_0 = \lfloor log_{10}(\varepsilon)+1 \rfloor$. -Any point $X'=(S',E')$ such that $E'=E$ and $\forall k \leqslant k_0, S'^k=S^k$, -are in the open ball $\mathcal{B}\left(X,\varepsilon\right)$. Let us define -$\check{X} = \left(\check{S},\check{E}\right)$, where $\check{X}= G^{k_0}(X)$. -We denote by $s\subset \llbracket 1; \mathsf{N} \rrbracket$ the set of coordinates -that are different between $\check{E}$ and the state of $Y$. Thus each point $X'$ of -the form $(S',E')$ where $E'=E$ and $S'$ starts with -$(S^0, S^1, \hdots, S^{k_0},s,\hdots)$, verifies the following properties: -\begin{itemize} - \item $X'$ is in $\mathcal{B}\left(X,\varepsilon\right)$, - \item the state of $G_f^{k_0+1}(X')$ is the state of $Y$. -\end{itemize} -Finally the point $\left(\left(S^0, S^1, \hdots, S^{k_0},s,s^0, s^1, \hdots\right); E\right)$, -where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties -claimed in the lemma. -\end{proof} - -We can now prove the Theorem~\ref{t:chaos des general}. - -\begin{proof}[Theorem~\ref{t:chaos des general}] -Firstly, strong transitivity implies transitivity. - -Let $(S,E) \in\mathcal{X}$ and $\varepsilon >0$. To -prove that $G_f$ is regular, it is sufficient to prove that -there exists a strategy $\tilde S$ such that the distance between -$(\tilde S,E)$ and $(S,E)$ is less than $\varepsilon$, and such that -$(\tilde S,E)$ is a periodic point. - -Let $t_1=\lfloor-\log_{10}(\varepsilon)\rfloor$, and let $E'$ be the -configuration that we obtain from $(S,E)$ after $t_1$ iterations of -$G_f$. As $G_f$ is strongly transitive, there exists a strategy $S'$ -and $t_2\in\mathds{N}$ such -that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$. - -Consider the strategy $\tilde S$ that alternates the first $t_1$ terms -of $S$ and the first $t_2$ terms of $S'$: -%%RAPH : j'ai coupé la ligne en 2 -$$\tilde -S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,$$$$\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It -is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after -$t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic -point. Since $\tilde S_t=S_t$ for $t0$. \medskip +%% \begin{itemize} +%% \item If $\varepsilon \geqslant 1$, we see that the distance +%% between $\left( G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is +%% strictly less than 1 after the $max(n_{0},n_{1})^{th}$ term (same state). +%% \medskip +%% \item If $\varepsilon <1$, then $\exists k\in \mathds{N},10^{-k}\geqslant +%% \varepsilon > 10^{-(k+1)}$. But $d_{s}(S^n,S)$ converges to 0, so +%% \begin{equation*} +%% \exists n_{2}\in \mathds{N},\forall n\geqslant +%% n_{2},d_{s}(S^n,S)<10^{-(k+2)}, +%% \end{equation*}% +%% thus after $n_{2}$, the $k+2$ first terms of $S^n$ and $S$ are equal. +%% \end{itemize} +%% \noindent As a consequence, the $k+1$ first entries of the strategies of $% +%% G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are the same ($G_{f}$ is a shift of strategies) and due to the definition of $d_{s}$, the floating part of +%% the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $% +%% 10^{-(k+1)}\leqslant \varepsilon $. + +%% In conclusion, +%% %%RAPH : ici j'ai rajouté une ligne +%% %%TOF : ici j'ai rajouté un commentaire +%% %%TOF : ici aussi +%% $ +%% \forall \varepsilon >0,$ $\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N} +%% ,$ $\forall n\geqslant N_{0},$ +%% $ d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right) +%% \leqslant \varepsilon . +%% $ +%% $G_{f}$ is consequently continuous. +%% \end{proof} + + +%% It is now possible to study the topological behavior of the general chaotic +%% iterations. We will prove that, + +%% \begin{theorem} +%% \label{t:chaos des general} +%% The general chaotic iterations defined on Equation~\ref{general CIs} satisfy +%% the Devaney's property of chaos. +%% \end{theorem} + +%% Let us firstly prove the following lemma. + +%% \begin{lemma}[Strong transitivity] +%% \label{strongTrans} +%% For all couples $X,Y \in \mathcal{X}$ and any neighborhood $V$ of $X$, we can +%% find $n \in \mathds{N}^*$ and $X' \in V$ such that $G^n(X')=Y$. +%% \end{lemma} + +%% \begin{proof} +%% Let $X=(S,E)$, $\varepsilon>0$, and $k_0 = \lfloor log_{10}(\varepsilon)+1 \rfloor$. +%% Any point $X'=(S',E')$ such that $E'=E$ and $\forall k \leqslant k_0, S'^k=S^k$, +%% are in the open ball $\mathcal{B}\left(X,\varepsilon\right)$. Let us define +%% $\check{X} = \left(\check{S},\check{E}\right)$, where $\check{X}= G^{k_0}(X)$. +%% We denote by $s\subset \llbracket 1; \mathsf{N} \rrbracket$ the set of coordinates +%% that are different between $\check{E}$ and the state of $Y$. Thus each point $X'$ of +%% the form $(S',E')$ where $E'=E$ and $S'$ starts with +%% $(S^0, S^1, \hdots, S^{k_0},s,\hdots)$, verifies the following properties: +%% \begin{itemize} +%% \item $X'$ is in $\mathcal{B}\left(X,\varepsilon\right)$, +%% \item the state of $G_f^{k_0+1}(X')$ is the state of $Y$. +%% \end{itemize} +%% Finally the point $\left(\left(S^0, S^1, \hdots, S^{k_0},s,s^0, s^1, \hdots\right); E\right)$, +%% where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties +%% claimed in the lemma. +%% \end{proof} + +%% We can now prove the Theorem~\ref{t:chaos des general}. + +%% \begin{proof}[Theorem~\ref{t:chaos des general}] +%% Firstly, strong transitivity implies transitivity. + +%% Let $(S,E) \in\mathcal{X}$ and $\varepsilon >0$. To +%% prove that $G_f$ is regular, it is sufficient to prove that +%% there exists a strategy $\tilde S$ such that the distance between +%% $(\tilde S,E)$ and $(S,E)$ is less than $\varepsilon$, and such that +%% $(\tilde S,E)$ is a periodic point. + +%% Let $t_1=\lfloor-\log_{10}(\varepsilon)\rfloor$, and let $E'$ be the +%% configuration that we obtain from $(S,E)$ after $t_1$ iterations of +%% $G_f$. As $G_f$ is strongly transitive, there exists a strategy $S'$ +%% and $t_2\in\mathds{N}$ such +%% that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$. + +%% Consider the strategy $\tilde S$ that alternates the first $t_1$ terms +%% of $S$ and the first $t_2$ terms of $S'$: +%% %%RAPH : j'ai coupé la ligne en 2 +%% $$\tilde +%% S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,$$$$\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It +%% is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after +%% $t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic +%% point. Since $\tilde S_t=S_t$ for $t0$ et $\liminf_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))=0$, meaning that their orbits always oscillate as the iterations pass. When a system is compact and contains an uncountable set of such points, it is claimed as chaotic according +%% to Li-Yorke~\cite{Li75,Ruette2001}. A similar property is regarded in the following NIST test~\cite{Nist10}. +%% \begin{itemize} +%% \item \textbf{Runs Test}. To determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence. In particular, this test determines whether the oscillation between such zeros and ones is too fast or too slow. +%% \end{itemize} +%% \item \textbf{Topological entropy}. The desire to formulate an equivalency of the thermodynamics entropy +%% has emerged both in the topological and statistical fields. Once again, a similar objective has led to two different +%% rewritting of an entropy based disorder: the famous Shannon definition of entropy is approximated in the statistical approach, +%% whereas topological entropy is defined as follows: +%% $x,y \in \mathcal{X}$ are $\varepsilon-$\emph{separated in time $n$} if there exists $k \leqslant n$ such that $d\left(f^{(k)}(x),f^{(k)}(y)\right)>\varepsilon$. Then $(n,\varepsilon)-$separated sets are sets of points that are all $\varepsilon-$separated in time $n$, which +%% leads to the definition of $s_n(\varepsilon,Y)$, being the maximal cardinality of all $(n,\varepsilon)-$separated sets. Using these notations, +%% the topological entropy is defined as follows: $$h_{top}(\mathcal{X},f) = \displaystyle{\lim_{\varepsilon \rightarrow 0} \Big[ \limsup_{n \rightarrow +\infty} \dfrac{1}{n} \log s_n(\varepsilon,\mathcal{X})\Big]}.$$ +%% This value measures the average exponential growth of the number of distinguishable orbit segments. +%% In this sense, it measures the complexity of the topological dynamical system, whereas +%% the Shannon approach comes to mind when defining the following test~\cite{Nist10}: +%% \begin{itemize} +%% \item \textbf{Approximate Entropy Test}. Compare the frequency of the overlapping blocks of two consecutive/adjacent lengths ($m$ and $m+1$) against the expected result for a random sequence. +%% \end{itemize} + +%% \item \textbf{Non-linearity, complexity}. Finally, let us remark that non-linearity and complexity are +%% not only sought in general to obtain chaos, but they are also required for randomness, as illustrated by the two tests below~\cite{Nist10}. +%% \begin{itemize} +%% \item \textbf{Binary Matrix Rank Test}. Check for linear dependence among fixed length substrings of the original sequence. +%% \item \textbf{Linear Complexity Test}. Determine whether or not the sequence is complex enough to be considered random. +%% \end{itemize} +%% \end{itemize} + + +%% We have proven in our previous works~\cite{guyeux12:bc} that chaotic iterations satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques} are, among other +%% things, strongly transitive, topologically mixing, chaotic as defined by Li and Yorke, +%% and that they have a topological entropy and an exponent of Lyapunov both equal to $ln(\mathsf{N})$, +%% where $\mathsf{N}$ is the size of the iterated vector. +%% These topological properties make that we are ground to believe that a generator based on chaotic +%% iterations will probably be able to pass all the existing statistical batteries for pseudorandomness like +%% the NIST one. The following subsections, in which we prove that defective generators have their +%% statistical properties improved by chaotic iterations, show that such an assumption is true. + +%% \subsection{Details of some Existing Generators} + +%% The list of defective PRNGs we will use +%% as inputs for the statistical tests to come is introduced here. + +%% Firstly, the simple linear congruency generators (LCGs) will be used. +%% They are defined by the following recurrence: +%% \begin{equation} +%% x^n = (ax^{n-1} + c)~mod~m, +%% \label{LCG} +%% \end{equation} +%% where $a$, $c$, and $x^0$ must be, among other things, non-negative and inferior to +%% $m$~\cite{LEcuyerS07}. In what follows, 2LCGs and 3LCGs refer to two (resp. three) +%% combinations of such LCGs. For further details, see~\cite{bfg12a:ip,combined_lcg}. +%% Secondly, the multiple recursive generators (MRGs) which will be used, +%% are based on a linear recurrence of order +%% $k$, modulo $m$~\cite{LEcuyerS07}: +%% \begin{equation} +%% x^n = (a^1x^{n-1}+~...~+a^kx^{n-k})~mod~m . +%% \label{MRG} +%% \end{equation} +%% The combination of two MRGs (referred as 2MRGs) is also used in these experiments. -Let us now explain why we have reasonable ground to believe that chaos -can improve statistical properties. -We will show in this section that chaotic properties as defined in the -mathematical theory of chaos are related to some statistical tests that can be found -in the NIST battery. Furthermore, we will check that, when mixing defective PRNGs with -chaotic iterations, the new generator presents better statistical properties -(this section summarizes and extends the work of~\cite{bfg12a:ip}). - - - -\subsection{Qualitative relations between topological properties and statistical tests} +%% Generators based on linear recurrences with carry will be regarded too. +%% This family of generators includes the add-with-carry (AWC) generator, based on the recurrence: +%% \begin{equation} +%% \label{AWC} +%% \begin{array}{l} +%% x^n = (x^{n-r} + x^{n-s} + c^{n-1})~mod~m, \\ +%% c^n= (x^{n-r} + x^{n-s} + c^{n-1}) / m, \end{array}\end{equation} +%% the SWB generator, having the recurrence: +%% \begin{equation} +%% \label{SWB} +%% \begin{array}{l} +%% x^n = (x^{n-r} - x^{n-s} - c^{n-1})~mod~m, \\ +%% c^n=\left\{ +%% \begin{array}{l} +%% 1 ~~~~~\text{if}~ (x^{i-r} - x^{i-s} - c^{i-1})<0\\ +%% 0 ~~~~~\text{else},\end{array} \right. \end{array}\end{equation} +%% and the SWC generator, which is based on the following recurrence: +%% \begin{equation} +%% \label{SWC} +%% \begin{array}{l} +%% x^n = (a^1x^{n-1} \oplus ~...~ \oplus a^rx^{n-r} \oplus c^{n-1}) ~ mod ~ 2^w, \\ +%% c^n = (a^1x^{n-1} \oplus ~...~ \oplus a^rx^{n-r} \oplus c^{n-1}) ~ / ~ 2^w. \end{array}\end{equation} +%% Then the generalized feedback shift register (GFSR) generator has been implemented, that is: +%% \begin{equation} +%% x^n = x^{n-r} \oplus x^{n-k} . +%% \label{GFSR} +%% \end{equation} -There are various relations between topological properties that describe an unpredictable behavior for a discrete -dynamical system on the one -hand, and statistical tests to check the randomness of a numerical sequence -on the other hand. These two mathematical disciplines follow a similar -objective in case of a recurrent sequence (to characterize an intrinsically complicated behavior for a -recurrent sequence), with two different but complementary approaches. -It is true that the following illustrative links give only qualitative arguments, -and proofs should be provided later to make such arguments irrefutable. However -they give a first understanding of the reason why we think that chaotic properties should tend -to improve the statistical quality of PRNGs. -% -Let us now list some of these relations between topological properties defined in the mathematical -theory of chaos and tests embedded into the NIST battery. %Such relations need to be further -%investigated, but they presently give a first illustration of a trend to search similar properties in the -%two following fields: mathematical chaos and statistics. +%% Finally, the nonlinear inversive (INV) generator~\cite{LEcuyerS07} has been studied, which is: -\begin{itemize} - \item \textbf{Regularity}. As stated in Section~\ref{subsec:Devaney}, a chaotic dynamical system must -have an element of regularity. Depending on the chosen definition of chaos, this element can be the existence of -a dense orbit, the density of periodic points, etc. The key idea is that a dynamical system with no periodicity -is not as chaotic as a system having periodic orbits: in the first situation, we can predict something and gain a -knowledge about the behavior of the system, that is, it never enters into a loop. A similar importance for periodicity is emphasized in -the two following NIST tests~\cite{Nist10}: - \begin{itemize} - \item \textbf{Non-overlapping Template Matching Test}. Detect generators that produce too many occurrences of a given non-periodic (aperiodic) pattern. - \item \textbf{Discrete Fourier Transform (Spectral) Test}. Detect periodic features (i.e., repetitive patterns that are close one to another) in the tested sequence that would indicate a deviation from the assumption of randomness. - \end{itemize} - -\item \textbf{Transitivity}. This topological property previously introduced states that the dynamical system is intrinsically complicated: it cannot be simplified into -two subsystems that do not interact, as we can find in any neighborhood of any point another point whose orbit visits the whole phase space. -This focus on the places visited by the orbits of the dynamical system takes various nonequivalent formulations in the mathematical theory -of chaos, namely: transitivity, strong transitivity, total transitivity, topological mixing, and so on~\cite{bg10:ij}. A similar attention -is brought on the states visited during a random walk in the two tests below~\cite{Nist10}: - \begin{itemize} - \item \textbf{Random Excursions Variant Test}. Detect deviations from the expected number of visits to various states in the random walk. - \item \textbf{Random Excursions Test}. Determine if the number of visits to a particular state within a cycle deviates from what one would expect for a random sequence. - \end{itemize} - -\item \textbf{Chaos according to Li and Yorke}. Two points of the phase space $(x,y)$ define a couple of Li-Yorke when $\limsup_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))>0$ et $\liminf_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))=0$, meaning that their orbits always oscillate as the iterations pass. When a system is compact and contains an uncountable set of such points, it is claimed as chaotic according -to Li-Yorke~\cite{Li75,Ruette2001}. A similar property is regarded in the following NIST test~\cite{Nist10}. - \begin{itemize} - \item \textbf{Runs Test}. To determine whether the number of runs of ones and zeros of various lengths is as expected for a random sequence. In particular, this test determines whether the oscillation between such zeros and ones is too fast or too slow. - \end{itemize} - \item \textbf{Topological entropy}. The desire to formulate an equivalency of the thermodynamics entropy -has emerged both in the topological and statistical fields. Once again, a similar objective has led to two different -rewritting of an entropy based disorder: the famous Shannon definition of entropy is approximated in the statistical approach, -whereas topological entropy is defined as follows: -$x,y \in \mathcal{X}$ are $\varepsilon-$\emph{separated in time $n$} if there exists $k \leqslant n$ such that $d\left(f^{(k)}(x),f^{(k)}(y)\right)>\varepsilon$. Then $(n,\varepsilon)-$separated sets are sets of points that are all $\varepsilon-$separated in time $n$, which -leads to the definition of $s_n(\varepsilon,Y)$, being the maximal cardinality of all $(n,\varepsilon)-$separated sets. Using these notations, -the topological entropy is defined as follows: $$h_{top}(\mathcal{X},f) = \displaystyle{\lim_{\varepsilon \rightarrow 0} \Big[ \limsup_{n \rightarrow +\infty} \dfrac{1}{n} \log s_n(\varepsilon,\mathcal{X})\Big]}.$$ -This value measures the average exponential growth of the number of distinguishable orbit segments. -In this sense, it measures the complexity of the topological dynamical system, whereas -the Shannon approach comes to mind when defining the following test~\cite{Nist10}: - \begin{itemize} -\item \textbf{Approximate Entropy Test}. Compare the frequency of the overlapping blocks of two consecutive/adjacent lengths ($m$ and $m+1$) against the expected result for a random sequence. - \end{itemize} - - \item \textbf{Non-linearity, complexity}. Finally, let us remark that non-linearity and complexity are -not only sought in general to obtain chaos, but they are also required for randomness, as illustrated by the two tests below~\cite{Nist10}. - \begin{itemize} -\item \textbf{Binary Matrix Rank Test}. Check for linear dependence among fixed length substrings of the original sequence. -\item \textbf{Linear Complexity Test}. Determine whether or not the sequence is complex enough to be considered random. - \end{itemize} -\end{itemize} +%% \begin{equation} +%% \label{INV} +%% \begin{array}{l} +%% x^n=\left\{ +%% \begin{array}{ll} +%% (a^1 + a^2 / z^{n-1})~mod~m & \text{if}~ z^{n-1} \neq 0 \\ +%% a^1 & \text{if}~ z^{n-1} = 0 .\end{array} \right. \end{array}\end{equation} -We have proven in our previous works~\cite{guyeux12:bc} that chaotic iterations satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques} are, among other -things, strongly transitive, topologically mixing, chaotic as defined by Li and Yorke, -and that they have a topological entropy and an exponent of Lyapunov both equal to $ln(\mathsf{N})$, -where $\mathsf{N}$ is the size of the iterated vector. -These topological properties make that we are ground to believe that a generator based on chaotic -iterations will probably be able to pass all the existing statistical batteries for pseudorandomness like -the NIST one. The following subsections, in which we prove that defective generators have their -statistical properties improved by chaotic iterations, show that such an assumption is true. -\subsection{Details of some Existing Generators} +%% \begin{table} +%% \renewcommand{\arraystretch}{1.3} +%% \caption{TestU01 Statistical Test Failures} +%% \label{TestU011} +%% \centering +%% \begin{tabular}{lccccc} +%% \toprule +%% Test name &Tests& Logistic & XORshift & ISAAC\\ +%% Rabbit & 38 &21 &14 &0 \\ +%% Alphabit & 17 &16 &9 &0 \\ +%% Pseudo DieHARD &126 &0 &2 &0 \\ +%% FIPS\_140\_2 &16 &0 &0 &0 \\ +%% SmallCrush &15 &4 &5 &0 \\ +%% Crush &144 &95 &57 &0 \\ +%% Big Crush &160 &125 &55 &0 \\ \hline +%% Failures & &261 &146 &0 \\ +%% \bottomrule +%% \end{tabular} +%% \end{table} -The list of defective PRNGs we will use -as inputs for the statistical tests to come is introduced here. -Firstly, the simple linear congruency generators (LCGs) will be used. -They are defined by the following recurrence: -\begin{equation} -x^n = (ax^{n-1} + c)~mod~m, -\label{LCG} -\end{equation} -where $a$, $c$, and $x^0$ must be, among other things, non-negative and inferior to -$m$~\cite{LEcuyerS07}. In what follows, 2LCGs and 3LCGs refer to two (resp. three) -combinations of such LCGs. For further details, see~\cite{bfg12a:ip,combined_lcg}. -Secondly, the multiple recursive generators (MRGs) which will be used, -are based on a linear recurrence of order -$k$, modulo $m$~\cite{LEcuyerS07}: -\begin{equation} -x^n = (a^1x^{n-1}+~...~+a^kx^{n-k})~mod~m . -\label{MRG} -\end{equation} -The combination of two MRGs (referred as 2MRGs) is also used in these experiments. +%% \begin{table} +%% \renewcommand{\arraystretch}{1.3} +%% \caption{TestU01 Statistical Test Failures for Old CI algorithms ($\mathsf{N}=4$)} +%% \label{TestU01 for Old CI} +%% \centering +%% \begin{tabular}{lcccc} +%% \toprule +%% \multirow{3}*{Test name} & \multicolumn{4}{c}{Old CI}\\ +%% &Logistic& XORshift& ISAAC&ISAAC \\ +%% &+& +& + & + \\ +%% &Logistic& XORshift& XORshift&ISAAC \\ \cmidrule(r){2-5} +%% Rabbit &7 &2 &0 &0 \\ +%% Alphabit & 3 &0 &0 &0 \\ +%% DieHARD &0 &0 &0 &0 \\ +%% FIPS\_140\_2 &0 &0 &0 &0 \\ +%% SmallCrush &2 &0 &0 &0 \\ +%% Crush &47 &4 &0 &0 \\ +%% Big Crush &79 &3 &0 &0 \\ \hline +%% Failures &138 &9 &0 &0 \\ +%% \bottomrule +%% \end{tabular} +%% \end{table} -Generators based on linear recurrences with carry will be regarded too. -This family of generators includes the add-with-carry (AWC) generator, based on the recurrence: -\begin{equation} -\label{AWC} -\begin{array}{l} -x^n = (x^{n-r} + x^{n-s} + c^{n-1})~mod~m, \\ -c^n= (x^{n-r} + x^{n-s} + c^{n-1}) / m, \end{array}\end{equation} -the SWB generator, having the recurrence: -\begin{equation} -\label{SWB} -\begin{array}{l} -x^n = (x^{n-r} - x^{n-s} - c^{n-1})~mod~m, \\ -c^n=\left\{ -\begin{array}{l} -1 ~~~~~\text{if}~ (x^{i-r} - x^{i-s} - c^{i-1})<0\\ -0 ~~~~~\text{else},\end{array} \right. \end{array}\end{equation} -and the SWC generator, which is based on the following recurrence: -\begin{equation} -\label{SWC} -\begin{array}{l} -x^n = (a^1x^{n-1} \oplus ~...~ \oplus a^rx^{n-r} \oplus c^{n-1}) ~ mod ~ 2^w, \\ -c^n = (a^1x^{n-1} \oplus ~...~ \oplus a^rx^{n-r} \oplus c^{n-1}) ~ / ~ 2^w. \end{array}\end{equation} -Then the generalized feedback shift register (GFSR) generator has been implemented, that is: -\begin{equation} -x^n = x^{n-r} \oplus x^{n-k} . -\label{GFSR} -\end{equation} -Finally, the nonlinear inversive (INV) generator~\cite{LEcuyerS07} has been studied, which is: -\begin{equation} -\label{INV} -\begin{array}{l} -x^n=\left\{ -\begin{array}{ll} -(a^1 + a^2 / z^{n-1})~mod~m & \text{if}~ z^{n-1} \neq 0 \\ -a^1 & \text{if}~ z^{n-1} = 0 .\end{array} \right. \end{array}\end{equation} - - - -\begin{table} -\renewcommand{\arraystretch}{1.3} -\caption{TestU01 Statistical Test Failures} -\label{TestU011} -\centering - \begin{tabular}{lccccc} - \toprule -Test name &Tests& Logistic & XORshift & ISAAC\\ -Rabbit & 38 &21 &14 &0 \\ -Alphabit & 17 &16 &9 &0 \\ -Pseudo DieHARD &126 &0 &2 &0 \\ -FIPS\_140\_2 &16 &0 &0 &0 \\ -SmallCrush &15 &4 &5 &0 \\ -Crush &144 &95 &57 &0 \\ -Big Crush &160 &125 &55 &0 \\ \hline -Failures & &261 &146 &0 \\ -\bottomrule - \end{tabular} -\end{table} - - - -\begin{table} -\renewcommand{\arraystretch}{1.3} -\caption{TestU01 Statistical Test Failures for Old CI algorithms ($\mathsf{N}=4$)} -\label{TestU01 for Old CI} -\centering - \begin{tabular}{lcccc} - \toprule -\multirow{3}*{Test name} & \multicolumn{4}{c}{Old CI}\\ -&Logistic& XORshift& ISAAC&ISAAC \\ -&+& +& + & + \\ -&Logistic& XORshift& XORshift&ISAAC \\ \cmidrule(r){2-5} -Rabbit &7 &2 &0 &0 \\ -Alphabit & 3 &0 &0 &0 \\ -DieHARD &0 &0 &0 &0 \\ -FIPS\_140\_2 &0 &0 &0 &0 \\ -SmallCrush &2 &0 &0 &0 \\ -Crush &47 &4 &0 &0 \\ -Big Crush &79 &3 &0 &0 \\ \hline -Failures &138 &9 &0 &0 \\ -\bottomrule - \end{tabular} -\end{table} - - - - - -\subsection{Statistical tests} -\label{Security analysis} - -Three batteries of tests are reputed and regularly used -to evaluate the statistical properties of newly designed pseudorandom -number generators. These batteries are named DieHard~\cite{Marsaglia1996}, -the NIST suite~\cite{ANDREW2008}, and the most stringent one called -TestU01~\cite{LEcuyerS07}, which encompasses the two other batteries. - - - -\label{Results and discussion} -\begin{table*} -\renewcommand{\arraystretch}{1.3} -\caption{NIST and DieHARD tests suite passing rates for PRNGs without CI} -\label{NIST and DieHARD tests suite passing rate the for PRNGs without CI} -\centering - \begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|} - \hline\hline -Types of PRNGs & \multicolumn{2}{c|}{Linear PRNGs} & \multicolumn{4}{c|}{Lagged PRNGs} & \multicolumn{1}{c|}{ICG PRNGs} & \multicolumn{3}{c|}{Mixed PRNGs}\\ \hline -\backslashbox{\textbf{$Tests$}} {\textbf{$PRNG$}} & LCG& MRG& AWC & SWB & SWC & GFSR & INV & LCG2& LCG3& MRG2 \\ \hline -NIST & 11/15 & 14/15 &\textbf{15/15} & \textbf{15/15} & 14/15 & 14/15 & 14/15 & 14/15& 14/15& 14/15 \\ \hline -DieHARD & 16/18 & 16/18 & 15/18 & 16/18 & \textbf{18/18} & 16/18 & 16/18 & 16/18& 16/18& 16/18\\ \hline -\end{tabular} -\end{table*} - -Table~\ref{NIST and DieHARD tests suite passing rate the for PRNGs without CI} shows the -results on the two first batteries recalled above, indicating that all the PRNGs presented -in the previous section -cannot pass all these tests. In other words, the statistical quality of these PRNGs cannot -fulfill the up-to-date standards presented previously. We have shown in~\cite{bfg12a:ip} that the use of chaotic -iterations can solve this issue. -%More precisely, to -%illustrate the effects of chaotic iterations on these defective PRNGs, experiments have been divided in three parts~\cite{bfg12a:ip}: -%\begin{enumerate} -% \item \textbf{Single CIPRNG}: The PRNGs involved in CI computing are of the same category. -% \item \textbf{Mixed CIPRNG}: Two different types of PRNGs are mixed during the chaotic iterations process. -% \item \textbf{Multiple CIPRNG}: The generator is obtained by repeating the composition of the iteration function as follows: $x^0\in \mathds{B}^{\mathsf{N}}$, and $\forall n\in \mathds{N}^{\ast },\forall i\in \llbracket1;\mathsf{N}\rrbracket, x_i^n=$ -%\begin{equation} -%\begin{array}{l} -%\left\{ -%\begin{array}{l} -%x_i^{n-1}~~~~~\text{if}~S^n\neq i \\ -%\forall j\in \llbracket1;\mathsf{m}\rrbracket,f^m(x^{n-1})_{S^{nm+j}}~\text{if}~S^{nm+j}=i.\end{array} \right. \end{array} -%\end{equation} -%$m$ is called the \emph{functional power}. -%\end{enumerate} -% -The obtained results are reproduced in Table -\ref{NIST and DieHARD tests suite passing rate the for single CIPRNGs}. -The scores written in boldface indicate that all the tests have been passed successfully, whereas an -asterisk ``*'' means that the considered passing rate has been improved. -The improvements are obvious for both the ``Old CI'' and the ``New CI'' generators. -Concerning the ``Xor CI PRNG'', the score is less spectacular. Because of a large speed improvement, the statistics - are not as good as for the two other versions of these CIPRNGs. -However 8 tests have been improved (with no deflation for the other results). - - -\begin{table*} -\renewcommand{\arraystretch}{1.3} -\caption{NIST and DieHARD tests suite passing rates for PRNGs with CI} -\label{NIST and DieHARD tests suite passing rate the for single CIPRNGs} -\centering - \begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|c|c|} - \hline -Types of PRNGs & \multicolumn{2}{c|}{Linear PRNGs} & \multicolumn{4}{c|}{Lagged PRNGs} & \multicolumn{1}{c|}{ICG PRNGs} & \multicolumn{3}{c|}{Mixed PRNGs}\\ \hline -\backslashbox{\textbf{$Tests$}} {\textbf{$Single~CIPRNG$}} & LCG & MRG & AWC & SWB & SWC & GFSR & INV& LCG2 & LCG3& MRG2 \\ \hline\hline -Old CIPRNG\\ \hline \hline -NIST & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} \\ \hline -DieHARD & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} * \\ \hline -New CIPRNG\\ \hline \hline -NIST & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} \\ \hline -DieHARD & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} *\\ \hline -Xor CIPRNG\\ \hline\hline -NIST & 14/15*& \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & 14/15 & \textbf{15/15} * & 14/15& \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} \\ \hline -DieHARD & 16/18 & 16/18 & 17/18* & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & 16/18 & 16/18 & 16/18& 16/18\\ \hline -\end{tabular} -\end{table*} - - -We have then investigated in~\cite{bfg12a:ip} if it were possible to improve -the statistical behavior of the Xor CI version by combining more than one -$\oplus$ operation. Results are summarized in Table~\ref{threshold}, illustrating -the progressive increasing effects of chaotic iterations, when giving time to chaos to get settled in. -Thus rapid and perfect PRNGs, regarding the NIST and DieHARD batteries, can be obtained -using chaotic iterations on defective generators. - -\begin{table*} -\renewcommand{\arraystretch}{1.3} -\caption{Number of $\oplus$ operations to pass the whole NIST and DieHARD batteries} -\label{threshold} -\centering - \begin{tabular}{|l||c|c|c|c|c|c|c|c|} - \hline -Inputted $PRNG$ & LCG & MRG & SWC & GFSR & INV& LCG2 & LCG3 & MRG2 \\ \hline\hline -Threshold value $m$& 19 & 7 & 2& 1 & 11& 9& 3& 4\\ \hline\hline -\end{tabular} -\end{table*} - -Finally, the TestU01 battery has been launched on three well-known generators -(a logistic map, a simple XORshift, and the cryptographically secure ISAAC, -see Table~\ref{TestU011}). These results can be compared with -Table~\ref{TestU01 for Old CI}, which gives the scores obtained by the -Old CI PRNG that has received these generators. -The obvious improvement speaks for itself, and together with the other -results recalled in this section, it reinforces the opinion that a strong -correlation between topological properties and statistical behavior exists. - - -The next subsection will now give a concrete original implementation of the Xor CI PRNG, the -fastest generator in the chaotic iteration based family. In the remainder, -this generator will be simply referred to as CIPRNG, or ``the proposed PRNG'', if this statement does not -raise ambiguity. +%% \subsection{Statistical tests} +%% \label{Security analysis} + +%% Three batteries of tests are reputed and regularly used +%% to evaluate the statistical properties of newly designed pseudorandom +%% number generators. These batteries are named DieHard~\cite{Marsaglia1996}, +%% the NIST suite~\cite{ANDREW2008}, and the most stringent one called +%% TestU01~\cite{LEcuyerS07}, which encompasses the two other batteries. + + + +%% \label{Results and discussion} +%% \begin{table*} +%% \renewcommand{\arraystretch}{1.3} +%% \caption{NIST and DieHARD tests suite passing rates for PRNGs without CI} +%% \label{NIST and DieHARD tests suite passing rate the for PRNGs without CI} +%% \centering +%% \begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|} +%% \hline\hline +%% Types of PRNGs & \multicolumn{2}{c|}{Linear PRNGs} & \multicolumn{4}{c|}{Lagged PRNGs} & \multicolumn{1}{c|}{ICG PRNGs} & \multicolumn{3}{c|}{Mixed PRNGs}\\ \hline +%% \backslashbox{\textbf{$Tests$}} {\textbf{$PRNG$}} & LCG& MRG& AWC & SWB & SWC & GFSR & INV & LCG2& LCG3& MRG2 \\ \hline +%% NIST & 11/15 & 14/15 &\textbf{15/15} & \textbf{15/15} & 14/15 & 14/15 & 14/15 & 14/15& 14/15& 14/15 \\ \hline +%% DieHARD & 16/18 & 16/18 & 15/18 & 16/18 & \textbf{18/18} & 16/18 & 16/18 & 16/18& 16/18& 16/18\\ \hline +%% \end{tabular} +%% \end{table*} + +%% Table~\ref{NIST and DieHARD tests suite passing rate the for PRNGs without CI} shows the +%% results on the two first batteries recalled above, indicating that all the PRNGs presented +%% in the previous section +%% cannot pass all these tests. In other words, the statistical quality of these PRNGs cannot +%% fulfill the up-to-date standards presented previously. We have shown in~\cite{bfg12a:ip} that the use of chaotic +%% iterations can solve this issue. +%% %More precisely, to +%% %illustrate the effects of chaotic iterations on these defective PRNGs, experiments have been divided in three parts~\cite{bfg12a:ip}: +%% %\begin{enumerate} +%% % \item \textbf{Single CIPRNG}: The PRNGs involved in CI computing are of the same category. +%% % \item \textbf{Mixed CIPRNG}: Two different types of PRNGs are mixed during the chaotic iterations process. +%% % \item \textbf{Multiple CIPRNG}: The generator is obtained by repeating the composition of the iteration function as follows: $x^0\in \mathds{B}^{\mathsf{N}}$, and $\forall n\in \mathds{N}^{\ast },\forall i\in \llbracket1;\mathsf{N}\rrbracket, x_i^n=$ +%% %\begin{equation} +%% %\begin{array}{l} +%% %\left\{ +%% %\begin{array}{l} +%% %x_i^{n-1}~~~~~\text{if}~S^n\neq i \\ +%% %\forall j\in \llbracket1;\mathsf{m}\rrbracket,f^m(x^{n-1})_{S^{nm+j}}~\text{if}~S^{nm+j}=i.\end{array} \right. \end{array} +%% %\end{equation} +%% %$m$ is called the \emph{functional power}. +%% %\end{enumerate} +%% % +%% The obtained results are reproduced in Table +%% \ref{NIST and DieHARD tests suite passing rate the for single CIPRNGs}. +%% The scores written in boldface indicate that all the tests have been passed successfully, whereas an +%% asterisk ``*'' means that the considered passing rate has been improved. +%% The improvements are obvious for both the ``Old CI'' and the ``New CI'' generators. +%% Concerning the ``Xor CI PRNG'', the score is less spectacular. Because of a large speed improvement, the statistics +%% are not as good as for the two other versions of these CIPRNGs. +%% However 8 tests have been improved (with no deflation for the other results). + + +%% \begin{table*} +%% \renewcommand{\arraystretch}{1.3} +%% \caption{NIST and DieHARD tests suite passing rates for PRNGs with CI} +%% \label{NIST and DieHARD tests suite passing rate the for single CIPRNGs} +%% \centering +%% \begin{tabular}{|l||c|c|c|c|c|c|c|c|c|c|c|c|} +%% \hline +%% Types of PRNGs & \multicolumn{2}{c|}{Linear PRNGs} & \multicolumn{4}{c|}{Lagged PRNGs} & \multicolumn{1}{c|}{ICG PRNGs} & \multicolumn{3}{c|}{Mixed PRNGs}\\ \hline +%% \backslashbox{\textbf{$Tests$}} {\textbf{$Single~CIPRNG$}} & LCG & MRG & AWC & SWB & SWC & GFSR & INV& LCG2 & LCG3& MRG2 \\ \hline\hline +%% Old CIPRNG\\ \hline \hline +%% NIST & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} \\ \hline +%% DieHARD & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} * \\ \hline +%% New CIPRNG\\ \hline \hline +%% NIST & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} * & \textbf{15/15} * & \textbf{15/15} \\ \hline +%% DieHARD & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} * & \textbf{18/18} *& \textbf{18/18} *\\ \hline +%% Xor CIPRNG\\ \hline\hline +%% NIST & 14/15*& \textbf{15/15} * & \textbf{15/15} & \textbf{15/15} & 14/15 & \textbf{15/15} * & 14/15& \textbf{15/15} * & \textbf{15/15} *& \textbf{15/15} \\ \hline +%% DieHARD & 16/18 & 16/18 & 17/18* & \textbf{18/18} * & \textbf{18/18} & \textbf{18/18} * & 16/18 & 16/18 & 16/18& 16/18\\ \hline +%% \end{tabular} +%% \end{table*} + + +%% We have then investigated in~\cite{bfg12a:ip} if it were possible to improve +%% the statistical behavior of the Xor CI version by combining more than one +%% $\oplus$ operation. Results are summarized in Table~\ref{threshold}, illustrating +%% the progressive increasing effects of chaotic iterations, when giving time to chaos to get settled in. +%% Thus rapid and perfect PRNGs, regarding the NIST and DieHARD batteries, can be obtained +%% using chaotic iterations on defective generators. + +%% \begin{table*} +%% \renewcommand{\arraystretch}{1.3} +%% \caption{Number of $\oplus$ operations to pass the whole NIST and DieHARD batteries} +%% \label{threshold} +%% \centering +%% \begin{tabular}{|l||c|c|c|c|c|c|c|c|} +%% \hline +%% Inputted $PRNG$ & LCG & MRG & SWC & GFSR & INV& LCG2 & LCG3 & MRG2 \\ \hline\hline +%% Threshold value $m$& 19 & 7 & 2& 1 & 11& 9& 3& 4\\ \hline\hline +%% \end{tabular} +%% \end{table*} + +%% Finally, the TestU01 battery has been launched on three well-known generators +%% (a logistic map, a simple XORshift, and the cryptographically secure ISAAC, +%% see Table~\ref{TestU011}). These results can be compared with +%% Table~\ref{TestU01 for Old CI}, which gives the scores obtained by the +%% Old CI PRNG that has received these generators. +%% The obvious improvement speaks for itself, and together with the other +%% results recalled in this section, it reinforces the opinion that a strong +%% correlation between topological properties and statistical behavior exists. + + +%% The next subsection will now give a concrete original implementation of the Xor CI PRNG, the +%% fastest generator in the chaotic iteration based family. In the remainder, +%% this generator will be simply referred to as CIPRNG, or ``the proposed PRNG'', if this statement does not +%% raise ambiguity. \subsection{First Efficient Implementation of a PRNG based on Chaotic Iterations} @@ -1743,92 +1760,95 @@ proving that $H$ is not secure, which is a contradiction. \subsection{Practical Security Evaluation} \label{sec:Practicak evaluation} - -Pseudorandom generators based on Eq.~\eqref{equation Oplus} are thus cryptographically secure when -they are XORed with an already cryptographically -secure PRNG. But, as stated previously, -such a property does not mean that, whatever the -key size, no attacker can predict the next bit -knowing all the previously released ones. -However, given a key size, it is possible to -measure in practice the minimum duration needed -for an attacker to break a cryptographically -secure PRNG, if we know the power of his/her -machines. Such a concrete security evaluation -is related to the $(T,\varepsilon)-$security -notion, which is recalled and evaluated in what -follows, for the sake of completeness. - -Let us firstly recall that, -\begin{definition} -Let $\mathcal{D} : \mathds{B}^M \longrightarrow \mathds{B}$ be a probabilistic algorithm that runs -in time $T$. -Let $\varepsilon > 0$. -$\mathcal{D}$ is called a $(T,\varepsilon)-$distinguishing attack on pseudorandom -generator $G$ if - -\begin{flushleft} -$\left| Pr[\mathcal{D}(G(k)) = 1 \mid k \in_R \{0,1\}^\ell ]\right.$ -\end{flushleft} - -\begin{flushright} -$ - \left. Pr[\mathcal{D}(s) = 1 \mid s \in_R \mathds{B}^M ]\right| \geqslant \varepsilon,$ -\end{flushright} - -\noindent where the probability is taken over the internal coin flips of $\mathcal{D}$, and the notation -``$\in_R$'' indicates the process of selecting an element at random and uniformly over the -corresponding set. -\end{definition} - -Let us recall that the running time of a probabilistic algorithm is defined to be the -maximum of the expected number of steps needed to produce an output, maximized -over all inputs; the expected number is averaged over all coin flips made by the algorithm~\cite{Knuth97}. -We are now able to define the notion of cryptographically secure PRNGs: - -\begin{definition} -A pseudorandom generator is $(T,\varepsilon)-$secure if there exists no $(T,\varepsilon)-$distinguishing attack on this pseudorandom generator. -\end{definition} - - - - - - - -Suppose now that the PRNG of Eq.~\eqref{equation Oplus} will work during -$M=100$ time units, and that during this period, -an attacker can realize $10^{12}$ clock cycles. -We thus wonder whether, during the PRNG's -lifetime, the attacker can distinguish this -sequence from a truly random one, with a probability -greater than $\varepsilon = 0.2$. -We consider that $N$ has 900 bits. - -Predicting the next generated bit knowing all the -previously released ones by Eq.~\eqref{equation Oplus} is obviously equivalent to predicting the -next bit in the BBS generator, which -is cryptographically secure. More precisely, it -is $(T,\varepsilon)-$secure: no -$(T,\varepsilon)-$distinguishing attack can be -successfully realized on this PRNG, if~\cite{Fischlin} -\begin{equation} -T \leqslant \dfrac{L(N)}{6 N (log_2(N))\varepsilon^{-2}M^2}-2^7 N \varepsilon^{-2} M^2 log_2 (8 N \varepsilon^{-1}M) -\label{mesureConcrete} -\end{equation} -where $M$ is the length of the output ($M=100$ in -our example), and $L(N)$ is equal to -$$ -2.8\times 10^{-3} exp \left(1.9229 \times (N ~ln~ 2)^\frac{1}{3} \times (ln(N~ln~ 2))^\frac{2}{3}\right) -$$ -is the number of clock cycles to factor a $N-$bit -integer. +This subsection is given in Section~\ref{A-sec:Practicak evaluation} of the annex document. +%%RAF mis en annexe + + +%% Pseudorandom generators based on Eq.~\eqref{equation Oplus} are thus cryptographically secure when +%% they are XORed with an already cryptographically +%% secure PRNG. But, as stated previously, +%% such a property does not mean that, whatever the +%% key size, no attacker can predict the next bit +%% knowing all the previously released ones. +%% However, given a key size, it is possible to +%% measure in practice the minimum duration needed +%% for an attacker to break a cryptographically +%% secure PRNG, if we know the power of his/her +%% machines. Such a concrete security evaluation +%% is related to the $(T,\varepsilon)-$security +%% notion, which is recalled and evaluated in what +%% follows, for the sake of completeness. + +%% Let us firstly recall that, +%% \begin{definition} +%% Let $\mathcal{D} : \mathds{B}^M \longrightarrow \mathds{B}$ be a probabilistic algorithm that runs +%% in time $T$. +%% Let $\varepsilon > 0$. +%% $\mathcal{D}$ is called a $(T,\varepsilon)-$distinguishing attack on pseudorandom +%% generator $G$ if + +%% \begin{flushleft} +%% $\left| Pr[\mathcal{D}(G(k)) = 1 \mid k \in_R \{0,1\}^\ell ]\right.$ +%% \end{flushleft} + +%% \begin{flushright} +%% $ - \left. Pr[\mathcal{D}(s) = 1 \mid s \in_R \mathds{B}^M ]\right| \geqslant \varepsilon,$ +%% \end{flushright} + +%% \noindent where the probability is taken over the internal coin flips of $\mathcal{D}$, and the notation +%% ``$\in_R$'' indicates the process of selecting an element at random and uniformly over the +%% corresponding set. +%% \end{definition} + +%% Let us recall that the running time of a probabilistic algorithm is defined to be the +%% maximum of the expected number of steps needed to produce an output, maximized +%% over all inputs; the expected number is averaged over all coin flips made by the algorithm~\cite{Knuth97}. +%% We are now able to define the notion of cryptographically secure PRNGs: + +%% \begin{definition} +%% A pseudorandom generator is $(T,\varepsilon)-$secure if there exists no $(T,\varepsilon)-$distinguishing attack on this pseudorandom generator. +%% \end{definition} + + + + + + + +%% Suppose now that the PRNG of Eq.~\eqref{equation Oplus} will work during +%% $M=100$ time units, and that during this period, +%% an attacker can realize $10^{12}$ clock cycles. +%% We thus wonder whether, during the PRNG's +%% lifetime, the attacker can distinguish this +%% sequence from a truly random one, with a probability +%% greater than $\varepsilon = 0.2$. +%% We consider that $N$ has 900 bits. + +%% Predicting the next generated bit knowing all the +%% previously released ones by Eq.~\eqref{equation Oplus} is obviously equivalent to predicting the +%% next bit in the BBS generator, which +%% is cryptographically secure. More precisely, it +%% is $(T,\varepsilon)-$secure: no +%% $(T,\varepsilon)-$distinguishing attack can be +%% successfully realized on this PRNG, if~\cite{Fischlin} +%% \begin{equation} +%% T \leqslant \dfrac{L(N)}{6 N (log_2(N))\varepsilon^{-2}M^2}-2^7 N \varepsilon^{-2} M^2 log_2 (8 N \varepsilon^{-1}M) +%% \label{mesureConcrete} +%% \end{equation} +%% where $M$ is the length of the output ($M=100$ in +%% our example), and $L(N)$ is equal to +%% $$ +%% 2.8\times 10^{-3} exp \left(1.9229 \times (N ~ln~ 2)^\frac{1}{3} \times (ln(N~ln~ 2))^\frac{2}{3}\right) +%% $$ +%% is the number of clock cycles to factor a $N-$bit +%% integer. -A direct numerical application shows that this attacker -cannot achieve its $(10^{12},0.2)$ distinguishing -attack in that context. +%% A direct numerical application shows that this attacker +%% cannot achieve its $(10^{12},0.2)$ distinguishing +%% attack in that context. diff --git a/supplementary.tex b/supplementary.tex index 2ab8f9c..012cfca 100644 --- a/supplementary.tex +++ b/supplementary.tex @@ -16,7 +16,6 @@ \usepackage{ctable} \usepackage{tabularx} \usepackage{multirow} - % Pour mathds : les ensembles IR, IN, etc. \usepackage{dsfont} @@ -26,6 +25,10 @@ \usepackage{graphicx} % Pour faire des sous-figures dans les figures \usepackage{subfigure} +\usepackage{xr-hyper} +\usepackage{hyperref} +\externaldocument{prng_gpu} +%\usepackage{hyperref} \newtheorem{notation}{Notation} @@ -39,7 +42,7 @@ -\title{Supplementary of ``Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom Numbers on GPU''} +\title{Annex document of ``Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom Numbers on GPU''} \begin{document} \author{Jacques M. Bahi, Rapha\"{e}l Couturier, Christophe @@ -52,6 +55,255 @@ Guyeux, and Pierre-Cyrille Héam\thanks{Authors in alphabetic order}} \IEEEpeerreviewmaketitle +\section{Proofs of Chaos of the General Formulation of the Chaotic Iterations} +\label{deuxième def} +Let us consider the discrete dynamical systems in chaotic iterations having +the general form: $\forall n\in \mathds{N}^{\ast }$, $ \forall i\in +\llbracket1;\mathsf{N}\rrbracket $, + +\begin{equation} + x_i^n=\left\{ +\begin{array}{ll} + x_i^{n-1} & \text{ if } i \notin \mathcal{S}^n \\ + \left(f(x^{n-1})\right)_{S^n} & \text{ if }i \in \mathcal{S}^n. +\end{array}\right. +\label{general CIs} +\end{equation} + +In other words, at the $n^{th}$ iteration, only the cells whose id is +contained into the set $S^{n}$ are iterated. + +Let us now rewrite these general chaotic iterations as usual discrete dynamical +system of the form $X^{n+1}=f(X^n)$ on an ad hoc metric space. Such a formulation +is required in order to study the topological behavior of the system. + +Let us introduce the following function: +\begin{equation} +\begin{array}{cccc} + \chi: & \llbracket 1; \mathsf{N} \rrbracket \times \mathcal{P}\left(\llbracket 1; \mathsf{N} \rrbracket\right) & \longrightarrow & \mathds{B}\\ + & (i,X) & \longmapsto & \left\{ \begin{array}{ll} 0 & \textrm{if }i \notin X, \\ 1 & \textrm{if }i \in X, \end{array}\right. +\end{array} +\end{equation} +where $\mathcal{P}\left(X\right)$ is for the powerset of the set $X$, that is, $Y \in \mathcal{P}\left(X\right) \Longleftrightarrow Y \subset X$. + +Given a function $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, define the function: +$F_{f}: \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} +\longrightarrow \mathds{B}^{\mathsf{N}}$ +\begin{equation*} +\begin{array}{rll} + (P,E) & \longmapsto & \left( E_{j}.\chi (j,P)+f(E)_{j}.\overline{\chi(j,P)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket}% +\end{array}% +\end{equation*}% +where + and . are the Boolean addition and product operations, and $\overline{x}$ +is the negation of the Boolean $x$. +Consider the phase space: +\begin{equation} +\mathcal{X} = \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N} \times +\mathds{B}^\mathsf{N}, +\end{equation} +\noindent and the map defined on $\mathcal{X}$: +\begin{equation} +G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), %\label{Gf} %%RAPH, j'ai viré ce label qui existe déjà avant... +\end{equation} +\noindent where $\sigma$ is the \emph{shift} function defined by $\sigma +(S^{n})_{n\in \mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow (S^{n+1})_{n\in +\mathds{N}}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}$ and $i$ is the \emph{initial function} +$i:(S^{n})_{n\in \mathds{N}} \in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)^\mathds{N}\longrightarrow S^{0}\in \mathcal{P}\left(\llbracket 1 ; \mathsf{N} \rrbracket\right)$. +Then the general chaotic iterations defined in Equation \ref{general CIs} can +be described by the following discrete dynamical system: +\begin{equation} +\left\{ +\begin{array}{l} +X^0 \in \mathcal{X} \\ +X^{k+1}=G_{f}(X^k).% +\end{array}% +\right. +\end{equation}% + +Once more, a shift function appears as a component of these general chaotic +iterations. + +To study the Devaney's chaos property, a distance between two points +$X = (S,E), Y = (\check{S},\check{E})$ of $\mathcal{X}$ must be defined. +Let us introduce: +\begin{equation} +d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S}), +\label{nouveau d} +\end{equation} +\noindent where $ \displaystyle{d_{e}(E,\check{E})} = \displaystyle{\sum_{k=1}^{\mathsf{N}% + }\delta (E_{k},\check{E}_{k})}$ is once more the Hamming distance, and +$ \displaystyle{d_{s}(S,\check{S})} = \displaystyle{\dfrac{9}{\mathsf{N}}% + \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}$, +%%RAPH : ici, j'ai supprimé tous les sauts à la ligne +%% \begin{equation} +%% \left\{ +%% \begin{array}{lll} +%% \displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}% +%% }\delta (E_{k},\check{E}_{k})} \textrm{ is once more the Hamming distance}, \\ +%% \displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}% +%% \sum_{k=1}^{\infty }\dfrac{|S^k\Delta {S}^k|}{10^{k}}}.% +%% \end{array}% +%% \right. +%% \end{equation} +where $|X|$ is the cardinality of a set $X$ and $A\Delta B$ is for the symmetric difference, defined for sets A, B as +$A\,\Delta\,B = (A \setminus B) \cup (B \setminus A)$. + + +\begin{proposition} +The function $d$ defined in Eq.~\ref{nouveau d} is a metric on $\mathcal{X}$. +\end{proposition} + +\begin{proof} + $d_e$ is the Hamming distance. We will prove that $d_s$ is a distance +too, thus $d$, as being the sum of two distances, will also be a distance. + \begin{itemize} +\item Obviously, $d_s(S,\check{S})\geqslant 0$, and if $S=\check{S}$, then +$d_s(S,\check{S})=0$. Conversely, if $d_s(S,\check{S})=0$, then +$\forall k \in \mathds{N}, |S^k\Delta {S}^k|=0$, and so $\forall k, S^k=\check{S}^k$. + \item $d_s$ is symmetric +($d_s(S,\check{S})=d_s(\check{S},S)$) due to the commutative property +of the symmetric difference. +\item Finally, $|S \Delta S''| = |(S \Delta \varnothing) \Delta S''|= |S \Delta (S'\Delta S') \Delta S''|= |(S \Delta S') \Delta (S' \Delta S'')|\leqslant |S \Delta S'| + |S' \Delta S''|$, +and so for all subsets $S,S',$ and $S''$ of $\llbracket 1, \mathsf{N} \rrbracket$, +we have $d_s(S,S'') \leqslant d_e(S,S')+d_s(S',S'')$, and the triangle +inequality is obtained. + \end{itemize} +\end{proof} + + +Before being able to study the topological behavior of the general +chaotic iterations, we must first establish that: + +\begin{proposition} + 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} + + +\begin{proof} +We use the sequential continuity. +Let $(S^n,E^n)_{n\in \mathds{N}}$ be a sequence of the phase space $% +\mathcal{X}$, which converges to $(S,E)$. We will prove that $\left( +G_{f}(S^n,E^n)\right) _{n\in \mathds{N}}$ converges to $\left( +G_{f}(S,E)\right) $. Let us remark that for all $n$, $S^n$ is a strategy, +thus, we consider a sequence of strategies (\emph{i.e.}, a sequence of +sequences).\newline +As $d((S^n,E^n);(S,E))$ converges to 0, each distance $d_{e}(E^n,E)$ and $d_{s}(S^n,S)$ converges +to 0. But $d_{e}(E^n,E)$ is an integer, so $\exists n_{0}\in \mathds{N},$ $% +d_{e}(E^n,E)=0$ for any $n\geqslant n_{0}$.\newline +In other words, there exists a threshold $n_{0}\in \mathds{N}$ after which no +cell will change its state: +$\exists n_{0}\in \mathds{N},n\geqslant n_{0}\Rightarrow E^n = E.$ + +In addition, $d_{s}(S^n,S)\longrightarrow 0,$ so $\exists n_{1}\in % +\mathds{N},d_{s}(S^n,S)<10^{-1}$ for all indexes greater than or equal to $% +n_{1}$. This means that for $n\geqslant n_{1}$, all the $S^n$ have the same +first term, which is $S^0$: $\forall n\geqslant n_{1},S_0^n=S_0.$ + +Thus, after the $max(n_{0},n_{1})^{th}$ term, states of $E^n$ and $E$ are +identical and strategies $S^n$ and $S$ start with the same first term.\newline +Consequently, states of $G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are equal, +so, after the $max(n_0, n_1)^{th}$ term, the distance $d$ between these two points is strictly less than 1.\newline +\noindent We now prove that the distance between $\left( +G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is convergent to +0. Let $\varepsilon >0$. \medskip +\begin{itemize} +\item If $\varepsilon \geqslant 1$, we see that the distance +between $\left( G_{f}(S^n,E^n)\right) $ and $\left( G_{f}(S,E)\right) $ is +strictly less than 1 after the $max(n_{0},n_{1})^{th}$ term (same state). +\medskip +\item If $\varepsilon <1$, then $\exists k\in \mathds{N},10^{-k}\geqslant +\varepsilon > 10^{-(k+1)}$. But $d_{s}(S^n,S)$ converges to 0, so +\begin{equation*} +\exists n_{2}\in \mathds{N},\forall n\geqslant +n_{2},d_{s}(S^n,S)<10^{-(k+2)}, +\end{equation*}% +thus after $n_{2}$, the $k+2$ first terms of $S^n$ and $S$ are equal. +\end{itemize} +\noindent As a consequence, the $k+1$ first entries of the strategies of $% +G_{f}(S^n,E^n)$ and $G_{f}(S,E)$ are the same ($G_{f}$ is a shift of strategies) and due to the definition of $d_{s}$, the floating part of +the distance between $(S^n,E^n)$ and $(S,E)$ is strictly less than $% +10^{-(k+1)}\leqslant \varepsilon $. + +In conclusion, +%%RAPH : ici j'ai rajouté une ligne +%%TOF : ici j'ai rajouté un commentaire +%%TOF : ici aussi +$ +\forall \varepsilon >0,$ $\exists N_{0}=max(n_{0},n_{1},n_{2})\in \mathds{N} +,$ $\forall n\geqslant N_{0},$ +$ d\left( G_{f}(S^n,E^n);G_{f}(S,E)\right) +\leqslant \varepsilon . +$ +$G_{f}$ is consequently continuous. +\end{proof} + + +It is now possible to study the topological behavior of the general chaotic +iterations. We will prove that, + +\begin{theorem} +\label{t:chaos des general} + The general chaotic iterations defined on Equation~\ref{general CIs} satisfy +the Devaney's property of chaos. +\end{theorem} + +Let us firstly prove the following lemma. + +\begin{lemma}[Strong transitivity] +\label{strongTrans} + For all couples $X,Y \in \mathcal{X}$ and any neighborhood $V$ of $X$, we can +find $n \in \mathds{N}^*$ and $X' \in V$ such that $G^n(X')=Y$. +\end{lemma} + +\begin{proof} + Let $X=(S,E)$, $\varepsilon>0$, and $k_0 = \lfloor log_{10}(\varepsilon)+1 \rfloor$. +Any point $X'=(S',E')$ such that $E'=E$ and $\forall k \leqslant k_0, S'^k=S^k$, +are in the open ball $\mathcal{B}\left(X,\varepsilon\right)$. Let us define +$\check{X} = \left(\check{S},\check{E}\right)$, where $\check{X}= G^{k_0}(X)$. +We denote by $s\subset \llbracket 1; \mathsf{N} \rrbracket$ the set of coordinates +that are different between $\check{E}$ and the state of $Y$. Thus each point $X'$ of +the form $(S',E')$ where $E'=E$ and $S'$ starts with +$(S^0, S^1, \hdots, S^{k_0},s,\hdots)$, verifies the following properties: +\begin{itemize} + \item $X'$ is in $\mathcal{B}\left(X,\varepsilon\right)$, + \item the state of $G_f^{k_0+1}(X')$ is the state of $Y$. +\end{itemize} +Finally the point $\left(\left(S^0, S^1, \hdots, S^{k_0},s,s^0, s^1, \hdots\right); E\right)$, +where $(s^0,s^1, \hdots)$ is the strategy of $Y$, satisfies the properties +claimed in the lemma. +\end{proof} + +We can now prove the Theorem~\ref{t:chaos des general}. + +\begin{proof}[Theorem~\ref{t:chaos des general}] +Firstly, strong transitivity implies transitivity. + +Let $(S,E) \in\mathcal{X}$ and $\varepsilon >0$. To +prove that $G_f$ is regular, it is sufficient to prove that +there exists a strategy $\tilde S$ such that the distance between +$(\tilde S,E)$ and $(S,E)$ is less than $\varepsilon$, and such that +$(\tilde S,E)$ is a periodic point. + +Let $t_1=\lfloor-\log_{10}(\varepsilon)\rfloor$, and let $E'$ be the +configuration that we obtain from $(S,E)$ after $t_1$ iterations of +$G_f$. As $G_f$ is strongly transitive, there exists a strategy $S'$ +and $t_2\in\mathds{N}$ such +that $E$ is reached from $(S',E')$ after $t_2$ iterations of $G_f$. + +Consider the strategy $\tilde S$ that alternates the first $t_1$ terms +of $S$ and the first $t_2$ terms of $S'$: +%%RAPH : j'ai coupé la ligne en 2 +$$\tilde +S=(S_0,\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,$$$$\dots,S_{t_1-1},S'_0,\dots,S'_{t_2-1},S_0,\dots).$$ It +is clear that $(\tilde S,E)$ is obtained from $(\tilde S,E)$ after +$t_1+t_2$ iterations of $G_f$. So $(\tilde S,E)$ is a periodic +point. Since $\tilde S_t=S_t$ for $t 0$. +$\mathcal{D}$ is called a $(T,\varepsilon)-$distinguishing attack on pseudorandom +generator $G$ if + +\begin{flushleft} +$\left| Pr[\mathcal{D}(G(k)) = 1 \mid k \in_R \{0,1\}^\ell ]\right.$ +\end{flushleft} + +\begin{flushright} +$ - \left. Pr[\mathcal{D}(s) = 1 \mid s \in_R \mathds{B}^M ]\right| \geqslant \varepsilon,$ +\end{flushright} + +\noindent where the probability is taken over the internal coin flips of $\mathcal{D}$, and the notation +``$\in_R$'' indicates the process of selecting an element at random and uniformly over the +corresponding set. +\end{definition} + +Let us recall that the running time of a probabilistic algorithm is defined to be the +maximum of the expected number of steps needed to produce an output, maximized +over all inputs; the expected number is averaged over all coin flips made by the algorithm~\cite{Knuth97}. +We are now able to define the notion of cryptographically secure PRNGs: + +\begin{definition} +A pseudorandom generator is $(T,\varepsilon)-$secure if there exists no $(T,\varepsilon)-$distinguishing attack on this pseudorandom generator. +\end{definition} + + + + + + + +Suppose now that the PRNG of Eq.~\eqref{equation Oplus} of the main document will work during +$M=100$ time units, and that during this period, +an attacker can realize $10^{12}$ clock cycles. +We thus wonder whether, during the PRNG's +lifetime, the attacker can distinguish this +sequence from a truly random one, with a probability +greater than $\varepsilon = 0.2$. +We consider that $N$ has 900 bits. + +Predicting the next generated bit knowing all the +previously released ones by Eq.~\eqref{equation Oplus} of the main document is obviously equivalent to predicting the +next bit in the BBS generator, which +is cryptographically secure. More precisely, it +is $(T,\varepsilon)-$secure: no +$(T,\varepsilon)-$distinguishing attack can be +successfully realized on this PRNG, if~\cite{Fischlin} +\begin{equation} +T \leqslant \dfrac{L(N)}{6 N (log_2(N))\varepsilon^{-2}M^2}-2^7 N \varepsilon^{-2} M^2 log_2 (8 N \varepsilon^{-1}M) +\label{mesureConcrete} +\end{equation} +where $M$ is the length of the output ($M=100$ in +our example), and $L(N)$ is equal to +$$ +2.8\times 10^{-3} exp \left(1.9229 \times (N ~ln~ 2)^\frac{1}{3} \times (ln(N~ln~ 2))^\frac{2}{3}\right) +$$ +is the number of clock cycles to factor a $N-$bit +integer. + + + + +A direct numerical application shows that this attacker +cannot achieve its $(10^{12},0.2)$ distinguishing +attack in that context. + + + + + \bibliographystyle{plain} \bibliography{mabase} -- 2.39.5