Generador de números pseudoaleatorios

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Un generador pseudoaleatorio de números (GPAN) es un algoritmo que produce una sucesión de números que es una muy buena aproximación a un conjunto aleatorio de números. La sucesión no es exactamente aleatoria en el sentido de que queda completamente determinada por un conjunto relativamente pequeño de valores iniciales, llamados el estado del GPAN. Si bien es posible generar sucesiones mediante generadores de números aleatorios por dispositivos mecánicos que son mejores aproximaciones a una sucesión aleatoria, los números pseudo-aleatorios son importantes en la práctica para simulaciones (por ejemplo, de sistemas físicos mediante el método de Montecarlo), y desempeñan un papel central en la criptografía.

La mayoría de los algoritmos de generadores pseudoaleatorios producen sucesiones que poseen una distribución uniforme según varios tipos de pruebas. Las clases más comunes de estos algoritmos son generadores lineales congruentes, generadores Fibonacci demorados, desplazamiento de registros con retroalimentación lineal y desplazamientos de registros con retroalimentación generalizada. Entre los desarrollos más recientes de algoritmos pseudoaleatorios se encuentran Blum Blum Shub, Fortuna, y el Mersenne twister.

Se requiere de un cuidadoso análisis matemático para tener algún tipo de confianza en que un dado GPAN genera números que son suficientemente "aleatorios" para ser útiles para el propósito para el que se los precisa. Robert R. Coveyou del Oak Ridge National Laboratory escribió un artículo titulado, "La generación de números aleatorios es demasiado importante como para ser dejado al azar."[1] Y como John von Neumann decía en broma, "Todo el que desarrolla métodos aritméticos para producir dígitos aleatorios esta desde luego en pecado."[2]

Problemas de los generadores determinísticos[editar]

En la práctica, los resultados de muchos GPAN presentan artefactos matemáticos que hacen que los mismos fallen en pruebas de detección de parámetros estadísticos. Entre estos se incluyen,

  • Períodos más cortos que lo esperado para algunos estados semilla; en este contexto dichos estados semilla pueden ser llamados 'débiles'
  • Falta de uniformidad de la distribución
  • Correlación de valores sucesivos
  • Pobre distribución dimensional de la sucesión resultado
  • Las distancias entre la ocurrencia de ciertos valores están distribuidas de manera distinta que la que corresponde a una sucesión aleatoria
  • Algunas secuencias de bits son 'más aleatorias' que otras

Los defectos que son exhibidos por los GPAN van desde un rango de lo imperceptible hasta lo absolutamente obvio. El algorimo de números aleatorios RANDU utilizado por décadas en grandes computadoras tipo mainframe poseía serias deficiencias, y como consecuencia mucho del trabajo de investigación producido en ese período es menos confiable de lo que podría haber sido.

Notas[editar]

  1. Peterson, Ivars. The Jungles of Randomness: A Mathematical Safari. Wiley, NY, 1998. (pp. 178) ISBN 0-471-16449-6
  2. "Various techniques used in connection with random digits", Applied Mathematics Series, no. 12, 36-38 (1951).

Referencias[editar]

  • Michael Luby, Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996. A definitive source of techniques for provably random sequences.
  • Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Chapter 3, pp.1–193. Extensive coverage of statistical tests for non-randomness.
  • R. Matthews Maximally Periodic Reciprocals Bulletin of the Institute of Mathematics and its Applications 28 147-148 1992
  • J. Viega, Practical Random Number Generation in Software, in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.
  • John von Neumann, "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Montecarlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U.S. Government Printing Office, 1951): 36-38.
  • NIST Recommendation for Random Number Generation Using Deterministic Random Bit Generators

Enlaces externos[editar]