Lista de generadores de números aleatorios

Los generadores de números aleatorios son importantes en muchos tipos de aplicaciones técnicas, incluidas la física , la ingeniería o los estudios informáticos matemáticos (por ejemplo, simulaciones de Monte Carlo ), la criptografía y los juegos de azar (en servidores de juegos ).

Esta lista incluye muchos tipos comunes, independientemente de su calidad o aplicabilidad a un caso de uso determinado.

Generadores de números pseudoaleatorios (PRNG)

Los siguientes algoritmos son generadores de números pseudoaleatorios .

Algoritmos criptográficos

Los algoritmos de cifrado y los hashes criptográficos se pueden utilizar como generadores de números pseudoaleatorios de muy alta calidad. Sin embargo, por lo general son considerablemente más lentos (normalmente, entre un factor de 2 y 10) que los generadores rápidos de números aleatorios no criptográficos.

Estos incluyen:

Cifrados de flujo . Las opciones más populares son Salsa20 o ChaCha (a menudo con la cantidad de rondas reducida a 8 para mayor velocidad), ISAAC , HC-128 y RC4 .
Cifrados de bloque en modo contador . Las opciones más comunes son AES (que es muy rápido en sistemas que lo admiten en hardware ), TwoFish , Serpent y Camellia .
Funciones hash criptográficas

Algunos generadores de números pseudoaleatorios criptográficamente seguros no se basan en algoritmos de cifrado, sino que intentan vincular matemáticamente la dificultad de distinguir su salida de un flujo aleatorio "real" con un problema computacionalmente difícil. Estos enfoques son importantes en teoría, pero son demasiado lentos para ser prácticos en la mayoría de las aplicaciones. Entre ellos se incluyen:

Algoritmo de Blum-Micali (1984)
Blum blum shub (1986)
Función pseudoaleatoria de Naor-Reingold (1997)

Generadores de números aleatorios que utilizan entropía externa

Estos enfoques combinan un generador de números pseudoaleatorios (a menudo en forma de cifrado de bloque o de flujo) con una fuente externa de aleatoriedad (por ejemplo, movimientos del mouse, demora entre pulsaciones de teclado, etc.).

/dev/random– Sistemas tipo Unix
CryptGenRandom – Microsoft Windows
Fortuna
Instrucciones RDRAND (llamadas Intel Secure Key por Intel ), disponibles en las CPU Intel x86 desde 2012. Utilizan el generador AES integrado en la CPU, reiniciándolo periódicamente.
Generador de números aleatorios verdaderos mediante descarga de corona. ^[40]
Milenrama

Véase también

Juego de dados
Pruebas de alto nivel : conjunto de pruebas estadísticas para generadores de números aleatorios
Generación de variables aleatorias no uniformes
Generador de números aleatorios de hardware
Ataque con generador de números aleatorios
Aleatoriedad
TestU01 : conjunto de pruebas estadísticas para generadores de números aleatorios

Referencias

