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 pseudoaleatorios 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

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

Lista de Generadores de Números Pseudoaleatorios

En esta sección se presenta una lista de generadores que marcaron históricamente el campo de estudio del proceso de generación de números pseudoaleatorios, ya sea por su importancia histórica o por ser un modelo innovador teniendo en cuenta sus respectivas épocas. Además, a pesar de ser PRNGs (Generadores de Números Pseudoaleatorios, en inglés) algunos de ellos pueden ser aplicables dentro del campo de la criptografía, como es el caso del fuerte algoritmo Blum Blum Shub y Fortuna como se ha presentado anteriormente.

Notas

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 Archivado el 24 de febrero de 2011 en Wayback Machine.: Web based Random-number generator built and maintained by Mads Haahr.
• RNG: Good Random Number Generator.
• 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 (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). Generating random numbers in Embedded Systems by Eric Uner

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