]> AND Private Git Repository - rairo15.git/blobdiff - conclusion.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
rétablissement stopping.tex suite à la remarque de PC
[rairo15.git] / conclusion.tex
index 0b510922821c0783e028224b1d6453bee171bbce..fcf2bad70df52595a399fd2c4c7e30b4d5fc3cb7 100644 (file)
@@ -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.