Generador de números pseudoaleatorios

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." 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."

Referencias

• 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

• La biblioteca científica GNU. Una biblioteca libre (GPL) en lenguaje C que incluye algunos algoritmos GPAN.
• DieHarder: A free (GPL) C Random Number Test Suite.
• crng: Generadores aleatorios de números programados como extensiones de tipo Python codificadas en lenguaje C.
• random.org: Web based Random-number generator built and maintained by Mads Haahr.
• http://eeyore.wu-wien.ac.at/src/ prng: Una colección de algoritmos para generar números pseudoaleatorios programados en lenguaje C, bajo GPL.
• Strange Attractors and TCP/IP Sequence Number Analysis - an analysis of the strength of PRNGs used to create TCP/IP sequence numbers by various operating systems using strange attractors. This is a good practical example of issues in PRNGs and the variation possible in their implementation.
  • Strange Attractors and TCP/IP Sequence Number Analysis - One Year Later - a follow-up article demonstrating some of the evolution of various PRNG algorithms over time.
• Generating random numbers Generating random numbers in Embedded Systems by Eric Uner

• Analysis of the Linux Random Number Generator by Zvi Gutterman, Benny Pinkas, and Tzachy Reinman