From: couturie Date: Mon, 25 Feb 2013 20:16:00 +0000 (+0100) Subject: new X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/book_gpu.git/commitdiff_plain/1ab765e98ab35b9396ce7f485d3e1121910ba320?ds=sidebyside new --- diff --git a/BookGPU/Chapters/chapter18/biblio.bib b/BookGPU/Chapters/chapter18/biblio.bib deleted file mode 100644 index 911369e..0000000 --- a/BookGPU/Chapters/chapter18/biblio.bib +++ /dev/null @@ -1,47 +0,0 @@ -@BOOK{devaney, - title = {An Introduction to Chaotic Dynamical Systems}, - publisher = {Addison-Wesley}, - year = {1989}, - author = {Devaney, R. L.}, - address = {Redwood City, CA}, - edition = {2nd} -} - -@ARTICLE{Marsaglia2003, - author = {G. Marsaglia}, - title = {Xorshift RNGs}, - journal = {Journal of Statistical Software}, - year = {2003}, - volume = {8(14)}, - pages = {1--6}, - timestamp = {2009.10.28} -} - -@Article{LEcuyerS07, - title = "Test{U01}: {A} {C} library for empirical testing of - random number generators", - author = "P. L'Ecuyer and R. J. Simard", - journal = "ACM Trans. Math. Softw", - year = "2007", - number = "4", - volume = "33", - bibdate = "2007-11-06", - bibsource = "DBLP, - http://dblp.uni-trier.de/db/journals/toms/toms33.html#LEcuyerS07", - URL = "http://doi.acm.org/10.1145/1268776.1268777", -} - -@manual{Nvid10, - author = {Nvidia}, - title = {Cuda cublas library}, - year = {2011}, - Note = {Version 4.0}, - } - -@InProceedings{Jenkins96, - author = "R. J. Jenkins", - title = "{ISAAC}", - booktitle = "IWFSE: International Workshop on Fast Software - Encryption, LNCS", - year = "1996", -} \ No newline at end of file diff --git a/BookGPU/Chapters/chapter18/biblio18.bib b/BookGPU/Chapters/chapter18/biblio18.bib new file mode 100644 index 0000000..2d0aed1 --- /dev/null +++ b/BookGPU/Chapters/chapter18/biblio18.bib @@ -0,0 +1,238 @@ +@BOOK{Devaney, + title = {An Introduction to Chaotic Dynamical Systems}, + publisher = {Addison-Wesley}, + year = {1989}, + author = {Devaney, R. L.}, + address = {Redwood City, CA}, + edition = {2nd} +} + +@ARTICLE{Marsaglia2003, + author = {Marsaglia, G.}, + title = {Xorshift RNGs}, + journal = {Journal of Statistical Software}, + year = {2003}, + volume = {8(14)}, + pages = {1--6}, + timestamp = {2009.10.28} +} + +@Article{LEcuyerS07, + title = "Test{U01}: {A} {C} library for empirical testing of + random number generators", + author = "L'Ecuyer, P. and Simard, R. J.", + journal = "ACM Trans. Math. Softw", + year = "2007", + number = "4", + volume = "33", + bibdate = "2007-11-06", + bibsource = "DBLP, + http://dblp.uni-trier.de/db/journals/toms/toms33.html#LEcuyerS07", + URL = "http://doi.acm.org/10.1145/1268776.1268777", +} + +@manual{Nvid10, + author = {Nvidia}, + title = {Cuda cublas library}, + year = {2011}, + Note = {Version 4.0}, + } + +@InProceedings{Jenkins96, + author = "Jenkins, R. J.", + title = "{ISAAC}", + booktitle = "IWFSE: International Workshop on Fast Software + Encryption, LNCS", + year = "1996", +} + + +@Book{Goldreich, + author = {Oded Goldreich}, + ALTeditor = {}, + title = {Foundations of Cryptography: Basic Tools}, + publisher = {Cambridge University Press}, + year = {2007}, +} + + +@book{kellert1994wake, + title={In the wake of chaos: unpredictable order in dynamical systems}, + author={Kellert, S.H.}, + isbn={9780226429762}, + lccn={lc92030355}, + series={Science and its conceptual foundations}, + url={http://books.google.fr/books?id=CUpcgo8DqR4C}, + year={1994}, + publisher={University of Chicago Press} +} + + + +@article{Wu20051195, +title = "Stochastic properties in Devaney's chaos", +journal = "Chaos, Solitons and Fractals", +volume = "23", +number = "4", +pages = "1195 - 1199", +year = "2005", +note = "", +issn = "0960-0779", +doi = "10.1016/j.chaos.2004.06.063", +url = "http://www.sciencedirect.com/science/article/pii/S0960077904003601", +author = "Wu, C. and Xu, Z. and Lin, W. and Ruan, J." +} + + +@book{gleick2011chaos, + title={Chaos: Making a New Science}, + author={Gleick, J.}, + isbn={9781453210475}, + url={http://books.google.fr/books?id=OoLNzl4XpPUC}, + year={2011}, + publisher={Open Road} +} + + + +@article{Werndl01032009, +author = {Werndl, C}, +title = {What Are the New Implications of Chaos for Unpredictability?}, +volume = {60}, +number = {1}, +pages = {195-220}, +year = {2009}, +doi = {10.1093/bjps/axn053}, +URL = {http://bjps.oxfordjournals.org/content/60/1/195.abstract}, +eprint = {http://bjps.oxfordjournals.org/content/60/1/195.full.pdf+html}, +journal = {The British Journal for the Philosophy of Science} +} + + +@article{bg10:ij, +inhal = {no}, +domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, +equipe = {and}, +classement = {ACLI}, +impact-factor ={#}, +isi-acro = {#}, +author = {Bahi, J. and Guyeux, C.}, +title = {Hash Functions Using Chaotic Iterations}, +journal = {Journal of Algorithms and Computational Technology}, +pages = {167--181}, +volume = 4, +number = 2, +doi = {10.1260/1748-3018.4.2.167}, +url = {http://dx.doi.org/10.1260/1748-3018.4.2.167}, +year = 2010, +} + + +@Article{ guyeux10, + author = "Bahi, J. and Guyeux, C.", + title = "Topological chaos and chaotic iterations, application to Hash functions", + booktitle = "WCCI'10, IEEE World Congress on Computational Intelligence", + year = "2010", + pages = "1--7", + address = "Barcelona, Spain", + month = jul, + publisher = "IEEE", + journal = "Neural Networks (IJCNN2010)", + equipe = "and", + inhal = "no", + owner = "christophe", + timestamp = "2010.04.11" +} + +@Book{ Robert1986, + title = "Discrete Iterations: A Metric Study", + year = "1986", + editor = "Springer-Verlag", + author = "Robert, F.", + volume = "6", + series = "Springer Series in Computational Mathematics", + owner = "guyeux", + timestamp = "17/02/2008" +} + + + +@PhDThesis{ GuyeuxThese10, + author = "Guyeux, C.", + title = "Le d{\'e}sordre des it{\'e}rations chaotiques et leur utilit{\'e} en s{\'e}curit{\'e} informatique", + school = "Universit{\'e} de Franche-Comt{\'e}", + year = "2010", + owner = "christophe", + timestamp = "2010.12.21" +} + + +@inproceedings{bgw09:ip, +inhal = {no}, +domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, +equipe = {and}, +classement = {ACTI}, +author = {Bahi, J and Guyeux, C. and Wang, Q.}, +title = {A novel pseudo-random generator based on discrete chaotic iterations}, +booktitle = {INTERNET'09, 1-st Int. Conf. on Evolving Internet}, +pages = {71--76}, +doi = {10.1109/INTERNET.2009.18}, +url = {http://dx.doi.org/10.1109/INTERNET.2009.18}, +address = {Cannes, France}, +month = aug, +year = 2009, +} + + +@article{bfgw11:ij, +inhal = {no}, +domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, +equipe = {and}, +classement = {ACLNI}, +impact-factor ={#}, +isi-acro = {#}, +author = {Bahi, J. and Fang, X. and Guyeux, C. and Wang, Q.}, +title = {Evaluating Quality of Chaotic Pseudo-Random Generators. Application to Information Hiding}, +journal = {IJAS, International Journal On Advances in Security}, +volume = 4, +number = {1-2}, +pages = {118--130}, +abstract = {Guaranteeing the security of information transmitted through the Internet, against passive or active attacks, is a major concern. The discovery of new pseudo-random number generators with a strong level of security is a field of research in full expansion, due to the fact that numerous cryptosystems and data hiding schemes are directly dependent on the quality of these generators. At the conference Internet`09, we described a generator based on chaotic iterations which behaves chaotically as defined by Devaney. In this paper which is an extension of the work presented at the conference Internet`10, the proposal is to improve the speed, the security, and the evaluation of this generator, to make its use more relevant in the Internet security context. In order to do so, a comparative study between various generators is carried out and statistical results are improved. Finally, an application in the information hiding framework is presented with details, to give an illustrative example of the use of such a generator in the Internet security field.}, +year = 2011, + +} + +@inproceedings{bgw10:ip, +inhal = {no}, +domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, +equipe = {and}, +classement = {ACTI}, +author = {Bahi, J. and Guyeux, C. and Wang, Q.}, +title = {A Pseudo Random Numbers Generator Based on Chaotic Iterations. Application to Watermarking}, +booktitle = {WISM 2010, Int. Conf. on Web Information Systems and Mining}, +pages = {202--211}, +series = {LNCS}, +volume = 6318, +url = {http://dx.doi.org/10.1007/978-3-642-16515-3_26}, +doi = {10.1007/978-3-642-16515-3_26}, +address = {Sanya, China}, +month = oct, +year = 2010, + +} + + +@inproceedings{bfg12a:ip, +inhal = {no}, +domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO}, +equipe = {and}, +classement = {ACTI}, +author = {Bahi, J. and Fang, X. and Guyeux, C.}, +title = {An optimization technique on pseudorandom generators based on chaotic iterations}, +booktitle = {INTERNET'2012, 4-th Int. Conf. on Evolving Internet}, +pages = {31--36}, +address = {Venice, Italy}, +month = jun, +year = 2012, + +} diff --git a/BookGPU/Chapters/chapter18/ch18.aux b/BookGPU/Chapters/chapter18/ch18.aux index d3e712f..558f1cb 100644 --- a/BookGPU/Chapters/chapter18/ch18.aux +++ b/BookGPU/Chapters/chapter18/ch18.aux @@ -2,42 +2,51 @@ \@writefile{toc}{\author{Rapha\IeC {\"e}l Couturier}{}} \@writefile{toc}{\author{Christophe Guyeux}{}} \@writefile{loa}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {chapter}{\numberline {16}Pseudo Random Number Generator on GPU}{359}} +\@writefile{toc}{\contentsline {chapter}{\numberline {16}Pseudorandom Number Generator on GPU}{359}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} \newlabel{chapter18}{{16}{359}} \@writefile{toc}{\contentsline {section}{\numberline {16.1}Introduction}{359}} -\@writefile{toc}{\contentsline {section}{\numberline {16.2}Basic Recalls}{360}} -\newlabel{section:BASIC RECALLS}{{16.2}{360}} -\@writefile{toc}{\contentsline {subsection}{\numberline {16.2.1}Devaney's Chaotic Dynamical Systems}{361}} -\@writefile{toc}{\contentsline {section}{\numberline {16.3}Toward Efficiency and Improvement for CI PRNG}{361}} -\newlabel{sec:efficient PRNG}{{16.3}{361}} -\@writefile{toc}{\contentsline {subsection}{\numberline {16.3.1}First Efficient Implementation of a PRNG based on Chaotic Iterations}{361}} -\newlabel{algo:seqCIPRNG}{{16.1}{361}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {16.1}C code of the sequential PRNG based on chaotic iterations}{361}} -\@writefile{toc}{\contentsline {subsection}{\numberline {16.3.2}Efficient PRNGs based on Chaotic Iterations on GPU}{361}} -\newlabel{sec:efficient PRNG gpu}{{16.3.2}{361}} -\@writefile{toc}{\contentsline {subsection}{\numberline {16.3.3}Naive Version for GPU}{362}} -\@writefile{loa}{\contentsline {algocf}{\numberline {16}{\ignorespaces Main kernel of the GPU ``naive'' version of the PRNG based on chaotic iterations\relax }}{362}} -\newlabel{algo:gpu_kernel}{{16}{362}} -\@writefile{toc}{\contentsline {subsection}{\numberline {16.3.4}Improved Version for GPU}{363}} -\@writefile{toc}{\contentsline {subsection}{\numberline {16.3.5}Chaos Evaluation of the Improved Version}{363}} -\newlabel{IR}{{17}{364}} -\@writefile{loa}{\contentsline {algocf}{\numberline {17}{\ignorespaces Main kernel for the chaotic iterations based PRNG GPU efficient version\relax }}{364}} -\newlabel{algo:gpu_kernel2}{{17}{364}} -\@writefile{toc}{\contentsline {section}{\numberline {16.4}Experiments}{364}} -\newlabel{sec:experiments}{{16.4}{364}} -\@writefile{lof}{\contentsline {figure}{\numberline {16.1}{\ignorespaces Quantity of pseudorandom numbers generated per second with the xorlike-based PRNG\relax }}{365}} -\newlabel{fig:time_xorlike_gpu}{{16.1}{365}} -\@writefile{lof}{\contentsline {figure}{\numberline {16.2}{\ignorespaces Quantity of pseudorandom numbers generated per second using the BBS-based PRNG\relax }}{366}} -\newlabel{fig:time_bbs_gpu}{{16.2}{366}} +\@writefile{toc}{\contentsline {section}{\numberline {16.2}Basic Recalls}{361}} +\newlabel{section:BASIC RECALLS}{{16.2}{361}} +\@writefile{toc}{\contentsline {subsection}{\numberline {16.2.1}A Short Presentation of Chaos}{361}} +\@writefile{toc}{\contentsline {subsection}{\numberline {16.2.2}On Devaney's Definition of Chaos}{361}} +\newlabel{sec:dev}{{16.2.2}{361}} +\newlabel{Devaney}{{16.1}{361}} +\@writefile{toc}{\contentsline {subsection}{\numberline {16.2.3}Chaotic iterations}{362}} +\newlabel{subsection:Chaotic iterations}{{16.2.3}{362}} +\newlabel{Chaotic iterations}{{2}{362}} +\newlabel{eq:generalIC}{{16.4}{363}} +\newlabel{equation Oplus}{{16.5}{363}} +\@writefile{toc}{\contentsline {section}{\numberline {16.3}Toward Efficiency and Improvement for CI PRNG}{363}} +\newlabel{sec:efficient PRNG}{{16.3}{363}} +\@writefile{toc}{\contentsline {subsection}{\numberline {16.3.1}First Efficient Implementation of a PRNG based on Chaotic Iterations}{363}} +\newlabel{algo:seqCIPRNG}{{16.1}{363}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {16.1}C code of the sequential PRNG based on chaotic iterations}{363}} +\@writefile{toc}{\contentsline {subsection}{\numberline {16.3.2}Efficient PRNGs based on Chaotic Iterations on GPU}{364}} +\newlabel{sec:efficient PRNG gpu}{{16.3.2}{364}} +\@writefile{toc}{\contentsline {subsection}{\numberline {16.3.3}Naive Version for GPU}{364}} +\@writefile{loa}{\contentsline {algocf}{\numberline {16}{\ignorespaces Main kernel of the GPU ``naive'' version of the PRNG based on chaotic iterations\relax }}{365}} +\newlabel{algo:gpu_kernel}{{16}{365}} +\@writefile{toc}{\contentsline {subsection}{\numberline {16.3.4}Improved Version for GPU}{365}} +\newlabel{IR}{{17}{366}} +\@writefile{loa}{\contentsline {algocf}{\numberline {17}{\ignorespaces Main kernel for the chaotic iterations based PRNG GPU efficient version\relax }}{366}} +\newlabel{algo:gpu_kernel2}{{17}{366}} +\@writefile{toc}{\contentsline {subsection}{\numberline {16.3.5}Chaos Evaluation of the Improved Version}{366}} +\@writefile{toc}{\contentsline {section}{\numberline {16.4}Experiments}{367}} +\newlabel{sec:experiments}{{16.4}{367}} +\@writefile{lof}{\contentsline {figure}{\numberline {16.1}{\ignorespaces Quantity of pseudorandom numbers generated per second with the xorlike-based PRNG\relax }}{368}} +\newlabel{fig:time_xorlike_gpu}{{16.1}{368}} +\@writefile{lof}{\contentsline {figure}{\numberline {16.2}{\ignorespaces Quantity of pseudorandom numbers generated per second using the BBS-based PRNG\relax }}{369}} +\newlabel{fig:time_bbs_gpu}{{16.2}{369}} +\@writefile{toc}{\contentsline {section}{Bibliography}{370}} \@setckpt{Chapters/chapter18/ch18}{ -\setcounter{page}{368} -\setcounter{equation}{0} +\setcounter{page}{372} +\setcounter{equation}{5} \setcounter{enumi}{2} \setcounter{enumii}{0} \setcounter{enumiii}{0} -\setcounter{enumiv}{22} +\setcounter{enumiv}{17} \setcounter{footnote}{2} \setcounter{mpfootnote}{0} \setcounter{part}{1} @@ -65,7 +74,7 @@ \setcounter{theorem}{0} \setcounter{exercise}{0} \setcounter{example}{0} -\setcounter{definition}{0} +\setcounter{definition}{2} \setcounter{proof}{1} \setcounter{lstlisting}{1} } diff --git a/BookGPU/Chapters/chapter18/ch18.tex b/BookGPU/Chapters/chapter18/ch18.tex index b4401c9..ed41c6e 100755 --- a/BookGPU/Chapters/chapter18/ch18.tex +++ b/BookGPU/Chapters/chapter18/ch18.tex @@ -1,8 +1,8 @@ -\chapterauthor{Raphaël Couturier}{Femto-ST Institute, University of Franche-Comte} -\chapterauthor{Christophe Guyeux}{Femto-ST Institute, University of Franche-Comte} +\chapterauthor{Raphaël Couturier}{Femto-ST Institute, University of Franche-Comt\'{e}} +\chapterauthor{Christophe Guyeux}{Femto-ST Institute, University of Franche-Comt\'{e}} -\chapter{Pseudo Random Number Generator on GPU} +\chapter{Pseudorandom Number Generator on GPU} \label{chapter18} \section{Introduction} @@ -10,7 +10,9 @@ Randomness is of importance in many fields such as scientific simulations or cryptography. ``Random numbers'' can mainly be generated either by a deterministic and reproducible algorithm called -a pseudorandom number generator (PRNG). In this paper, we focus on +a pseudorandom number generator (PRNG), or by a physical non-deterministic +process having all the characteristics of a random noise, called a truly random number +generator (TRNG). In this chapter, we focus on reproducible generators, useful for instance in Monte-Carlo based simulators. These domains need PRNGs that are statistically irreproachable. In some fields such as in numerical simulations, @@ -31,14 +33,14 @@ to make the distinction between numbers obtained with the secure generator and a true random sequence. Or, in an equivalent formulation, he or she should not be able (in practice) to predict the next bit of the generator, having the knowledge of all the binary -digits that have been already released. ``Being able in practice'' +digits that have been already released~\cite{Goldreich}. ``Being able in practice'' refers here to the possibility to achieve this attack in polynomial time, and to the exponential growth of the difficulty of this challenge when the size of the parameters of the PRNG increases. Finally, a small part of the community working in this domain focuses on a -third requirement, that is to define chaotic generators. +third requirement, that is to define chaotic generators~\cite{kellert1994wake, Wu20051195,gleick2011chaos}. The main idea is to take benefits from a chaotic dynamical system to obtain a generator that is unpredictable, disordered, sensible to its seed, or in other word chaotic. Their desire is to map a given chaotic dynamics into a sequence that seems random @@ -50,7 +52,15 @@ Furthermore, authors of such chaotic generators often claim their PRNG as secure due to their chaos properties, but there is no obvious relation between chaos and security as it is understood in cryptography. This is why the use of chaos for PRNG still remains marginal and disputable. -Let us finish this paragraph by noticing that, in this paper, +However, we have established in previous researches that these flaws can +be circumvented by using a tool called choatic iterations. +Such investigations have led to the definition of a new +family of PRNGs that are chaotic while being fast and statistically perfect, +or cryptographically secure~\cite{bgw09:ip,bgw10:ip,bfgw11:ij,bfg12a:ip}. This family is improved and adapted for GPU +architectures in this chapter. + + +Let us finish this introduction by noticing that, in this paper, statistical perfection refers to the ability to pass the whole {\it BigCrush} battery of tests, which is widely considered as the most stringent statistical evaluation of a sequence claimed as random. @@ -66,8 +76,13 @@ the same test. With this approach all our PRNGs pass the {\it Chaos, for its part, refers to the well-established definition of a chaotic dynamical system defined by Devaney~\cite{Devaney}. -The remainder of this paper is organized as follows. -A COMPLETER +The remainder of this chapter is organized as follows. +Basic definitions and terminologies about both topological chaos +and chaotic iterations are provided in the next section. Various +chaotic iterations based pseudorandom number generators are then +presented in Section~\ref{sec:efficient PRNG}. They encompass +naive and improved efficient generators for CPU and for GPU. +These generators are finally experimented in Section~\ref{sec:experiments}. \section{Basic Recalls} @@ -78,12 +93,117 @@ topological chaos and chaotic iterations. We assume the reader is familiar with basic notions on topology (see for instance~\cite{Devaney}). -\subsection{Devaney's Chaotic Dynamical Systems} +\subsection{A Short Presentation of Chaos} + + +Chaos theory studies the behavior of dynamical systems that are perfectly predictable, yet appear to be wildly amorphous and without meaningful. +Chaotic systems are highly sensitive to initial conditions, +which is popularly referred to as the butterfly effect. +In other words, small differences in initial conditions (such as those due to rounding errors in numerical computation) yield widely diverging outcomes, +rendering long-term prediction impossible in general \cite{kellert1994wake}. This happens even though these systems are deterministic, meaning that their future behavior is fully determined by their initial conditions, with no random elements involved \cite{kellert1994wake}. That is, the deterministic nature of these systems does not make them predictable \cite{kellert1994wake,Werndl01032009}. This behavior is known as deterministic chaos, or simply chaos. It has been well-studied in mathematics and +physics, leading among other things to the well-established definition of Devaney +recalled thereafter. + + + + + +\subsection{On Devaney's Definition of Chaos} +\label{sec:dev} +Consider a metric space $(\mathcal{X},d)$ and a continuous function $f:\mathcal{X}\longrightarrow \mathcal{X}$, for one-dimensional dynamical systems of the form: +\begin{equation} +x^0 \in \mathcal{X} \textrm{ and } \forall n \in \mathds{N}^*, x^n=f(x^{n-1}), +\label{Devaney} +\end{equation} +the following definition of chaotic behavior, formulated by Devaney~\cite{Devaney}, is widely accepted. + +\begin{definition} + A dynamical system of Form~(\ref{Devaney}) is said to be chaotic if the following conditions hold. +\begin{itemize} +\item Topological transitivity: + +\begin{equation} +\forall U,V \textrm{ open sets of } \mathcal{X},~\exists k>0, f^k(U) \cap V \neq \varnothing . +\end{equation} + +Intuitively, a topologically transitive map has points that eventually move under iteration from one arbitrarily small neighborhood to any other. Consequently, the dynamical system cannot be decomposed into two disjoint open sets that are invariant under the map. Note that if a map possesses a dense orbit, then it is clearly topologically transitive. +\item Density of periodic points in $\mathcal{X}$. + +Let $P=\{p\in \mathcal{X}|\exists n \in \mathds{N}^{\ast}:f^n(p)=p\}$ the set of periodic points of $f$. Then $P$ is dense in $\mathcal{X}$: + +\begin{equation} + \overline{P}=\mathcal{X} . +\end{equation} + +Density of periodic orbits means that every point in the space is approached arbitrarily closely by periodic orbits. Topologically mixing systems failing this condition may not display sensitivity to initial conditions presented below, and hence may not be chaotic. +\item Sensitive dependence on initial conditions: + +$\exists \varepsilon>0,$ $\forall x \in \mathcal{X},$ $\forall \delta >0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$ and $d\left(f^n(x),f^n(y)\right) \geqslant \varepsilon.$ + +Intuitively, a map possesses sensitive dependence on initial conditions if there exist points arbitrarily close to $x$ that eventually separate from $x$ by at least $\varepsilon$ under iteration of $f$. Not all points near $x$ need eventually separate from $x$ under iteration, but there must be at least one such point in every neighborhood of $x$. If a map possesses sensitive dependence on initial conditions, then for all practical purposes, the dynamics of the map defy numerical computation. Small errors in computation that are introduced by round-off may become magnified upon iteration. The results of numerical computation of an orbit, no matter how accurate, may bear no resemblance whatsoever with the real orbit. +\end{itemize} + +\end{definition} + +When $f$ is chaotic, then the system $(\mathcal{X}, f)$ is chaotic and quoting Devaney: ``it is unpredictable because of the sensitive dependence on initial conditions. It cannot be broken down or decomposed into two subsystems which do not interact because of topological transitivity. And, in the midst of this random behavior, we nevertheless have an element of regularity.'' Fundamentally different behaviors are consequently possible and occur in an unpredictable way. + + + + + + + + +\subsection{Chaotic iterations} +\label{subsection:Chaotic iterations} +Let us now introduce an example of a dynamical systems family that has +the potentiality to become chaotic, depending on the choice of the iteration +function. This family is the basis of the PRNGs we will +develop during this chapter. -A COMPLETER +\begin{definition} +\label{Chaotic iterations} +The set $\mathds{B}$ denoting $\{0,1\}$, let $f:\mathds{B}^{\mathsf{N}% +}\longrightarrow \mathds{B}^{\mathsf{N}}$ be an ``iteration'' function and $S$ be a +sequence of subsets of $\llbracket 1, \mathsf{N}\rrbracket$ called a chaotic strategy. Then, the so-called \emph{chaotic iterations} are defined by~\cite{Robert1986}: +\begin{equation} +\label{eq:generalIC} +\left\{\begin{array}{l} +x^0\in \mathds{B}^{\mathsf{N}}, \\ +\forall n\in \mathds{N}^{\ast },\forall i\in \llbracket1;\mathsf{N}\rrbracket% +,x_i^n= +\left\{ +\begin{array}{ll} +x_i^{n-1} & \text{if}~ i\notin S^n \\ +f(x^{n-1})_{i} & \text{if}~ i \in S^n. +\end{array} +\right. +\end{array} +\right. +\end{equation} +\end{definition} +In other words, at the $n^{th}$ iteration, only the cells of $S^{n}$ are +``iterated''. +Chaotic iterations generate a set of vectors; +they are defined by an initial state $x^{0}$, an iteration function $f$, and a chaotic strategy $S$~\cite{bg10:ij}. +These ``chaotic iterations'' can behave chaotically as defined by Devaney, +depending on the choice of $f$~\cite{bg10:ij}. For instance, +chaos is obtained when $f$ is the vectorial negation. +Note that, with this example of function, chaotic iterations +defined above can be rewritten as: +\begin{equation} +\label{equation Oplus} +x^0 \in \llbracket 0,2^\mathsf{N}-1\rrbracket,~\mathcal{S}^n \in \mathcal{P}\left(\llbracket 1,2^\mathsf{N}-1\rrbracket\right)^\mathds{N},~~ x^{n+1}=x^n \oplus \mathcal{S}^n, +\end{equation} +where $\mathcal{P}(X)$ stands for the set of subsets of $X$, whereas +$a\oplus b$ is the bitwise exclusive or operation between the binary +representation of the integers $a$ and $b$. Note that the term + $\mathcal{S}^n$ is directly and obviously linked to the $S^n$ of +Eq.\ref{eq:generalIC}. As recalled above, such an iterative sequence +satisfies the Devaney's definition of chaos. \section{Toward Efficiency and Improvement for CI PRNG} \label{sec:efficient PRNG} @@ -155,7 +275,8 @@ unsigned int CIPRNG() { In Listing~\ref{algo:seqCIPRNG} a sequential version of the proposed PRNG based -on chaotic iterations is presented. The xor operator is represented by +on chaotic iterations is presented, which extends the generator family +formerly presented in~\cite{bgw09:ip,guyeux10}. The xor operator is represented by \textasciicircum. This function uses three classical 64-bits PRNGs, namely the \texttt{xorshift}, the \texttt{xor128}, and the \texttt{xorwow}~\cite{Marsaglia2003}. In the following, we call them ``xor-like @@ -309,19 +430,20 @@ system of Eq.~\ref{eq:generalIC}. That is, an iteration of the general chaotic iterations is realized between the last stored value $x$ of the thread and a strategy $t$ (obtained by a bitwise exclusive or between a value provided by a xor-like() call and two values previously obtained by two other threads). -To be certain that we are in the framework of Theorem~\ref{t:chaos des general}, +To be certain that such iterations corresponds to the chaotic one recalled at the +end of the Section~\ref{sec:dev}, we must guarantee that this dynamical system iterates on the space -$\mathcal{X} = \mathcal{P}\left(\llbracket 1, \mathsf{N} \rrbracket\right)^\mathds{N}\times\mathds{B}^\mathsf{N}$. +$\mathcal{X} =\mathds{B}^\mathsf{N} \times \mathcal{P}\left(\llbracket 1, 2^\mathsf{N} \rrbracket\right)^\mathds{N}$. The left term $x$ obviously belongs to $\mathds{B}^ \mathsf{N}$. To prevent from any flaws of chaotic properties, we must check that the right term (the last $t$), corresponding to the strategies, can possibly be equal to any -integer of $\llbracket 1, \mathsf{N} \rrbracket$. +integer of $\llbracket 1, 2^\mathsf{N} \rrbracket$. Such a result is obvious, as for the xor-like(), all the integers belonging into its interval of definition can occur at each iteration, and thus the last $t$ respects the requirement. Furthermore, it is possible to -prove by an immediate mathematical induction that, as the initial $x$ -is uniformly distributed (it is provided by a cryptographically secure PRNG), +prove by an immediate mathematical induction that, supposes that the initial $x$ +is uniformly distributed, %(it is provided by a cryptographically secure PRNG), the two other stored values shmem[o1] and shmem[o2] are uniformly distributed too, (this is the induction hypothesis), and thus the next $x$ is finally uniformly distributed. @@ -402,5 +524,5 @@ as it is shown in the next sections. -\putbib[Chapters/chapter18/biblio] +\putbib[Chapters/chapter18/biblio18] diff --git a/BookGPU/Makefile b/BookGPU/Makefile index 3eefa39..cdc3c59 100644 --- a/BookGPU/Makefile +++ b/BookGPU/Makefile @@ -19,6 +19,7 @@ all: bibtex bu12 bibtex bu13 bibtex bu14 + bibtex bu15 makeindex ${BOOK}.idx pdflatex ${BOOK}