^ Algunos de los artículos de von Neumann de 1949 se imprimieron recién en 1951. John von Neumann, “Various technique used in connection with random digits,” en AS Householder, GE Forsythe y HH Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series , vol. 12 (Washington, DC: US Government Printing Office, 1951): pp. 36–38.
^ Lehmer, Derrick H. (1951). "Métodos matemáticos en unidades de computación a gran escala". Actas del 2º Simposio sobre Maquinaria de Cálculo Digital a Gran Escala : 141–146.
^ Thomson, WE (1958). "Un método de congruencia modificado para generar números pseudoaleatorios". The Computer Journal . 1 (2): 83. doi : 10.1093/comjnl/1.2.83 .
^ Rotenberg, A. (1960). "Un nuevo generador de números pseudoaleatorios". Revista de la ACM . 7 (1): 75–77. doi : 10.1145/321008.321019 . S2CID 16770825.
^ DE Knuth, El arte de la programación informática, vol. 2 Algoritmos seminuméricos, 3.ª ed., Addison Wesley Longman (1998); Véase la página 27.
^ Tausworthe, RC (1965). "Números aleatorios generados por recurrencia lineal módulo dos" (PDF) . Matemáticas de la computación . 19 (90): 201–209. doi : 10.1090/S0025-5718-1965-0184406-1 .
^ Wichmann, Brian A.; Hill, David I. (1982). "Algoritmo AS 183: un generador de números pseudoaleatorios eficiente y portátil". Revista de la Royal Statistical Society. Serie C (Estadística aplicada) . 31 (2): 188–190. doi :10.2307/2347988. JSTOR 2347988.
^ "Soporte de Microsoft: Descripción de la función RAND en Excel". 17 de abril de 2018.
^ "Documentación » La biblioteca estándar de Python » 9. Módulos numéricos y matemáticos » 9.6. random — Generar números pseudoaleatorios".
^ Wolfram, S. (1983). "Mecánica estadística de autómatas celulares". Rev. Mod. Phys . 55 (3): 601–644. Código Bibliográfico :1983RvMP...55..601W. doi :10.1103/RevModPhys.55.601.
^ Eichenauer, Jürgen; Lehn, Jürgen (1986). "Un generador de números pseudoaleatorios congruenciales no lineales". Estadísticas estadísticas . 27 : 315–326. doi :10.1007/BF02932576. S2CID 122052399.
^ Blum, L.; Blum, M.; Shub, M. (1986-05-01). "Un generador de números pseudoaleatorios simple e impredecible". Revista SIAM de Computación . 15 (2): 364–383. doi :10.1137/0215025. ISSN 0097-5397.
^ Park, Stephen K.; Miller, Keith W. (1988). "Generadores de números aleatorios: los buenos son difíciles de encontrar" (PDF) . Comunicaciones de la ACM . 31 (10): 1192–1201. doi :10.1145/63039.63042. S2CID 207575300.
^ "Generación de números pseudoaleatorios". cppreference.com . Consultado el 14 de noviembre de 2021 .
^ Wikramaratna, RS (1989). "ACORN — Un nuevo método para generar secuencias de números pseudoaleatorios distribuidos uniformemente". Journal of Computational Physics . 83 (1): 16–31. Bibcode :1989JCoPh..83...16W. doi :10.1016/0021-9991(89)90221-0.
^ Wikramaratna, RS Resultados de convergencia teórica y empírica para generadores de números aleatorios congruenciales aditivos, Journal of Computational and Applied Mathematics (2009), doi :10.1016/j.cam.2009.10.015
^ Savvidy, GK; Ter-Arutyunyan-Savvidy, NG (1991). "Sobre la simulación de Monte Carlo de sistemas físicos". Journal of Computational Physics . 97 (2): 566. Bibcode :1991JCoPh..97..566S. doi :10.1016/0021-9991(91)90015-D.
^ ab George, Marsaglia; Zaman, Arif (1991). "Una nueva clase de generadores de números aleatorios". Anales de probabilidad aplicada . 1 (3): 462–480. doi : 10.1214/aoap/1177005878 .
^ Martin, Lüscher (1994). "Un generador de números aleatorios portátil de alta calidad para simulaciones de teoría de campos en red". Computer Physics Communications . 79 (1): 100–110. arXiv : hep-lat/9309020 . Código Bibliográfico :1994CoPhC..79..100L. doi :10.1016/0010-4655(94)90232-1. S2CID 17608961.
^ Matthews, Robert AJ (1992). "Recíprocos de máxima periodicidad". Bull. Inst. Math. Appl . 28 : 147–148.
^ Marsaglia, George; Zaman, Arif (1993). "El generador KISS". Informe técnico, Departamento de Estadística, Universidad Estatal de Florida, Tallahassee, FL, EE. UU .
^ Publicación de George Marsaglia en el grupo de noticias sci.stat.math del 1 de agosto de 2018 con el título 'Otro RNG más'.
^ Koç, Cemal (1995). "Secuencias recurrentes con acarreo". Revista de probabilidad aplicada . 32 (4): 966–971. doi :10.2307/3215210. JSTOR 3215210. S2CID 123798320.
^ Couture, Raymond; L'Ecuyer, Pierre (1997). "Propiedades de distribución de generadores de números aleatorios de multiplicación con acarreo" (PDF) . Matemáticas de la computación . Número 66. 218 (218): 591–607. Bibcode :1997MaCom..66..591C. doi : 10.1090/S0025-5718-97-00827-2 .
^ Matsumoto, M.; Nishimura, T. (1998). "MersenneTwister: Generador de números pseudoaleatorios uniformes equidistribuidos en 3 dimensiones". ACM Transactions on Modeling and Computer Simulation . 8 (1): 3–30. CiteSeerX 10.1.1.215.1141 . doi :10.1145/272991.272995. S2CID 3332028.
^ Marsaglia, George (julio de 2003). "Generadores aleatorios Xorshift". Revista de software estadístico . 8 (14). doi : 10.18637/jss.v008.i14 .
^ Panneton, François O.; l'Ecuyer, Pierre; Matsumoto, Pierre (marzo de 2006). "Generadores mejorados de período largo basados en recurrencias lineales módulo 2" (PDF) . ACM Transactions on Mathematical Software . 32 (1): 1–16. CiteSeerX 10.1.1.73.5499 . doi :10.1145/1132973.1132974. S2CID 7368302.
^ Jenkins, Bob (2009). "Un pequeño PRNG no criptográfico".
^ abc Salmon, John; Moraes, Mark; Dror, Ron; Shaw, David (2011). "Números aleatorios paralelos: tan fácil como 1, 2, 3". Actas de la Conferencia internacional de 2011 sobre computación de alto rendimiento, redes, almacenamiento y análisis, artículo n.º 16. doi : 10.1145/2063384.2063405.
^ Balkova, Lubomira; Bucci, Michelangelo; De Luca, Alessandro; Hladky, Jiri; Puzynina, Svetlana (septiembre de 2016). "Generadores de números pseudoaleatorios aperiódicos basados en palabras infinitas". Ciencias de la Computación Teórica . 647 : 85–100. arXiv : 1311.6002 . doi :10.1016/j.tcs.2016.07.042. S2CID 2175443.
^ Steele, Guy L. Jr.; Lea, Doug; Flood, Christine H. (2014). "Generadores de números pseudoaleatorios divisibles rápidamente" (PDF) . OOPSLA '14 Actas de la Conferencia internacional ACM 2014 sobre lenguajes y aplicaciones de sistemas de programación orientados a objetos .
^ O'Neill, Melissa E. (2014). "PCG: una familia de algoritmos simples, rápidos y con uso eficiente del espacio y estadísticamente buenos para la generación de números aleatorios" (PDF) . Informe técnico .
^ Cookman, Richard (2016). "Generador de bits de ciclo aleatorio (rcb_generator)". Informe técnico .
^ Widynski, Bernard (2017). "Generador aleatorio de secuencia de Weyl de cuadrado medio". arXiv : 1704.00358 [cs.CR].
^ Kneusel, Ron (2018). Números aleatorios y computadoras (1.ª ed.). Springer. pp. 13-14. ISBN 9783319776972.
^ Cabuk, Umut Can; Aydin, Ömer; Dalkiliç, Gökhan (2017). "Un generador de números aleatorios para protocolos de autenticación ligeros: xorshiftR+". Revista turca de ingeniería eléctrica y ciencias de la computación . 25 : 4818–4828. doi : 10.3906/elk-1703-361.
^ Blackman, David; Vigna, Sebastiano (2018). "Generadores pseudoaleatorios lineales desordenados". arXiv : 1805.01407 [cs.DS].
^ Harase, S.; Kimoto, T. (2018). "Implementación de generadores lineales F2 de distribución máxima equidistribuida de 64 bits con período primo de Mersenne". ACM Transactions on Mathematical Software . 44 (3): 30:1–30:11. arXiv : 1505.06582 . doi :10.1145/3159444. S2CID 14923086.
^ Widynski, Bernard (2020). "Cuadrados: un generador de números aleatorios rápido basado en contadores". arXiv : 2004.06278 [cs.DS].
^ Generador de números aleatorios verdaderos mediante descarga de corona: Oficina de Patentes de la India. Número de solicitud de patente: 201821026766

