From e4f6e60e4d2af88e0e16f2d680cf4fe3725ea1fc Mon Sep 17 00:00:00 2001 From: couchot Date: Sat, 14 Mar 2015 11:51:43 +0100 Subject: [PATCH] reprise conclusion --- conclusion.tex | 67 +++++++++++++++++++++++++------------------------- 1 file changed, 33 insertions(+), 34 deletions(-) diff --git a/conclusion.tex b/conclusion.tex index 0b51092..fcf2bad 100644 --- a/conclusion.tex +++ b/conclusion.tex @@ -1,36 +1,35 @@ -% Dans cet article, nous avons montré qu'une fonction $G_f$ est chaotique si et -% seulement la fonction booléenne $f$ a un graphe d'itérations chaotiques -% fortement connexe. L'originalité majeure repose sur le type d'itérations -% considéré, qui n'est pas limité à la mise à jour d'un seul élément par -% itération, mais qui est étendu à la mise à jour simultanée de plusieurs éléments -% du système à chaque itération. De plus, il a été prouvé que la sortie d'une -% telle fonction suit une loi de distribution uniforme si et seulement si la -% chaîne de Markov induite peut se représenter à l'aide d'une matrice doublement -% stochastique. Enfin, un algorithme permettant d'engendrer des fonctions qui -% vérifient ces deux contraintes a été présenté et évalué. Ces fonctions ont été -% ensuite appliquées avec succès à la génération de nombres pseudo-aléatoires. -% Les expériences sur une batterie de tests éprouvée ont pu confirmer la -% pertinence de l'approche théorique. -% +This work has assumed a Boolean map $f$ which is embedded into +a discrete-time dynamical system $G_f$. +This one is supposed to be iterated a fixed number +$p_1$ or $p_2$,\ldots, or $p_{\mathds{p}}$ of +times before its output is considered. +This work has first shown that iterations of +$G_f$ are chaotic if and only if its iteration graph $\Gamma_{\mathcal{P}}(f)$ +is strongly connected where $\mathcal{P}$ is $\{p_1, \ldots, p_{\mathds{p}}\}$. +Any PRNG, which iterates $G_f$ as above +satisfies in some cases the property of chaos. -In this article, we have proven that the most general chaotic iterations based PRNG, which embeds -an iteration function, satisfies in some cases the property of chaos -as defined by Devaney. We then have shown how to generate such functions together -with the related number of iterations, leading to strongly connected -iteration graphs and thus to chaos for the associated pseudorandom number generators. -By removing some paths in the hypercube, we then have provided examples of such graphs -that lead to chaos, while linking these graphs to the PRNG problem under consideration. +We then have shown that a previously presented approach can be directly +applied here to generate function $f$ with strongly connected +$\Gamma_{\mathcal{P}}(f)$. +The iterated map inside the generator is built by first removing from a +$\mathsf{N}$-cube an Hamiltonian path and next +adding a self loop to each vertex. +The PRNG can thus be seen as a random walks of length in $\mathsf{P}$ +into $\mathsf{N}$ this new cube. +We furthermore have exhibit a bound on the number of iterations +that are sufficient to obtain a uniform distribution of the output. +Finally, experiments through the NIST battery have shown that +the statistical properties are almost established for +$\mathsf{N} = 4, 5, 6, 7, 8$. -In future work, we intend to understand the link between succeeded or failed statistical tests -and the properties of chaos for the associated asynchronous iterations. By doing so, -relations between desired statistically unbiased behaviors and topological properties will be -understood, leading to better choices in iteration functions. Conditions allowing the -reduction of the mixing time will be investigated too, while other modifications of the hypercube -will be regarded in order to enlarge the set of known chaotic and random asynchronous -iterations. - -% -%%% Local Variables: -%%% mode: latex -%%% TeX-master: "main" -%%% End: +In future work, we intend to understand the link between +statistical tests and the properties of chaos for +the associated iterations. +By doing so, relations between desired statistically unbiased behaviors and +topological properties will be understood, leading to better choices +in iteration functions. +Conditions allowing the reduction of the stopping-time will be +investigated too, while other modifications of the hypercube will +be regarded in order to enlarge the set of known chaotic +and random iterations. -- 2.39.5