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

Los generadores de números aleatorios son importantes en muchos tipos de aplicaciones técnicas, incluida 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 la calidad.

Generadores de números pseudoaleatorios (PRNG) [ editar ]

Siempre que utilice un generador de números pseudoaleatorios , tenga en cuenta el dicho de John von Neumann : "Cualquiera que considere métodos aritméticos para producir dígitos aleatorios está, por supuesto, en un estado de pecado". [1]

Los siguientes algoritmos son generadores de números pseudoaleatorios.

GeneradorFechaPrimeros proponentesReferenciasNotas
Método del cuadrado medio1946J. von Neumann[2]En su forma original, es de mala calidad y solo tiene interés histórico.
Generador de Lehmer1951DH Lehmer[3]Uno de los diseños más tempranos e influyentes.
Generador congruencial lineal (LCG)1958WE Thomson; A. Rotenberg[4] [5]Una generalización del generador de Lehmer e históricamente el generador más influyente y estudiado.
Generador de Fibonacci retrasado (LFG)1958GJ Mitchell y DP Moore[6]
Registro de desplazamiento de retroalimentación lineal (LFSR)1965RC Tausworthe[7]Un diseño muy influyente. También se llaman generadores Tauswort.
Generador de Wichmann – Hillmil novecientos ochenta y dosBA Wichmann y DI Hill[8]Una combinación de tres LCG pequeños, adecuada para CPU de 16 bits . Ampliamente utilizado en muchos programas, por ejemplo, se utiliza en Excel 2003 y versiones posteriores para la función RAND [9] y era el generador predeterminado en el lenguaje Python hasta la versión 2.2. [10]
Regla 301983S. Wolfram[11]Basado en autómatas celulares.
Generador congruencial inversor (ICG)1986J. Eichenauer y J. Lehn[12]
Generador Park-Miller1988SK Park y KW Miller[13]Una implementación específica de un generador de Lehmer, ampliamente utilizado porque está integrado en los lenguajes C y C ++ como la función `minstd '.
Generador de BELLOTA(descubierto 1984) 1989RS Wikramaratna[14] [15]El A dditive Co ngruential R Andom N umber generador.

Fácil de implementar, rápido, pero poco conocido. Con las inicializaciones adecuadas, pasa todas las series de pruebas empíricas actuales y se demuestra formalmente que converge. Fácil de ampliar para una duración de período arbitraria y rendimiento estadístico mejorado en dimensiones más altas y con mayor precisión.

Generador MIXMAX1991GK Savvidy y NG Ter-Arutyunyan-Savvidy[dieciséis]Es un miembro de la clase de generador congruencial lineal de matrices, una generalización de LCG. El fundamento de la familia de generadores MIXMAX se basa en los resultados de la teoría ergódica y la mecánica clásica.
Agregar con transporte (AWC)1991G. Marsaglia y A. Zaman[17]Una modificación de los generadores Lagged-Fibonacci.
Restar con pedir prestado (SWB)1991G. Marsaglia y A. Zaman[17]Una modificación de los generadores Lagged-Fibonacci. Un generador SWB es la base del generador RANLUX, [18] ampliamente utilizado, por ejemplo, para simulaciones de física de partículas.
Recíprocos máximamente periódicos1992RAJ Matthews[19]Un método con raíces en la teoría de números, aunque nunca se utilizó en aplicaciones prácticas.
BESO1993G. Marsaglia[20]Ejemplo prototípico de un generador de combinación.
Multiplicar con acarreo (MWC)1994G. Marsaglia; C. Koç[21] [22]
Complementario-multiplicar-con-acarreo (CMWC)1997R. Couture y P. L'Ecuyer[23]
Mersenne Twister (MT)1998M. Matsumoto y T. Nishimura[24]Estrechamente relacionado con las LFSR. En su implementación MT19937 es probablemente el PRNG moderno más utilizado. Generador predeterminado en R y el lenguaje Python a partir de la versión 2.3.
Xorshift2003G. Marsaglia[25]Es un subtipo muy rápido de generadores LFSR. Marsaglia también sugirió como mejora el generador xorwow, en el que la salida de un generador xorshift se agrega con una secuencia de Weyl . El generador xorwow es el generador predeterminado en la biblioteca CURAND de la interfaz de programación de aplicaciones nVidia CUDA para unidades de procesamiento de gráficos.
Bien equidistribuido lineal de largo período (BIEN)2006F. Panneton, P. L'Ecuyer y M. Matsumoto[26]Un LFSR estrechamente relacionado con Mersenne Twister, con el objetivo de remediar algunas de sus deficiencias.
Un pequeño PRNG no criptográfico (JSF)2007Bob Jenkins[27]
Sistema de aleatorización avanzado (ARS)2011J. Salmon, M. Moraes, R. Dror y D. Shaw[28]Una versión simplificada del cifrado de bloques AES , que conduce a un rendimiento muy rápido en el sistema que admite AES-NI .
Threefry2011J. Salmon, M. Moraes, R. Dror y D. Shaw[28]Una versión simplificada del cifrado de bloques Threefish, adecuada para implementaciones de GPU.
Philox2011J. Salmon, M. Moraes, R. Dror y D. Shaw[28]Una simplificación y modificación del cifrado en bloque Threefish con la adición de un S-box .
SplitMix2014GL Steele, D. Lea y CH Flood[29]Basado en la función de mezcla final de MurmurHash3. Incluido en Java Development Kit 8 y superior.
Generador congruencial permutado (PCG)2014YO O'Neill[30]Una modificación de LCG.
Generador de bits de ciclo aleatorio (RCB)2016R. Cookman[31]RCB se describe como un generador de patrones de bits creado para superar algunas de las deficiencias de Mersenne Twister y la restricción de períodos cortos / longitud de bits de los generadores de desplazamiento / módulo.
Xoroshiro128 +2018D. Blackman, S. Vigna[32]Una modificación de los generadores Xorshift de Marsaglia, uno de los generadores más rápidos en las CPU modernas de 64 bits . Los generadores relacionados incluyen xoroshiro128 **, xoshiro256 + y xoshiro256 **.
MELG de 64 bits2018S. Harase, T. Kimoto[33]Una implementación de generadores lineales F 2 equidistribuidos al máximo de 64 bits con período principal de Mersenne.

Algoritmos criptográficos [ editar ]

Los algoritmos de cifrado y los hashes criptográficos se pueden utilizar como generadores de números pseudoaleatorios de muy alta calidad. Sin embargo, generalmente son considerablemente más lentos (típicamente en un factor de 2 a 10) que los generadores de números aleatorios no criptográficos rápidos.

Éstas incluyen:

  • Flujo de cifrados . Las opciones populares son Salsa20 o ChaCha (a menudo con el número de rondas reducido a 8 para la velocidad), ISAAC , HC-128 y RC4 .
  • Bloquear cifrados en modo contador . Las opciones comunes son AES (que es muy rápido en sistemas que lo soportan 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, pero intentan vincular matemáticamente la dificultad de distinguir su salida de un flujo aleatorio "verdadero" a un problema computacionalmente difícil. Estos enfoques son teóricamente importantes, pero son demasiado lentos para ser prácticos en la mayoría de las aplicaciones. Incluyen:

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

Generadores de números aleatorios que usan entropía externa [ editar ]

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

  • /dev/random- Sistemas similares a Unix
  • CryptGenRandom - Microsoft Windows
  • Fortuna
  • Instrucciones RDRAND (llamadas Intel Secure Key de Intel ), disponibles en las CPU Intel x86 desde 2012. Utilizan el generador AES integrado en la CPU y lo reinician periódicamente.
  • Generador de números aleatorios verdaderos con descarga de corona. [34]
  • Milenrama

Servidores de números aleatorios [ editar ]

La siguiente lista (no exhaustiva) de sitios web afirma proporcionar números aleatorios generados a partir de una fuente verdaderamente aleatoria, y muchos brindan servicios adicionales de asignación al azar:

  • Universidad Nacional de Australia [35]
  • HotBits
  • Universidad Humboldt de Berlín (se requiere inscripción)
  • random.org
  • csrng.net

API PRNG conocidas [ editar ]

  • /dev/randomen sistemas similares a Unix
  • Clase aleatoria en .NET Framework
  • Clase aleatoria en el lenguaje de programación Java
  • Módulo aleatorio en las especificaciones de Haskell 98
  • Servicios de aleatorización en los idiomas Objective-C y Swift
  • Clase SecureRandom en el lenguaje de programación Java
  • API de criptografía web para navegadores web

Ver también [ editar ]

  • Diceware
  • Pruebas duras: conjunto de pruebas estadísticas para generadores de números aleatorios.
  • TestU01 : conjunto de pruebas estadísticas para generadores de números aleatorios.
  • Generador de números aleatorios de hardware
  • Ataque generador de números aleatorios
  • Aleatoriedad

Referencias [ editar ]

  1. ^ Von Neumann, John (1951). "Varias técnicas utilizadas en relación con dígitos aleatorios" (PDF) . Serie de Matemáticas Aplicadas de la Oficina Nacional de Estándares . 12 : 36–38.
  2. ^ Algunos de los artículos de von Neumann de 1949 se imprimieron solo en 1951. John von Neumann, "Varias técnicas utilizadas en relación con dígitos aleatorios", en AS Householder, GE Forsythe y HH Germond, eds., Método Monte Carlo, Oficina Nacional de Estándares Serie de matemáticas aplicadas , vol. 12 (Washington, DC: Oficina de Imprenta del Gobierno de EE. UU., 1951): págs. 36-38.
  3. ^ Lehmer, Derrick H. (1951). "Métodos matemáticos en unidades informáticas a gran escala". Actas del segundo simposio sobre maquinaria de cálculo digital a gran escala : 141-146.
  4. ^ Thomson, NOSOTROS (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 .
  5. ^ Rotenberg, A. (1960). "Un nuevo generador de números pseudoaleatorios". Revista de la ACM . 7 (1): 75–77. doi : 10.1145 / 321008.321019 .
  6. ^ DE Knuth, El arte de la programación informática, vol. 2 Seminumerical Algorithms, 3ª ed., Addison Wesley Longman (1998); Ver pag. 27.
  7. ^ 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 .
  8. ^ Wichmann, Brian A .; Hill, David I. (1982). "Algoritmo como 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 . 
  9. ^ "Soporte de Microsoft - Descripción de la función RAND en Excel" . 17 de abril de 2018.
  10. ^ "Documentación» La biblioteca estándar de Python »9. Módulos numéricos y matemáticos» 9.6. Aleatorio: generar números pseudoaleatorios " .
  11. ^ 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 .
  12. ^ Eichenauer, Jürgen; Lehn, Jürgen (1986). "Un generador de números pseudoaleatorios congruenciales no lineales". Statistische Hefte . 27 : 315–326. doi : 10.1007 / BF02932576 .
  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 .
  14. ^ Wikramaratna, RS (1989). "ACORN - Un nuevo método para generar secuencias de números pseudoaleatorios distribuidos uniformemente". Revista de Física Computacional . 83 (1): 16–31. Código Bibliográfico : 1989JCoPh..83 ... 16W . doi : 10.1016 / 0021-9991 (89) 90221-0 .
  15. ^ Wikramaratna, RS Resultados de convergencia teórica y empírica para generadores de números aleatorios congruentes aditivos, Journal of Computational and Applied Mathematics (2009), doi: 10.1016 / j.cam.2009.10.015
  16. ^ Savvidy, GK; Ter-Arutyunyan-Savvidy, NG (1991). "Sobre la simulación de Monte Carlo de sistemas físicos". Revista de Física Computacional . 97 (2): 566. Código bibliográfico : 1991JCoPh..97..566S . doi : 10.1016 / 0021-9991 (91) 90015-D .
  17. ^ a b 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 .
  18. ^ Martin, Lüscher (1994). "Un generador de números aleatorios portátil de alta calidad para simulaciones de teoría de campo de celosía". Comunicaciones de Física Informática . 79 (1): 100-110. arXiv : hep-lat / 9309020 . Código bibliográfico : 1994CoPhC..79..100L . doi : 10.1016 / 0010-4655 (94) 90232-1 .
  19. ^ Matthews, Robert AJ (1992). "Recíprocos máximamente periódicos" . Toro. Inst. Matemáticas. Apl . 28 : 147-148.
  20. ^ Marsaglia, George; Zaman, Arif (1993). "El generador KISS". Informe técnico, Departamento de Estadística, Universidad Estatal de Florida, Tallahassee, FL, EE . UU .
  21. ^ Publicación de George Marsaglia en el grupo de noticias sci.stat.math de fecha 1 de agosto de 2018 con el título ' Otro más '.
  22. ^ Koç, Cemal (1995). "Secuencias recurrentes con acarreo". Revista de probabilidad aplicada . 32 (4): 966–971. doi : 10.2307 / 3215210 . JSTOR 3215210 . 
  23. ^ Couture, Raymond; L'Ecuyer, Pierre (1997). "Propiedades de distribución de los generadores de números aleatorios multiplicar con acarreo" (PDF) . Matemáticas de la Computación . 66 Número. 218 (218): 591–607. Código Bibliográfico : 1997MaCom..66..591C . doi : 10.1090 / S0025-5718-97-00827-2 .
  24. ^ Matsumoto, M .; Nishimura, T. (1998). "MersenneTwister: generador de números pseudo aleatorios uniformes equidistribuidos dimensionalmente A623". Transacciones ACM sobre modelado y simulación por computadora . 8 (1): 3–30. CiteSeerX 10.1.1.215.1141 . doi : 10.1145 / 272991.272995 . 
  25. ^ Marsaglia, George (julio de 2003). "Xorshift RNG" . Revista de software estadístico . 8 (14). doi : 10.18637 / jss.v008.i14 .
  26. ↑ Panneton, François O .; l'Ecuyer, Pierre; Matsumoto, Pierre (marzo de 2006). "Generadores mejorados de largo período basados ​​en recurrencias lineales módulo 2" (PDF) . Transacciones ACM en software matemático . 32 (1): 1–16. CiteSeerX 10.1.1.73.5499 . doi : 10.1145 / 1132973.1132974 .  
  27. ^ Jenkins, Bob (2009). "Un pequeño PRNG no criptográfico" .
  28. ^ a b c Salmón, 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 para Computación, Redes, Almacenamiento y Análisis de Alto Rendimiento, Artículo No. 16 . doi : 10.1145 / 2063384.2063405 .
  29. ^ Steele, Guy L. Jr .; Lea, Doug; Inundación, Christine H. (2014). "Generadores de números pseudoaleatorios divisibles rápidos" (PDF) . OOPSLA '14 Actas de la Conferencia Internacional ACM 2014 sobre lenguajes y aplicaciones de sistemas de programación orientados a objetos .
  30. ^ O'Neill, Melissa E. (2014). "PCG: una familia de algoritmos estadísticamente buenos, simples, rápidos y eficientes en el espacio para la generación de números aleatorios" (PDF) . Informe técnico .
  31. ^ Cookman, Richard (2016). "generador de bits de ciclo aleatorio (rcb_generator)" . Informe técnico .
  32. ^ Blackman, David; Vigna, Sebastiano (2018). "Generadores pseudoaleatorios lineales codificados". arXiv : 1805.01407 [ cs.DS ].
  33. ^ Harase, S .; Kimoto, T. (2018). "Implementación de generadores lineales F 2 de 64 bits con máxima equidistribución con Mersenne Prime Period" . Transacciones ACM en software matemático . 44 (3): 30: 1–30: 11. arXiv : 1505.06582 . doi : 10.1145 / 3159444 .
  34. ^ Generador de números aleatorios verdaderos con descarga de corona: Oficina de patentes de la India. Número de solicitud de patente: 201821026766
  35. ^ Thomas Symul; Syed M. Assad; Ping Koy Lam (2011-06-07), "Demostración en tiempo real de generación de números aleatorios cuánticos de alta tasa de bits con luz láser coherente", Applied Physics Letters , 98 (23): 231103, arXiv : 1107.4438 , Bibcode : 2011ApPhL..98w1103S , doi : 10.1063 / 1.3597793

Enlaces externos [ editar ]

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