Enlaces externos

Serie SP800-90 sobre generación de números aleatorios, NIST
Manual de referencia de la biblioteca científica GNU sobre generación de números aleatorios
Rutinas de generación de números aleatorios en la biblioteca numérica NAG
Descripción general de los PRNG de Chris Lomont, incluida una buena implementación del algoritmo WELL512
Código fuente para leer datos de un TRNG de hardware TrueRNG V2

[1] Algunos de los artículos de von Neumann de 1949 se imprimieron recién en 1951. John von Neumann, “Various technique used in connection with random digits,” en AS Householder, GE Forsythe y HH Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series , vol. 12 (Washington, DC: US Government Printing Office, 1951): pp. 36–38.

[2] Lehmer, Derrick H. (1951). "Métodos matemáticos en unidades de computación a gran escala". Actas del 2º Simposio sobre Maquinaria de Cálculo Digital a Gran Escala : 141–146.

[3] Thomson, WE (1958). "Un método de congruencia modificado para generar números pseudoaleatorios". The Computer Journal . 1 (2): 83. doi : 10.1093/comjnl/1.2.83 .

[4] Rotenberg, A. (1960). "Un nuevo generador de números pseudoaleatorios". Revista de la ACM . 7 (1): 75–77. doi : 10.1145/321008.321019 . S2CID 16770825.

