X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/8657185ec89ecf42d39c56a9a57ec20e61e20299..2e8e9b41154df43b7a17bb19733abea069a7f20e:/prng_gpu.tex diff --git a/prng_gpu.tex b/prng_gpu.tex index 5a3324b..5431409 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -129,13 +129,13 @@ Boolean \emph{state}. Having $\mathsf{N}$ Boolean values for these cells leads to the definition of a particular \emph{state of the system}. A sequence which elements belong to $\llbracket 1;\mathsf{N} \rrbracket $ is called a \emph{strategy}. The set of all strategies is -denoted by $\mathbb{S}.$ +denoted by $\llbracket 1, \mathsf{N} \rrbracket^\mathds{N}.$ \begin{definition} \label{Def:chaotic iterations} The set $\mathds{B}$ denoting $\{0,1\}$, let $f:\mathds{B}^{\mathsf{N}}\longrightarrow \mathds{B}^{\mathsf{N}}$ be -a function and $S\in \mathbb{S}$ be a strategy. The so-called +a function and $S\in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}$ be a strategy. The so-called \emph{chaotic iterations} are defined by $x^0\in \mathds{B}^{\mathsf{N}}$ and \begin{equation} @@ -182,9 +182,9 @@ Consider the phase space: G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), \label{Gf} \end{equation} \noindent where $\sigma$ is the \emph{shift} function defined by $\sigma -(S^{n})_{n\in \mathds{N}}\in \mathbb{S}\longrightarrow (S^{n+1})_{n\in -\mathds{N}}\in \mathbb{S}$ and $i$ is the \emph{initial function} -$i:(S^{n})_{n\in \mathds{N}} \in \mathbb{S}\longrightarrow S^{0}\in \llbracket +(S^{n})_{n\in \mathds{N}}\in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}\longrightarrow (S^{n+1})_{n\in +\mathds{N}}\in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}$ and $i$ is the \emph{initial function} +$i:(S^{n})_{n\in \mathds{N}} \in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}\longrightarrow S^{0}\in \llbracket 1;\mathsf{N}\rrbracket$. Then the chaotic iterations defined in (\ref{sec:chaotic iterations}) can be described by the following iterations: \begin{equation} @@ -233,7 +233,7 @@ components that are updated are the same too. \end{itemize} The distance presented above follows these recommendations. Indeed, if the floor value $\lfloor d(X,Y)\rfloor $ is equal to $n$, then the systems $E, \check{E}$ -differ in $n$ cells. In addition, $d(X,Y) - \lfloor d(X,Y) \rfloor $ is a +differ in $n$ cells ($d_e$ is indeed the Hamming distance). In addition, $d(X,Y) - \lfloor d(X,Y) \rfloor $ is a measure of the differences between strategies $S$ and $\check{S}$. More precisely, this floating part is less than $10^{-k}$ if and only if the first $k$ terms of the two strategies are equal. Moreover, if the $k^{th}$ digit is @@ -419,6 +419,7 @@ the general form: 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 @@ -431,7 +432,7 @@ is required in order to study the topological behavior of the system. Let us introduce the following function: \begin{equation} \begin{array}{cccc} - \delta: & \llbracket 1; \mathsf{N} \rrbracket \times \mathcal{P}\left(\llbracket 1; \mathsf{N} \rrbracket\right) & \longrightarrow & \mathds{B}\\ + \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} @@ -440,16 +441,17 @@ where $\mathcal{P}\left(X\right)$ is for the powerset of the set $X$, that is, $ Given a function $f:\mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N} $, define the function: \begin{equation} \begin{array}{lrll} -F_{f}: & \llbracket1;\mathsf{N}\rrbracket\times \mathds{B}^{\mathsf{N}} & +F_{f}: & \mathcal{P}\left(\llbracket1;\mathsf{N}\rrbracket \right) \times \mathds{B}^{\mathsf{N}} & \longrightarrow & \mathds{B}^{\mathsf{N}} \\ -& (k,E) & \longmapsto & \left( E_{j}.\delta (k,j)+f(E)_{k}.\overline{\delta -(k,j)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket},% +& (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}% -\noindent where + and . are the Boolean addition and product operations. +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} = \llbracket 1 ; \mathsf{N} \rrbracket^\mathds{N} \times +\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}$: @@ -457,11 +459,11 @@ Consider the phase space: G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), \label{Gf} \end{equation} \noindent where $\sigma$ is the \emph{shift} function defined by $\sigma -(S^{n})_{n\in \mathds{N}}\in \mathbb{S}\longrightarrow (S^{n+1})_{n\in -\mathds{N}}\in \mathbb{S}$ and $i$ is the \emph{initial function} -$i:(S^{n})_{n\in \mathds{N}} \in \mathbb{S}\longrightarrow S^{0}\in \llbracket -1;\mathsf{N}\rrbracket$. Then the chaotic iterations defined in -(\ref{sec:chaotic iterations}) can be described by the following iterations: +(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} @@ -471,28 +473,161 @@ X^{k+1}=G_{f}(X^k).% \right. \end{equation}% -With this formulation, a shift function appears as a component of chaotic -iterations. The shift function is a famous example of a chaotic -map~\cite{Devaney} but its presence is not sufficient enough to claim $G_f$ as -chaotic. +Another time, a shift function appears as a component of these general chaotic +iterations. -To study this claim, a new distance between two points $X = (S,E), Y = -(\check{S},\check{E})\in -\mathcal{X}$ has been introduced in \cite{guyeux10} as follows: +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 introduced. +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 \begin{equation} \left\{ \begin{array}{lll} \displaystyle{d_{e}(E,\check{E})} & = & \displaystyle{\sum_{k=1}^{\mathsf{N}% -}\delta (E_{k},\check{E}_{k})}, \\ +}\delta (E_{k},\check{E}_{k})}\textrm{ is another time the Hamming distance}, \\ \displaystyle{d_{s}(S,\check{S})} & = & \displaystyle{\dfrac{9}{\mathsf{N}}% -\sum_{k=1}^{\infty }\dfrac{|S^k-\check{S}^k|}{10^{k}}}.% +\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$ will be a distance as sum of two distances. + \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 firstly 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 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 $.\bigskip \newline +In conclusion, +$$ +\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}] + On the one hand, strong transitivity implies transitivity. On the other hand, +the regularity is exactly Lemma~\ref{strongTrans} with $Y=X$. As the sensitivity +to the initial condition is implied by these two properties, we thus have +the theorem. +\end{proof} + \section{Efficient PRNG based on Chaotic Iterations}