Abstract:
Pseudorandom number generators (PRNG) are extensively used in Monte Carlo simulations, gambling machines and cryptography as substitutes of ideal random number generators (RNG). Each application imposes different statistical requirements to PRNGs. As L'Ecuyer clearly states "the main goal for Monte Carlo methods is to reproduce the statistical properties on which these methods are based whereas for gambling machines and cryptology, observing the sequence of output values for some time should provide no practical advantage for predicting the forthcoming numbers better than by just guessing at random". In accordance with different applications several statistical test suites have been developed to analyze the sequences generated by PRNGs. In a recent paper a new statistical complexity measure [Phys. Lett. A 311 (2003) 126] has been defined. Here we propose this measure, as a randomness quantifier of a PRNGs. The test is applied to three very well known and widely tested PRNGs available in the literature. All of them are based on mathematical algorithms. Another PRNGs based on Lorenz 3D chaotic dynamical system is also analyzed. PRNGs based on chaos may be considered as a model for physical noise sources and important new results are recently reported. All the design steps of this PRNG are described, and each stage increase the PRNG randomness using different strategies. It is shown that the MPR statistical complexity measure is capable to quantify this randomness improvement. The PRNG based on the chaotic 3D Lorenz dynamical system is also evaluated using traditional digital signal processing tools for comparison. © 2005 Elsevier B.V. All rights reserved.
Registro:
Documento: |
Artículo
|
Título: | Statistical complexity measure of pseudorandom bit generators |
Autor: | González, C.M.; Larrondo, H.A.; Rosso, O.A. |
Filiación: | Facultad de Ingeniería, Universidad Nacional de Mar del Plata, Juan B. Justo 4302, 7600 Mar del Plata, Argentina Chaos and Biology Group, Instituto de Cálculo, Fac. de Ciencias Exactas Y Naturales, Universidad de Buenos Aires, Pabellon II, Ciudad Universitaria, 1428 Ciudad de Buenos Aires, Argentina
|
Palabras clave: | Random number generators; Statistical complexity; Acoustic noise; Algorithms; Computational complexity; Computer simulation; Monte Carlo methods; Public key cryptography; Statistical mechanics; Chaotic dynamical systems; Noise sources; Random number generators; Statistical complexity; Random processes |
Año: | 2005
|
Volumen: | 354
|
Número: | 1-4
|
Página de inicio: | 281
|
Página de fin: | 300
|
DOI: |
http://dx.doi.org/10.1016/j.physa.2005.02.054 |
Título revista: | Physica A: Statistical Mechanics and its Applications
|
Título revista abreviado: | Phys A Stat Mech Appl
|
ISSN: | 03784371
|
CODEN: | PHYAD
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03784371_v354_n1-4_p281_Gonzalez |
Referencias:
- http://cgm.cs.mcgill.ca/~luc/rng.html; Schuster, H.G., (1984) Deterministic Chaos - An introduction, , Physik Verlag Weinheim
- Stojanovski, T., Kocarev, L., IEEE Trans (2001) Circuits Systems I, 48, p. 281
- Stojanovski, T., Kocarev, L., IEEE Trans (2001) Circuits Systems I, 48, p. 382
- Kocarev, L., Jakimoski, G., IEEE Trans (2003) Circuits Systems I, 50, p. 123
- Kocarev, L., (2001) IEEE Circuits Systems Mag., 1, p. 6
- Jessa, M., IEEE Trans (2002) Circuits Systems I, 49, pp. 84-89
- Li, S., http://www.hooklee.com/Thesis/ethesis.pdf, Ph.D Dissertation of Xi an Jiaotong University; Álvarez, G., Montoya, F., Romera, M., Pastor, G., (2003) Phys. Lett. a, 306, p. 200
- Álvarez, G., Montoya, F., Pastor, G., Romera, M., Breaking a Secure Communication Scheme Based on the Phase Synchronization of Chaotic Systems, , http://arxiv.org/pdf/nlin.CD/0311040
- Baptista, M.S., (1998) Phys. Lett. a, 240, p. 50
- Soto, J., Statistical Testing of Random Number Generators, , http://www.itl.nist.gov/div893/staff/soto/jshome.html
- Marsaglia, G., Diehard Statistical Tests, , http://stat.fsu.edu/~geo/diehard.html
- Gustafson, H.M., Dawson, E.P., Nielsen, L., Caelli, W.J., (1994) J. Comput. Security, 13, p. 687
- Rukhin, A.L., Testing randomness: A suite of statistical procedures (2000) Theory Probab. Appl., 45, p. 111
- L'ecuyer, P., Random number generation (2004) Handbook of Computational Statistics, , http://www.iro.umontreal.ca/~lecuyer/myftp/papers/handstat.pdf, J.E. Gentle, W. Haerdle, Y. Mory (Eds.) Springer, Berlin
- Vattulainen, I., Ala-Nissila, T., Kankaala, K., (1994) Phys. Rev. Lett., 73, p. 2513
- Ott, E., Sauer, T., Yorke, J.A., (1994) Copying with Chaos, , Wiley New York
- Ott, E., (1993) Chaos in Dynamical Systems, , Cambridge University Press New York
- Shiner, J.S., Davison, M., Landsberg, P.T., (1999) Phys. Rev. e, 59, p. 1459
- López-Ruiz, R., Mancini, H.L., Calbet, X., (1995) Phys. Lett. a, 209, p. 321
- Martin, M.T., Plastino, A., Rosso, O.A., (2003) Phys. Lett. a, 311, p. 126
- González, C.M., Larrondo, H.A., Gayoso, C.A., Arnone, L.J., Boemo, E.I., http://arXiv.org/abs/cs.CR/0402056; Cover, T.M., Thomas, J.A., (1991) Elements of Information Theory, , Wiley New York
- Feldman, D.P., Crutchfield, J.P., (1998) Phys. Lett. a, 238, p. 244
- Anteneodo, C., Plastino, A.R., (1996) Phys. Lett. a, 223, p. 348
- Wootters, W.K., (1981) Phys. Rev. D, 23, p. 357
- Martin, M.T., (2004), Ph.D. Thesis, Department of Mathematics, Faculty of Sciences University of La Plata, La Plata, Argentina; Menezes, A., Van Oorschot, P., Vanstone, S., (1997) Handbook of Applied Cryptography, , CRC Press Boca Raton
- Papoulis, A., (1991) Probability, Random Variables, and Stochastic Processes, , McGraw-Hill New York
- Mitra, S.K., (1998) Digital Signal Processing, , McGraw-Hill New York
Citas:
---------- APA ----------
González, C.M., Larrondo, H.A. & Rosso, O.A.
(2005)
. Statistical complexity measure of pseudorandom bit generators. Physica A: Statistical Mechanics and its Applications, 354(1-4), 281-300.
http://dx.doi.org/10.1016/j.physa.2005.02.054---------- CHICAGO ----------
González, C.M., Larrondo, H.A., Rosso, O.A.
"Statistical complexity measure of pseudorandom bit generators"
. Physica A: Statistical Mechanics and its Applications 354, no. 1-4
(2005) : 281-300.
http://dx.doi.org/10.1016/j.physa.2005.02.054---------- MLA ----------
González, C.M., Larrondo, H.A., Rosso, O.A.
"Statistical complexity measure of pseudorandom bit generators"
. Physica A: Statistical Mechanics and its Applications, vol. 354, no. 1-4, 2005, pp. 281-300.
http://dx.doi.org/10.1016/j.physa.2005.02.054---------- VANCOUVER ----------
González, C.M., Larrondo, H.A., Rosso, O.A. Statistical complexity measure of pseudorandom bit generators. Phys A Stat Mech Appl. 2005;354(1-4):281-300.
http://dx.doi.org/10.1016/j.physa.2005.02.054