[5] DE Knuth, El arte de la programación informática, vol. 2 Algoritmos seminuméricos, 3.ª ed., Addison Wesley Longman (1998); Véase la página 27.

[6] Tausworthe, RC (1965). "Números aleatorios generados por recurrencia lineal módulo dos" (PDF) . Matemáticas de la computación . 19 (90): 201–209. doi : 10.1090/S0025-5718-1965-0184406-1 .

[7] Wichmann, Brian A.; Hill, David I. (1982). "Algoritmo AS 183: un generador de números pseudoaleatorios eficiente y portátil". Revista de la Royal Statistical Society. Serie C (Estadística aplicada) . 31 (2): 188–190. doi :10.2307/2347988. JSTOR 2347988.

[8] "Soporte de Microsoft: Descripción de la función RAND en Excel". 17 de abril de 2018.

[9] "Documentación » La biblioteca estándar de Python » 9. Módulos numéricos y matemáticos » 9.6. random — Generar números pseudoaleatorios".

[10] Wolfram, S. (1983). "Mecánica estadística de autómatas celulares". Rev. Mod. Phys . 55 (3): 601–644. Código Bibliográfico :1983RvMP...55..601W. doi :10.1103/RevModPhys.55.601.

[11] Eichenauer, Jürgen; Lehn, Jürgen (1986). "Un generador de números pseudoaleatorios congruenciales no lineales". Estadísticas estadísticas . 27 : 315–326. doi :10.1007/BF02932576. S2CID 122052399.

[12] Blum, L.; Blum, M.; Shub, M. (1986-05-01). "Un generador de números pseudoaleatorios simple e impredecible". Revista SIAM de Computación . 15 (2): 364–383. doi :10.1137/0215025. ISSN 0097-5397.

[13] Park, Stephen K.; Miller, Keith W. (1988). "Generadores de números aleatorios: los buenos son difíciles de encontrar" (PDF) . Comunicaciones de la ACM . 31 (10): 1192–1201. doi :10.1145/63039.63042. S2CID 207575300.

[14] "Generación de números pseudoaleatorios". cppreference.com . Consultado el 14 de noviembre de 2021 .

[15] Wikramaratna, RS (1989). "ACORN — Un nuevo método para generar secuencias de números pseudoaleatorios distribuidos uniformemente". Journal of Computational Physics . 83 (1): 16–31. Bibcode :1989JCoPh..83...16W. doi :10.1016/0021-9991(89)90221-0.

[16] Wikramaratna, RS Resultados de convergencia teórica y empírica para generadores de números aleatorios congruenciales aditivos, Journal of Computational and Applied Mathematics (2009), doi :10.1016/j.cam.2009.10.015

[17] Savvidy, GK; Ter-Arutyunyan-Savvidy, NG (1991). "Sobre la simulación de Monte Carlo de sistemas físicos". Journal of Computational Physics . 97 (2): 566. Bibcode :1991JCoPh..97..566S. doi :10.1016/0021-9991(91)90015-D.

[George_1991_462–480-18] George, Marsaglia; Zaman, Arif (1991). "Una nueva clase de generadores de números aleatorios". Anales de probabilidad aplicada . 1 (3): 462–480. doi : 10.1214/aoap/1177005878 .

[19] Martin, Lüscher (1994). "Un generador de números aleatorios portátil de alta calidad para simulaciones de teoría de campos en red". Computer Physics Communications . 79 (1): 100–110. arXiv : hep-lat/9309020 . Código Bibliográfico :1994CoPhC..79..100L. doi :10.1016/0010-4655(94)90232-1. S2CID 17608961.

[20] Matthews, Robert AJ (1992). "Recíprocos de máxima periodicidad". Bull. Inst. Math. Appl . 28 : 147–148.

[21] Marsaglia, George; Zaman, Arif (1993). "El generador KISS". Informe técnico, Departamento de Estadística, Universidad Estatal de Florida, Tallahassee, FL, EE. UU .

[22] Publicación de George Marsaglia en el grupo de noticias sci.stat.math del 1 de agosto de 2018 con el título 'Otro RNG más'.

