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

Private GIT Repository
reprise de l'intro
[rairo15.git] / conclusion.tex
index 59d8eff0f104ce0cacd71bdb683c8a84e6a11e17..fcf2bad70df52595a399fd2c4c7e30b4d5fc3cb7 100644 (file)
@@ -1,30 +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
-satisfy the property of chaos as defined by Devaney. We then have shown how to generate
-such functions together with the number of iterations, leading to strongly connected
-iteration graphs and thus to chaos for the associated pseudorandom number generators. 
+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$.
 
 
-% The next section focus 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
-% intended future work is outlined.
-% 
-%%% 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.