Un generador de números pseudoaleatorios (GNPA) 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 GNPA. 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 secuencias que presentan una distribución uniforme conforme a diversos tipos de pruebas estadísticas.

Entre las clases más comunes de estos algoritmos se encuentran los generadores lineales congruenciales, los generadores Fibonacci demorados, los basados en registros de desplazamiento con retroalimentación lineal (LFSR) y aquellos con retroalimentación generalizada.

Entre los desarrollos más recientes de generadores pseudoaleatorios destacan los algoritmos Blum Blum Shub, Fortuna y el Mersenne twister, ampliamente utilizados por su calidad estadística y su aplicabilidad en criptografía, simulación y modelado computacional.

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

Problemas de los generadores deterministas En la práctica, los resultados de muchos GNPA 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 GNPA 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. +AlgoritmoAñoAutoresReferenciasDescripciónMedio del cuadrado1946John von NeumannUn PRNG considerado de baja calidad pero de gran relevancia histórica por ser uno de los algoritmos pioneros.Generador de Lehmer1951D. H. LehmerTambién conocido como método Congruente Lineal Multiplicativo y de gran influencia en este campo de estudio.Generador lineal congruencial1958W. E. ThomsonModelo derivado de Lehmer (1951) de gran influencia y muy estudiado en todo el mundo.Generador Lagged Fibonacci (LFG)1958G. J. Mitchell; D.P. MooreUn algoritmo muy influyente en el campo del estudio de los procesos de generación de números aleatorios que inspiró a otros grandes autores en los siguientes años como George Marsaglia, creador del valorado test de calidad de números aleatorios llamado "Diehard", por ejemplo.Linear-feedback Shift Register1965R. C. TauswortheUn generador cuyo diseño influyó en muchos otros PRNG posteriores. Por lo tanto, es muy importante desde el punto de vista histórico. También conocido como el generador Tausworthe.Generador de Wichmann-Hill1982B. A. Wichmann; D. I. HillUna combinación de tres pequeños LCGs, adecuados para CPUs de 16 bits. Ampliamente utilizado en muchos programas, por ejemplo se utilizó en Excel 2003 y algunas versiones posteriores para la función RAND de Excel y fue el generador por defecto en el lenguaje Python hasta la versión 2.2.Rule 301983Stephen WolframGenerador basado en autómatas celulares.Blum Blum Shub1986Manuel Blum;Leonore Blum; Michael ShubConsiderado uno de los generadores más seguros desde el punto de vista criptográfico, debido principalmente a la implementación en su fórmula de estudios y conceptos derivados de la teoría de números.Generador de Park-Miller1988S. K. Park; K. W. MillerUna implementación específica de un generador de Lehmer, ampliamente utilizada porque se incluye en C++ como la función minstd_rand0 a partir de C++11.MIXMAX1991G. K. Savvidy; N. G. Ter-Arutyunyan-SavvidyEs un generador que pertenece a la clase de generador lineal congruente matricial, una generalización del Método Congruente Lineal. La lógica de la familia de generadores MIXMAX se basa en los resultados de la teoría ergódica y la mecánica clásica.Add-with-carry (ACW)1991G. Marsaglia; A. ZamanUna modificación de los generadores Lagged-Fibonacci.Subtract-with-borrow1991G. Marsaglia; A. ZamanAlgoritmo derivado de los generadores Lagged-Fibonacci.ISAAC1993R. J. JenkinsGenerador criptográfico seguro (CSPRNG) desarrollado por Robert J. Jenkins.Mersenne twister1998M. Matsumoto; T. NishimuraProbablemente sea el generador más conocido de esta lista, principalmente porque es un algoritmo implementado en las funciones RAND de los lenguajes de programación Python y R, además de su gran presencia en juegos electrónicos como el Pro Evolution Soccer (PES).Xorshift2003G. MarsagliaEs un subtipo muy rápido de generadores LFSR. Marsaglia también propuso como mejora el generador xorwow, en el que la salida de un generador xorshift se suma con una secuencia de Weyl. El generador xorwow es el generador por defecto de la biblioteca CURAND de la interfaz de programación de aplicaciones nVidia CUDA para unidades de procesamiento gráfico.Fortuna2003Bruce Schneier; Niels FergusonAlgoritmo considerado criptográficamente seguro. Un CSPRNG muy conocido por ser implementado en los sistemas y productos de Apple.Well equidistributed long-period linear (WELL)2006F. Panneton; P. L'Ecuyer; M. MatsumotoAlgoritmo conocido por ser complementario al Mersenne Twister (MT), buscando deliberadamente cubrir sus puntos débiles.Advanced Randomization System (ARS)2011J. Salmon; M. Moraes; R. Dror; D. ShawUna versión simplificada del cifrado en bloque AES, que permite un rendimiento muy rápido en el sistema que soporta AES-NI.Permuted Congruential Generator (PCG)2014M. E. O'NeillUn modelo derivado del Método Lineal Congruencial.Random Cycle Bit Generator (RCB)2016R. CookmanEl RCB se describe como un generador de patrones de bits hecho para superar algunas de las deficiencias con el Mersenne Twister (MT) y la restricción de duración de período/bit corto de los generadores de desplazamiento/módulo.Xoroshiro128+2018D. Blackman; S. VignaUna modificación de los generadores Xorshift de G. Marsaglia, uno de los generadores más rápidos en las CPUs modernas de 64 bits. Los generadores relacionados son xoroshiro128**, xoshiro256+ y xoshiro256***.64-bit MELG (MELG-64)2018S. Harase; T. KimotoUna implementación de generadores lineales F2 de 64 bits con el período primario de Mersenne.Squares RNG2020B. WidynskiGenerador derivado del método del cuadrado medio propuesto por Jhon von Neumman.Itamaracá (Ita)2021D. H. PereiraConocido por ser el primer algoritmo PRNG que tiene la Función de Valor Absoluto en su base. Itamaracá también se presenta como un modelo sencillo y rápido que genera secuencias de números aleatorios aperiódicos.

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 : 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 in Embedded Systems by Eric Uner

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

Categoría:Algoritmos