From: Christophe Guyeux Date: Sat, 14 Mar 2015 08:01:03 +0000 (+0100) Subject: fin de la relecture de la première version de l'intro X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/rairo15.git/commitdiff_plain/07fc9a29ed26c33dfe987821fc94b3afa4cdd3a5 fin de la relecture de la première version de l'intro --- diff --git a/biblio.bib b/biblio.bib index 30bdba6..7faa670 100644 --- a/biblio.bib +++ b/biblio.bib @@ -17,6 +17,23 @@ OPTmonth = {}, } +@inproceedings{chgw14oip, +inhal = {no}, +domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO, INFO:INFO_SE}, +equipe = {ie}, +classement = {COM}, +author = {Couchot, Jean-Fran\c{c}ois and H\'eam, Pierre-Cyrille and Guyeux, Christophe and Wang, Qianxue and Bahi, Jacques}, +title = {Pseudorandom Number Generators with Balanced Gray Codes}, +booktitle = {Secrypt 2014, 11th Int. Conf. on Security and Cryptography}, +pages = {469--475}, +address = {Vienna, Austria}, +month = aug, +date = {28-30 aout}, +year = 2014, +note = {Position short paper}, + +} + @Misc{GridComp, OPTkey = {}, OPTauthor = {}, diff --git a/intro.tex b/intro.tex index dafa1cf..569c493 100644 --- a/intro.tex +++ b/intro.tex @@ -4,20 +4,20 @@ chosen due to their unpredictable character and their sensitiveness to initial c In most cases, these generators simply consist in iterating a chaotic function like the logistic map~\cite{915396,915385} or the Arnold's one~\cite{5376454}\ldots It thus remains to find optimal parameters in such functions so that attractors are -avoided, guaranteeing by doing so that generated numbers follow a uniform distribution. +avoided, hoping by doing so that the generated numbers follow a uniform distribution. In order to check the quality of the produced outputs, it is usual to test the PRNGs (Pseudo-Random Number Generators) with statistical batteries like -the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite{LEcuyerS07}. +the so-called DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10}, or TestU01~\cite{LEcuyerS07} ones. -In its general understanding, the chaos notion is often reduced to the strong +In its general understanding, chaos notion is often reduced to the strong sensitiveness to the initial conditions (the well known ``butterfly effect''): a continuous function $k$ defined on a metrical space is said -\emph{strongly sensitive to the initial conditions} if for all point -$x$ and all positive value $\epsilon$, it is possible to find another -point $y$, as close as possible to $x$, and an integer $t$ such that the distance +\emph{strongly sensitive to the initial conditions} if for each point +$x$ and each positive value $\epsilon$, it is possible to find another +point $y$ as close as possible to $x$, and an integer $t$ such that the distance between the $t$-th iterates of $x$ and $y$, denoted by $k^t(x)$ and $k^t(y)$, are larger than $\epsilon$. However, in his definition of chaos, Devaney~\cite{Devaney} -impose to the chaotic function two other properties called +imposes to the chaotic function two other properties called \emph{transitivity} and \emph{regularity}. Functions evoked above have been studied according to these properties, and they have been proven as chaotic on $\R$. But nothing guarantees that such properties are preserved when iterating the functions @@ -38,7 +38,7 @@ asynchronous iterations are strongly connected. We then have proven that it is n and sufficient that the Markov matrix associated to this graph is doubly stochastic, in order to have a uniform distribution of the outputs. We have finally established sufficient conditions to guarantee the first property of connectivity. Among the -generated functions, we thus considered for further investigations only the one that +generated functions, we thus have considered for further investigations only the one that satisfy the second property too. In~\cite{chgw14oip}, we have proposed an algorithmic method allowing to directly obtain a strongly connected iteration graph having a doubly stochastic Markov matrix. The research work presented here generalizes this latter article @@ -219,7 +219,7 @@ The remainder of this article is organized as follows. The next section is devot preliminaries, basic notations, and terminologies regarding asynchronous iterations. Then, in Section~\ref{sec:proofOfChaos}, Devaney's definition of chaos is recalled while the proofs of chaos of our most general PRNGs is provided. Section~\ref{sec:SCCfunc} shows how to generate functions and a number of iterations such that the iteration graph is strongly connected, making the -PRNG chaotic. The next section focus on examples of such graphs obtained by modifying the +PRNG chaotic. The next section focuses on examples of such graphs obtained by modifying the hypercube, while Section~\ref{sec:prng} establishes the link between the theoretical study and pseudorandom number generation. This research work ends by a conclusion section, where the contribution is summarized and