From 69e15f7dca156a0c19b96e7ecdb4732465630b7e Mon Sep 17 00:00:00 2001 From: qianxue Date: Thu, 22 Sep 2011 16:34:29 +0200 Subject: [PATCH] Add \section{Travaux en relation} --- Introduction.tex | 10 ++ Thesis.bib | 301 ++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 310 insertions(+), 1 deletion(-) diff --git a/Introduction.tex b/Introduction.tex index cd2341c..c8923b2 100644 --- a/Introduction.tex +++ b/Introduction.tex @@ -36,7 +36,17 @@ On montre qu’un PRNG est qualité par des preuves théoriques et validations e \section{Travaux en relation} +Random number generators (RNGs) are essential in statistical studies in several fields. They may be based on physical noise sources or on mathematical algorithms, but in both cases truly random numbers may not be obtained because of data acquisition +systems in the first case or because machine precision in the second case~\cite{Gonzalez2005281,Guler2011}. In spite of the fact that the existence (or not) of truly random number generators (RNG) remains an open question, the random number is replaced by value, pseudo-random numbers, provided by deterministic algorithms whose properties mimic those of a truly random sequence~\cite{DeMicco20083373,Knuth1998}. +Pseudo Random Number Generators (PRNGs) are widely used in science and technology, it is a critical component in modern cryptographic systems, communication systems, statistical simulation systems and any scientific area incorporating Monte Carlo methods~\cite{Vadim2011692,Marchi20093328,citeulike:867581,thecolourblue:1046} and many others. By the way, the Monte Carlo method appeared on the scientific scene in the late 1940s, for problems involving particle scattering in nuclear physics~\cite{Dyadkin1997258}. In the present era, there are few scientific fields that do not use random number. One of the most important applications of PRNGs is in cryptography to generate cryptographic keys, and to randomly initialize certain variables in cryptographic protocols. + +Moreover, the idea o f applying chaos theory to randomness has produced important works very recently ~\cite{james1995,Gonzalez1999109,Ergun2007235,Zhou20093442,Gonzalez2002259,Behnia20113455}. Chaos theory has been established since 1970s by many different research areas, such as physics, mathematics, engineering, and biology, etc. ~\cite{Hao1993}. Since 1990s, many researchers have noticed that there exists the close relationship between chaos and cryptography ~\cite{Brown1996,Fridrich98symmetricciphers}; many properties of chaotic systems have their corresponding counterparts in traditional cryptosystems. Chaotic systems have several significant features favorable to secure communications, such as ergodicity, sensitivity to initial condition, control parameters and random like behaviour, which can be connected with some +conventional cryptographic properties of good ciphers, such as confusion/diffusion. With all these advantages scientists +expected to introduce new and powerful tools of chaotic cryptography. Cryptography is the art of achieving security by +encoding messages to make them non-readable. Nowaday, some efficient techniques for encoding based on discrete time chaotic systems are presented in ~\cite{Djema2009,Belmouhoub2005}. A good random number generation improves the cryptographic security ~\cite{Behnia2008408}. + +Several test suites are readily available to researchers in academia and industry who wish to analyze their newly developed PRNG. Some general purpose test suites are Diehard by George Marsaglia ~\cite{Marsaglia1996}, the National Institute of Standards and Technology Statistical Test Suite ~\cite{ANDREW2008}, and Comparative test parameters~\cite{Menezes1997}. Systematic tests of pseudorandom number generators have received much attention. Finally, The TestU01 testsuite by L'Ecuyer and Simard ~\cite{Lecuyer2009} appears to define the current state of the art in the field. \section{Résume de nos contributions} Il a été étable dans ~\cite{guyeux09, guyeux10} que les itérations chaotiques (IC), un outil servant à l’obtention d’algorithmes itératifs rapide, satisfait la propriété de chaos topologique telle qu'elle a été définie par Devaney ~\cite{ Dev89}. Nous avons alors construit notre PRNG en combinant ces itérations chaotiques avec deux générateurs basés sur la suite de logistique~\cite{wang2009}. diff --git a/Thesis.bib b/Thesis.bib index 6020372..2a24078 100644 --- a/Thesis.bib +++ b/Thesis.bib @@ -7,7 +7,143 @@ year = "2008", crossref = "DBLP:conf/seta/2008", bibsource = "DBLP, http://dblp.uni-trier.de", - ee = "http://dx.doi.org/10.1007/978-3-540-85912-3\\\\\\\\_1" + ee = "http://dx.doi.org/10.1007/978-3-540-85912-3\\\\\\\\\\\_1" +} + +@Article{ Dyadkin1997258, + title = "A family of enhanced Lehmer random number generators, with hyperplane suppression, and direct support for certain physical applications", + journal = "Computer Physics Communications", + volume = "107", + number = "1-3", + pages = "258--280", + year = "1997", + note = "", + issn = "0010-4655", + doi = "10.1016/S0010-4655(97)00101-X", + url = "http://www.sciencedirect.com/science/article/pii/S001046559700101X", + author = "Iosif G. Dyadkin and Kenneth G. Hamilton", + keywords = "Monte Carlo", + keywords1 = "Random numbers", + keywords2 = "Random number generators", + keywords3 = "Pseudorandom", + keywords4 = "Klein-Nishina", + keywords5 = "Neutron scattering", + keywords6 = "Nuclear geophysics", + keywords7 = "Well logging", + keywords8 = "Petroleum exploration" +} + +@Electronic{ citeulike:867581, + abstract = "{Monte Carlo simulations are one of the major tools in statistical physics, complex system science, and other fields, and an increasing number of these simulations is run on distributed systems like clusters or grids. This raises the issue of generating random numbers in a parallel, distributed environment. In this contribution we demonstrate that multiple linear recurrences in finite fields are an ideal method to produce high quality pseudo-random numbers in sequential and parallel algorithms. Their known weakness (failure of sampling points in high dimensions) can be overcome by an appropriate delinearization that preserves all desirable properties of the underlying linear sequence.}", + archivePrefix = "arXiv", + author = "Heiko Bauke and Stephan Mertens", + citeulike-article-id = "867581", + citeulike-linkout-0 = "http://arxiv.org/abs/cond-mat/0609584", + citeulike-linkout-1 = "http://arxiv.org/pdf/cond-mat/0609584", + day = "22", + eprint = "cond-mat/0609584", + keywords = "distributed, monte-carlo, random, simulation", + month = sep, + posted-at = "2006-09-26 18:51:08", + priority = "2", + title = "{Random Numbers for Large Scale Distributed Monte Carlo Simulation}", + url = "http://arxiv.org/abs/cond-mat/0609584", + year = "2006" +} + +@Article{ thecolourblue:1046, + abstract = "{The Wolff algorithm is now accepted as the best cluster-flipping Monte Carlo algorithm for beating ''critical slowing down.'' We show how this method can yield incorrect answers due to subtle correlations in ''high quality'' random number generators.}", + author = "A. M. Ferrenberg and D. P. Landau and Y. J. Wong", + doi = "10.1103/PhysRevLett.69.3382", + issn = "1079-7114", + journal = "Physical Review Letters", + number = "23", + pages = "3382+", + title = "{Monte Carlo simulations: Hidden errors from ``good'' random number generators}", + url = "http://link.aps.org/abstract/PRL/v69/p3382", + volume = "69", + year = "1992", + citeulike-article-id = "7197366", + citeulike-linkout-0 = "http://dx.doi.org/10.1103/PhysRevLett.69.3382", + citeulike-linkout-1 = "http://link.aps.org/abstract/PRL/v69/p3382", + comment = "Copyright (C) 2008 The American Physical Society; Please report any problems to prola@aps.org", + pdf = "file://localhost/Users/aonghus/Documents/Papers/1992/Ferrenberg/Physical\%20Review\%20Letters\%201992\%20Ferrenberg.pdf", + posted-at = "2010-05-19 12:25:19", + priority = "0" +} + +@Article{ Gonzalez1999109, + title = "A random number generator based on unpredictable chaotic functions", + journal = "Computer Physics Communications", + volume = "120", + number = "2-3", + pages = "109--114", + year = "1999", + note = "", + issn = "0010-4655", + doi = "10.1016/S0010-4655(99)00233-7", + url = "http://www.sciencedirect.com/science/article/pii/S0010465599002337", + author = "Jorge A. Gonzalez and Ramiro Pino", + keywords = "05.45.+b", + keywords1 = "02.50.+s", + keywords2 = "05.40.+j", + keywords3 = "Chaos", + keywords4 = "Exact solutions", + keywords5 = "Stochastic processes", + keywords6 = "Random number generator" +} + +@Article{ Marchi20093328, + title = "Polynomial pseudo-random number generator via cyclic phase", + journal = "Mathematics and Computers in Simulation", + volume = "79", + number = "11", + pages = "3328--3338", + year = "2009", + note = "", + issn = "0378-4754", + doi = "10.1016/j.matcom.2009.05.006", + url = "http://www.sciencedirect.com/science/article/pii/S0378475409001463", + author = "A. Marchi and A. Liverani and A. Del Giudice", + keywords = "Monte carlo simulation", + keywords1 = "Random number", + keywords2 = "Pseudo-random number generator shift register" +} + +@Article{ Guler2011, + title = "A high speed, fully digital IC random number generator", + journal = "AEU - International Journal of Electronics and Communications", + volume = "", + number = "0", + pages = "--", + year = "2011", + note = "", + issn = "1434-8411", + doi = "10.1016/j.aeue.2011.06.001", + url = "http://www.sciencedirect.com/science/article/pii/S1434841111001713", + author = "Ulkuhan Guler and Salih Ergun", + keywords = "Ring oscillators", + keywords1 = "Phase noise", + keywords2 = "Random number generators" +} + +@Article{ Vadim2011692, + title = "Pseudo-random number generators for Monte Carlo simulations on ATI Graphics Processing Units", + journal = "Computer Physics Communications", + volume = "182", + number = "3", + pages = "692--705", + year = "2011", + note = "", + issn = "0010-4655", + doi = "10.1016/j.cpc.2010.12.008", + url = "http://www.sciencedirect.com/science/article/pii/S0010465510004868", + author = "Vadim and Demchik", + keywords = "Numerical calculations", + keywords1 = "Monte Carlo", + keywords2 = "Programming", + keywords3 = "Performance", + keywords4 = "GPGPU" } @Article{ Kocarev2001, @@ -119,6 +255,75 @@ timestamp = "2009.10.29" } +@Article{ Ergun2007235, + title = "Truly random number generators based on a non-autonomous chaotic oscillator", + journal = "AEU - International Journal of Electronics and Communications", + volume = "61", + number = "4", + pages = "235--242", + year = "2007", + note = "", + issn = "1434-8411", + doi = "10.1016/j.aeue.2006.05.006", + url = "http://www.sciencedirect.com/science/article/pii/S1434841106000720", + author = "Salih Ergun and Serdar Ozoguz", + keywords = "Chaotic oscillators", + keywords1 = "Random number generators" +} + +@Article{ Zhou20093442, + title = "True random number generator based on mouse movement and chaotic hash function", + journal = "Information Sciences", + volume = "179", + number = "19", + pages = "3442--3450", + year = "2009", + note = "", + issn = "0020-0255", + doi = "10.1016/j.ins.2009.06.005", + url = "http://www.sciencedirect.com/science/article/pii/S0020025509002540", + author = "Qing Zhou and Xiaofeng Liao and Kwok-wo Wong and Yue Hu and Di Xiao", + keywords = "Chaos", + keywords1 = "Mouse movement", + keywords2 = "TRNG" +} + +@Article{ Gonzalez2002259, + title = "Chaos-induced true randomness", + journal = "Physica A: Statistical Mechanics and its Applications", + volume = "316", + number = "1-4", + pages = "259--288", + year = "2002", + note = "", + issn = "0378-4371", + doi = "10.1016/S0378-4371(02)01031-2", + url = "http://www.sciencedirect.com/science/article/pii/S0378437102010312", + author = "J.A Gonzalez and L.I Reyes and J.J Suarez and L.E Guerrero and G Guti{\'e}rrez", + keywords = "Choatic systems", + keywords1 = "Random systems", + keywords2 = "Experimental chaos" +} + +@Article{ Behnia20113455, + title = "A novel dynamic model of pseudo random number generator", + journal = "Journal of Computational and Applied Mathematics", + volume = "235", + number = "12", + pages = "3455--3463", + year = "2011", + note = "", + issn = "0377-0427", + doi = "10.1016/j.cam.2011.02.006", + url = "http://www.sciencedirect.com/science/article/pii/S0377042711000793", + author = "S. Behnia and A. Akhavan and A. Akhshani and A. Samsudin", + keywords = "Chaotic function", + keywords1 = "Pseudo random sequence", + keywords2 = "Ergodic theory", + keywords3 = "Invariant measure", + keywords4 = "Perron--Frobenius operator" +} + @Misc{ Robshaw95streamciphers, author = "M. J. B. Robshaw", title = "Stream Ciphers", @@ -277,6 +482,22 @@ timestamp = "2010.02.05" } +@Article{ Gonzalez2005281, + title = "Statistical complexity measure of pseudorandom bit generators", + journal = "Physica A: Statistical Mechanics and its Applications", + volume = "354", + number = "0", + pages = "281--300", + year = "2005", + note = "", + issn = "0378-4371", + doi = "10.1016/j.physa.2005.02.054", + url = "http://www.sciencedirect.com/science/article/pii/S0378437105001779", + author = "C.M. Gonzalez and H.A. Larrondo and O.A. Rosso", + keywords = "Random number generators", + keywords1 = "Statistical complexity" +} + @Article{ Schuster1984, title = "Deterministic Chaos An introduction", author = "H. G. Schuster", @@ -584,3 +805,81 @@ numpages = "14" } +@Article{ james1995, + title = "Chaos and randomness", + author = "F. James", + journal = "Chaos, Solitons \& Fractals", + pages = "221--226", + volume = "6", + year = "1995" +} + +@Article{ Djema2009, + title = "Discrete time normal form for left invertibility problem +", + author = "M. Djema and J.P. Barbot and I. Belmouhoub", + journal = "European Journal of Control +", + pages = "194----204 +", + volume = "15 (2) +", + year = "2009" +} + +@Article{ Behnia2008408, + title = "A novel algorithm for image encryption based on mixture of chaotic maps", + journal = "Chaos, Solitons \& Fractals", + volume = "35", + number = "2", + pages = "408--419", + year = "2008", + note = "", + issn = "0960-0779", + doi = "10.1016/j.chaos.2006.05.011", + url = "http://www.sciencedirect.com/science/article/pii/S0960077906004681", + author = "S. Behnia and A. Akhshani and H. Mahmodi and A. Akhavan" +} + +@Article{ Belmouhoub2005, + title = "Observability quadratic normal form for discrete-time systems ", + author = "I. Belmouhoub and M. Djemai and J.-P. Barbot", + journal = "Automatic Control, IEEE Transactions on ", + pages = "1031--1038", + volume = "50", + number = "7", + month = "July", + year = "2005" +} + +@Book{ Hao1993, + title = "Starting with parabolas: an introduction to chaotic dynamics", + author = "B. Hao", + publisher = "Shanghai China: Shanghai Scientific and Technological +Education Publishing House +", + year = "1993" +} + +@Article{ Fridrich98symmetricciphers, + author = "Jiri Fridrich", + title = "Symmetric Ciphers Based On Two-Dimensional Chaotic Maps", + journal = "Int. J. Bifurcation and Chaos", + year = "1998", + volume = "8", + pages = "1259--1284" +} + +@Article{ Brown1996, + title = "Clarifying chaos: examples and counterexamples +", + author = "R. + Brown and LO. + Chua", + journal = "International Journal of Bifurcation and Chaos", + pages = "219--249", + volume = "6", + number = "(2)", + year = "1996" +} + -- 2.39.5