[23] Koç, Cemal (1995). "Secuencias recurrentes con acarreo". Revista de probabilidad aplicada . 32 (4): 966–971. doi :10.2307/3215210. JSTOR 3215210. S2CID 123798320.

[24] Couture, Raymond; L'Ecuyer, Pierre (1997). "Propiedades de distribución de generadores de números aleatorios de multiplicación con acarreo" (PDF) . Matemáticas de la computación . Número 66. 218 (218): 591–607. Bibcode :1997MaCom..66..591C. doi : 10.1090/S0025-5718-97-00827-2 .

[25] Matsumoto, M.; Nishimura, T. (1998). "MersenneTwister: Generador de números pseudoaleatorios uniformes equidistribuidos en 3 dimensiones". ACM Transactions on Modeling and Computer Simulation . 8 (1): 3–30. CiteSeerX 10.1.1.215.1141 . doi :10.1145/272991.272995. S2CID 3332028.

[26] Marsaglia, George (julio de 2003). "Generadores aleatorios Xorshift". Revista de software estadístico . 8 (14). doi : 10.18637/jss.v008.i14 .

[27] Panneton, François O.; l'Ecuyer, Pierre; Matsumoto, Pierre (marzo de 2006). "Generadores mejorados de período largo basados en recurrencias lineales módulo 2" (PDF) . ACM Transactions on Mathematical Software . 32 (1): 1–16. CiteSeerX 10.1.1.73.5499 . doi :10.1145/1132973.1132974. S2CID 7368302.

[28] Jenkins, Bob (2009). "Un pequeño PRNG no criptográfico".

[:0-29] Salmon, John; Moraes, Mark; Dror, Ron; Shaw, David (2011). "Números aleatorios paralelos: tan fácil como 1, 2, 3". Actas de la Conferencia internacional de 2011 sobre computación de alto rendimiento, redes, almacenamiento y análisis, artículo n.º 16. doi : 10.1145/2063384.2063405.

[30] Balkova, Lubomira; Bucci, Michelangelo; De Luca, Alessandro; Hladky, Jiri; Puzynina, Svetlana (septiembre de 2016). "Generadores de números pseudoaleatorios aperiódicos basados en palabras infinitas". Ciencias de la Computación Teórica . 647 : 85–100. arXiv : 1311.6002 . doi :10.1016/j.tcs.2016.07.042. S2CID 2175443.

[31] Steele, Guy L. Jr.; Lea, Doug; Flood, Christine H. (2014). "Generadores de números pseudoaleatorios divisibles rápidamente" (PDF) . OOPSLA '14 Actas de la Conferencia internacional ACM 2014 sobre lenguajes y aplicaciones de sistemas de programación orientados a objetos .

[32] O'Neill, Melissa E. (2014). "PCG: una familia de algoritmos simples, rápidos y con uso eficiente del espacio y estadísticamente buenos para la generación de números aleatorios" (PDF) . Informe técnico .

[33] Cookman, Richard (2016). "Generador de bits de ciclo aleatorio (rcb_generator)". Informe técnico .

[34] Widynski, Bernard (2017). "Generador aleatorio de secuencia de Weyl de cuadrado medio". arXiv : 1704.00358 [cs.CR].

[35] Kneusel, Ron (2018). Números aleatorios y computadoras (1.ª ed.). Springer. pp. 13-14. ISBN 9783319776972.

[36] Cabuk, Umut Can; Aydin, Ömer; Dalkiliç, Gökhan (2017). "Un generador de números aleatorios para protocolos de autenticación ligeros: xorshiftR+". Revista turca de ingeniería eléctrica y ciencias de la computación . 25 : 4818–4828. doi : 10.3906/elk-1703-361.

[37] Blackman, David; Vigna, Sebastiano (2018). "Generadores pseudoaleatorios lineales desordenados". arXiv : 1805.01407 [cs.DS].

[38] Harase, S.; Kimoto, T. (2018). "Implementación de generadores lineales F2 de distribución máxima equidistribuida de 64 bits con período primo de Mersenne". ACM Transactions on Mathematical Software . 44 (3): 30:1–30:11. arXiv : 1505.06582 . doi :10.1145/3159444. S2CID 14923086.

[39] Widynski, Bernard (2020). "Cuadrados: un generador de números aleatorios rápido basado en contadores". arXiv : 2004.06278 [cs.DS].

[40] Generador de números aleatorios verdaderos mediante descarga de corona: Oficina de Patentes de la India. Número de solicitud de patente: 201821026766