From: guyeux Date: Thu, 14 Jun 2012 08:21:16 +0000 (+0200) Subject: Plein de trucs X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/commitdiff_plain/0f430d9a654120c023030faedfd501aa3f6195e9 Plein de trucs --- diff --git a/prng_gpu.tex b/prng_gpu.tex index 90f00f8..ba76fe2 100644 --- a/prng_gpu.tex +++ b/prng_gpu.tex @@ -418,7 +418,7 @@ the metric space $(\mathcal{X},d)$. \end{proposition} The chaotic property of $G_f$ has been firstly established for the vectorial -Boolean negation $f(x_1,\hdots, x_\mathsf{N}) = (\overline{x_1},\hdots, \overline{x_\mathsf{N}})$ \cite{guyeux10}. To obtain a characterization, we have secondly +Boolean negation $f_0(x_1,\hdots, x_\mathsf{N}) = (\overline{x_1},\hdots, \overline{x_\mathsf{N}})$ \cite{guyeux10}. To obtain a characterization, we have secondly introduced the notion of asynchronous iteration graph recalled bellow. Let $f$ be a map from $\mathds{B}^\mathsf{N}$ to itself. The @@ -475,33 +475,58 @@ Let us finally remark that the vectorial negation satisfies the hypotheses of bo We have proposed in~\cite{bgw09:ip} a new family of generators that receives two PRNGs as inputs. These two generators are mixed with chaotic iterations, -leading thus to a new PRNG that improves the statistical properties of each -generator taken alone. Furthermore, our generator -possesses various chaos properties that none of the generators used as input +leading thus to a new PRNG that +\begin{color}{red} +should improves the statistical properties of each +generator taken alone. +Furthermore, the generator obtained by this way possesses various chaos properties that none of the generators used as input present. + \begin{algorithm}[h!] \begin{small} \KwIn{a function $f$, an iteration number $b$, an initial configuration $x^0$ ($n$ bits)} \KwOut{a configuration $x$ ($n$ bits)} $x\leftarrow x^0$\; -$k\leftarrow b + \textit{XORshift}(b)$\; +$k\leftarrow b + PRNG_1(b)$\; \For{$i=0,\dots,k$} { -$s\leftarrow{\textit{XORshift}(n)}$\; +$s\leftarrow{PRNG_2(n)}$\; $x\leftarrow{F_f(s,x)}$\; } return $x$\; \end{small} -\caption{PRNG with chaotic functions} +\caption{An arbitrary round of $Old~ CI~ PRNG_f(PRNG_1,PRNG_2)$} \label{CI Algorithm} \end{algorithm} +This generator is synthesized in Algorithm~\ref{CI Algorithm}. +It takes as input: a Boolean function $f$ satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques}; +an integer $b$, ensuring that the number of executed iterations +between two outputs is at least $b$ +and at most $2b+1$; and an initial configuration $x^0$. +It returns the new generated configuration $x$. Internally, it embeds two +inputted generators $PRNG_i(k), i=1,2$, + which must return integers +uniformly distributed +into $\llbracket 1 ; k \rrbracket$. +For instance, these PRNGs can be the \textit{XORshift}~\cite{Marsaglia2003}, +being a category of very fast PRNGs designed by George Marsaglia +that repeatedly uses the transform of exclusive or (XOR, $\oplus$) on a number +with a bit shifted version of it. Such a PRNG, which has a period of +$2^{32}-1=4.29\times10^9$, is summed up in Algorithm~\ref{XORshift}. +This XORshift, or any other reasonable PRNG, is used +in our own generator to compute both the number of iterations between two +outputs (provided by $PRNG_1$) and the strategy elements ($PRNG_2$). + +%This former generator has successively passed various batteries of statistical tests, as the NIST~\cite{bcgr11:ip}, DieHARD~\cite{Marsaglia1996}, and TestU01~\cite{LEcuyerS07} ones. + + \begin{algorithm}[h!] \begin{small} \KwIn{the internal configuration $z$ (a 32-bit word)} @@ -517,31 +542,95 @@ return $y$\; \end{algorithm} +\subsection{A ``New CI PRNG''} + +In order to make the Old CI PRNG usable in practice, we have proposed +an adapted version of the chaotic iteration based generator in~\cite{bg10:ip}. +In this ``New CI PRNG'', we prevent from changing twice a given +bit between two outputs. +This new generator is designed by the following process. + +First of all, some chaotic iterations have to be done to generate a sequence +$\left(x^n\right)_{n\in\mathds{N}} \in \left(\mathds{B}^{32}\right)^\mathds{N}$ +of Boolean vectors, which are the successive states of the iterated system. +Some of these vectors will be randomly extracted and our pseudo-random bit +flow will be constituted by their components. Such chaotic iterations are +realized as follows. Initial state $x^0 \in \mathds{B}^{32}$ is a Boolean +vector taken as a seed and chaotic strategy $\left(S^n\right)_{n\in\mathds{N}}\in +\llbracket 1, 32 \rrbracket^\mathds{N}$ is +an \emph{irregular decimation} of $PRNG_2$ sequence, as described in +Algorithm~\ref{Chaotic iteration1}. + +Then, at each iteration, only the $S^n$-th component of state $x^n$ is +updated, as follows: $x_i^n = x_i^{n-1}$ if $i \neq S^n$, else $x_i^n = \overline{x_i^{n-1}}$. +Such a procedure is equivalent to achieve chaotic iterations with +the Boolean vectorial negation $f_0$ and some well-chosen strategies. +Finally, some $x^n$ are selected +by a sequence $m^n$ as the pseudo-random bit sequence of our generator. +$(m^n)_{n \in \mathds{N}} \in \mathcal{M}^\mathds{N}$ is computed from $PRNG_1$, where $\mathcal{M}\subset \mathds{N}^*$ is a finite nonempty set of integers. +The basic design procedure of the New CI generator is summarized in Algorithm~\ref{Chaotic iteration1}. +The internal state is $x$, the output state is $r$. $a$ and $b$ are those computed by the two input +PRNGs. Lastly, the value $g(a)$ is an integer defined as in Eq.~\ref{Formula}. +This function is required to make the outputs uniform in $\llbracket 0, 2^\mathsf{N}-1 \rrbracket$ +(the reader is referred to~\cite{bg10:ip} for more information). +\begin{equation} +\label{Formula} +m^n = g(y^n)= +\left\{ +\begin{array}{l} +0 \text{ if }0 \leqslant{y^n}<{C^0_{32}},\\ +1 \text{ if }{C^0_{32}} \leqslant{y^n}<\sum_{i=0}^1{C^i_{32}},\\ +2 \text{ if }\sum_{i=0}^1{C^i_{32}} \leqslant{y^n}<\sum_{i=0}^2{C^i_{32}},\\ +\vdots~~~~~ ~~\vdots~~~ ~~~~\\ +N \text{ if }\sum_{i=0}^{N-1}{C^i_{32}}\leqslant{y^n}<1.\\ +\end{array} +\right. +\end{equation} -This generator is synthesized in Algorithm~\ref{CI Algorithm}. -It takes as input: a Boolean function $f$ satisfying Theorem~\ref{Th:Caractérisation des IC chaotiques}; -an integer $b$, ensuring that the number of executed iterations is at least $b$ -and at most $2b+1$; and an initial configuration $x^0$. -It returns the new generated configuration $x$. Internally, it embeds two -\textit{XORshift}$(k)$ PRNGs~\cite{Marsaglia2003} that return integers -uniformly distributed -into $\llbracket 1 ; k \rrbracket$. -\textit{XORshift} is a category of very fast PRNGs designed by George Marsaglia, -which repeatedly uses the transform of exclusive or (XOR, $\oplus$) on a number -with a bit shifted version of it. This PRNG, which has a period of -$2^{32}-1=4.29\times10^9$, is summed up in Algorithm~\ref{XORshift}. It is used -in our PRNG to compute the strategy length and the strategy elements. +\begin{algorithm} +\textbf{Input:} the internal state $x$ (32 bits)\\ +\textbf{Output:} a state $r$ of 32 bits +\begin{algorithmic}[1] +\FOR{$i=0,\dots,N$} +{ +\STATE$d_i\leftarrow{0}$\; +} +\ENDFOR +\STATE$a\leftarrow{PRNG_1()}$\; +\STATE$m\leftarrow{g(a)}$\; +\STATE$k\leftarrow{m}$\; +\WHILE{$i=0,\dots,k$} -This former generator has successively passed various batteries of statistical tests, as the NIST~\cite{bcgr11:ip}, DieHARD~\cite{Marsaglia1996}, and TestU01~\cite{LEcuyerS07} ones. +\STATE$b\leftarrow{PRNG_2()~mod~\mathsf{N}}$\; +\STATE$S\leftarrow{b}$\; + \IF{$d_S=0$} + { +\STATE $x_S\leftarrow{ \overline{x_S}}$\; +\STATE $d_S\leftarrow{1}$\; + + } + \ELSIF{$d_S=1$} + { +\STATE $k\leftarrow{ k+1}$\; + }\ENDIF +\ENDWHILE\\ +\STATE $r\leftarrow{x}$\; +\STATE return $r$\; +\medskip +\caption{An arbitrary round of the new CI generator} +\label{Chaotic iteration1} +\end{algorithmic} +\end{algorithm} +\end{color} \subsection{Improving the Speed of the Former Generator} -Instead of updating only one cell at each iteration, we can try to choose a -subset of components and to update them together. Such an attempt leads -to a kind of merger of the two sequences used in Algorithm -\ref{CI Algorithm}. When the updating function is the vectorial negation, +Instead of updating only one cell at each iteration,\begin{color}{red} we now propose to choose a +subset of components and to update them together, for speed improvements. Such a proposition leads\end{color} +to a kind of merger of the two sequences used in Algorithms +\ref{CI Algorithm} and \ref{Chaotic iteration1}. When the updating function is the vectorial negation, this algorithm can be rewritten as follows: \begin{equation} @@ -551,7 +640,7 @@ x^0 \in \llbracket 0, 2^\mathsf{N}-1 \rrbracket, S \in \llbracket 0, 2^\mathsf{N \forall n \in \mathds{N}^*, x^n = x^{n-1} \oplus S^n, \end{array} \right. -\label{equation Oplus} +\label{equation Oplus0} \end{equation} where $\oplus$ is for the bitwise exclusive or between two integers. This rewriting can be understood as follows. The $n-$th term $S^n$ of the @@ -561,7 +650,7 @@ as an integer having $\mathsf{N}$ bits too). More precisely, the $k-$th component of this state (a binary digit) changes if and only if the $k-$th digit in the binary decomposition of $S^n$ is 1. -The single basic component presented in Eq.~\ref{equation Oplus} is of +The single basic component presented in Eq.~\ref{equation Oplus0} is of ordinary use as a good elementary brick in various PRNGs. It corresponds to the following discrete dynamical system in chaotic iterations: @@ -582,8 +671,8 @@ than the ones presented in Definition \ref{Def:chaotic iterations} because, inst we select a subset of components to change. -Obviously, replacing Algorithm~\ref{CI Algorithm} by -Equation~\ref{equation Oplus}, which is possible when the iteration function is +Obviously, replacing the previous CI PRNG Algorithms by +Equation~\ref{equation Oplus0}, which is possible when the iteration function is the vectorial negation, leads to a speed improvement. However, proofs of chaos obtained in~\cite{bg10:ij} have been established only for chaotic iterations of the form presented in Definition @@ -838,134 +927,7 @@ have $d((S,E),(\tilde S,E))<\epsilon$. \begin{color}{red} -\section{Improving Statistical Properties Using Chaotic Iterations} - - -\subsection{The CIPRNG family} - -Three categories of PRNGs have been derived from chaotic iterations. They are -recalled in what follows. - -\subsubsection{Old CIPRNG} - -Let $\mathsf{N} = 4$. Some chaotic iterations are fulfilled to generate a sequence $\left(x^n\right)_{n\in\mathds{N}} \in \left(\mathds{B}^4\right)^\mathds{N}$ of Boolean vectors: the successive states of the iterated system. Some of these vectors are randomly extracted and their components constitute our pseudorandom bit flow~\cite{bgw09:ip}. -Chaotic iterations are realized as follows. Initial state $x^0 \in \mathds{B}^4$ is a Boolean vector taken as a seed and chaotic strategy $\left(S^n\right)_{n\in\mathds{N}}\in \llbracket 1, 4 \rrbracket^\mathds{N}$ is constructed with $PRNG_2$. Lastly, iterate function $f$ is the vectorial Boolean negation. -At each iteration, only the $S^n$-th component of state $x^n$ is updated. Finally, some $x^n$ are selected by a sequence $m^n$, provided by a second generator $PRNG_1$, as the pseudorandom bit sequence of our generator. - -The basic design procedure of the Old CI generator is summed up in Algorithm~\ref{Chaotic iteration}. -The internal state is $x$, the output array is $r$. $a$ and $b$ are those computed by $PRNG_1$ and $PRNG_2$. - - -\begin{algorithm} -\textbf{Input:} the internal state $x$ (an array of 4-bit words)\\ -\textbf{Output:} an array $r$ of 4-bit words -\begin{algorithmic}[1] - -\STATE$a\leftarrow{PRNG_1()}$; -\STATE$m\leftarrow{a~mod~2+13}$; -\WHILE{$i=0,\dots,m$} -\STATE$b\leftarrow{PRNG_2()}$; -\STATE$S\leftarrow{b~mod~4}$; -\STATE$x_S\leftarrow{ \overline{x_S}}$; -\ENDWHILE -\STATE$r\leftarrow{x}$; -\STATE return $r$; -\medskip -\caption{An arbitrary round of the old CI generator} -\label{Chaotic iteration} -\end{algorithmic} -\end{algorithm} - -\subsubsection{New CIPRNG} - -The New CI generator is designed by the following process~\cite{bg10:ip}. First of all, some chaotic iterations have to be done to generate a sequence $\left(x^n\right)_{n\in\mathds{N}} \in \left(\mathds{B}^{32}\right)^\mathds{N}$ of Boolean vectors, which are the successive states of the iterated system. Some of these vectors will be randomly extracted and our pseudo-random bit flow will be constituted by their components. Such chaotic iterations are realized as follows. Initial state $x^0 \in \mathds{B}^{32}$ is a Boolean vector taken as a seed and chaotic strategy $\left(S^n\right)_{n\in\mathds{N}}\in \llbracket 1, 32 \rrbracket^\mathds{N}$ is -an \emph{irregular decimation} of $PRNG_2$ sequence, as described in Algorithm~\ref{Chaotic iteration1}. - -Another time, at each iteration, only the $S^n$-th component of state $x^n$ is updated, as follows: $x_i^n = x_i^{n-1}$ if $i \neq S^n$, else $x_i^n = \overline{x_i^{n-1}}$. -Finally, some $x^n$ are selected -by a sequence $m^n$ as the pseudo-random bit sequence of our generator. -$(m^n)_{n \in \mathds{N}} \in \mathcal{M}^\mathds{N}$ is computed from $PRNG_1$, where $\mathcal{M}\subset \mathds{N}^*$ is a finite nonempty set of integers. - -The basic design procedure of the New CI generator is summarized in Algorithm~\ref{Chaotic iteration1}. -The internal state is $x$, the output state is $r$. $a$ and $b$ are those computed by the two input -PRNGs. Lastly, the value $g_1(a)$ is an integer defined as in Eq.~\ref{Formula}. - -\begin{equation} -\label{Formula} -m^n = g_1(y^n)= -\left\{ -\begin{array}{l} -0 \text{ if }0 \leqslant{y^n}<{C^0_{32}},\\ -1 \text{ if }{C^0_{32}} \leqslant{y^n}<\sum_{i=0}^1{C^i_{32}},\\ -2 \text{ if }\sum_{i=0}^1{C^i_{32}} \leqslant{y^n}<\sum_{i=0}^2{C^i_{32}},\\ -\vdots~~~~~ ~~\vdots~~~ ~~~~\\ -N \text{ if }\sum_{i=0}^{N-1}{C^i_{32}}\leqslant{y^n}<1.\\ -\end{array} -\right. -\end{equation} - -\begin{algorithm} -\textbf{Input:} the internal state $x$ (32 bits)\\ -\textbf{Output:} a state $r$ of 32 bits -\begin{algorithmic}[1] -\FOR{$i=0,\dots,N$} -{ -\STATE$d_i\leftarrow{0}$\; -} -\ENDFOR -\STATE$a\leftarrow{PRNG_1()}$\; -\STATE$m\leftarrow{f(a)}$\; -\STATE$k\leftarrow{m}$\; -\WHILE{$i=0,\dots,k$} - -\STATE$b\leftarrow{PRNG_2()~mod~\mathsf{N}}$\; -\STATE$S\leftarrow{b}$\; - \IF{$d_S=0$} - { -\STATE $x_S\leftarrow{ \overline{x_S}}$\; -\STATE $d_S\leftarrow{1}$\; - - } - \ELSIF{$d_S=1$} - { -\STATE $k\leftarrow{ k+1}$\; - }\ENDIF -\ENDWHILE\\ -\STATE $r\leftarrow{x}$\; -\STATE return $r$\; -\medskip -\caption{An arbitrary round of the new CI generator} -\label{Chaotic iteration1} -\end{algorithmic} -\end{algorithm} - - -\subsubsection{Xor CIPRNG} - -Instead of updating only one cell at each iteration as Old CI and New CI, we can try to choose a -subset of components and to update them together. Such an attempt leads -to a kind of merger of the two random sequences. When the updating function is the vectorial negation, -this algorithm can be rewritten as follows~\cite{arxivRCCGPCH}: - -\begin{equation} -\left\{ -\begin{array}{l} -x^0 \in \llbracket 0, 2^\mathsf{N}-1 \rrbracket, S \in \llbracket 0, 2^\mathsf{N}-1 \rrbracket^\mathds{N} \\ -\forall n \in \mathds{N}^*, x^n = x^{n-1} \oplus S^n, -\end{array} -\right. -\label{equation Oplus} -\end{equation} -%This rewriting can be understood as follows. The $n-$th term $S^n$ of the -%sequence $S$, which is an integer of $\mathsf{N}$ binary digits, presents -%the list of cells to update in the state $x^n$ of the system (represented -%as an integer having $\mathsf{N}$ bits too). More precisely, the $k-$th -%component of this state (a binary digit) changes if and only if the $k-$th -%digit in the binary decomposition of $S^n$ is 1. - -The single basic component presented in Eq.~\ref{equation Oplus} is of -ordinary use as a good elementary brick in various PRNGs. It corresponds -to the discrete dynamical system in chaotic iterations. +\section{Statistical Improvements Using Chaotic Iterations} \subsection{About some Well-known PRNGs} \label{The generation of pseudo-random sequence}