Método lineal congruente

El método congruencial lineal  es uno de los métodos para generar números pseudoaleatorios . Se utiliza en casos simples y no tiene fuerza criptográfica . Incluido en las bibliotecas estándar de varios compiladores .

Descripción

El método lineal congruente fue propuesto por D. G. Lehmer en 1949. [1] La esencia del método es calcular una secuencia de números aleatorios , asumiendo

donde  es el módulo ( número natural , con respecto al cual se calcula el resto de la división ; ),  es el multiplicador ( ),  es el incremento ( ),  es el valor inicial ( ).

Esta sucesión se llama sucesión lineal congruente . Por ejemplo, obtenemos la sucesión [2]

Propiedades

Una secuencia lineal congruente definida por los números , y es periódica con un período que no excede . En este caso, la duración del período es igual si y solo si [3] :

  1. Números y relativamente primos ;
  2. es múltiplo de todo primo que es divisor de ;
  3. múltiple , si es múltiple .

La presencia de esta propiedad para el caso donde  es el número de bits en una palabra de máquina fue demostrada por M. Greenberg . [4] La existencia de esta propiedad para el caso general y la suficiencia de las condiciones fueron probadas por TE Hull y AR Dobell . [5]   

El método para generar una secuencia lineal congruente en se denomina método congruente multiplicativo y en método congruente  mixto . Con , los números generados tendrán un período más corto que con , pero bajo ciertas condiciones, puede obtener un período de longitud , si  es un número primo . El hecho de que la condición puede conducir a la aparición de períodos más largos fue establecido por W. E. Thomson ( ing. WT Thomson ) e independientemente por A. Rotenberg ( ing. A. Rotenberg ). [2] Para garantizar el máximo ciclo de repetición de la secuencia en , es necesario elegir un número primo como valor del parámetro. El generador más famoso de este tipo es el llamado generador de números aleatorios estándar mínimo propuesto por Stephen Park y Keith Miller en 1988 . Para él , también . [6] [7]    

El método más comúnmente practicado para generar secuencias de números pseudoaleatorios es el método congruencial mixto.

Parámetros de uso común

Al elegir un número , se deben considerar las siguientes condiciones:

1) el número debe ser bastante grande, ya que el período no puede tener más elementos;

2) el valor del número debe ser tal que se pueda calcular rápidamente.

En la práctica, al implementar el método, según las condiciones especificadas, la mayoría de las veces elige , donde  es el número de bits en la palabra de la máquina . Al mismo tiempo, se debe tener en cuenta que los bits menos significativos de los números aleatorios así generados muestran un comportamiento que dista mucho de ser aleatorio, por lo que se recomienda utilizar únicamente los bits más significativos. Esta situación no se presenta cuando , donde  es la longitud de una palabra de máquina. En este caso, los bits inferiores se comportan de forma tan aleatoria como los superiores. [2] La elección del multiplicador y del incremento se debe principalmente a la necesidad de cumplir la condición para alcanzar el período de duración máxima.

Tabla de buenas constantes para generadores lineales congruentes

Todas las constantes anteriores aseguran el funcionamiento del generador con un período máximo. La tabla está ordenada por el producto más grande que no causa desbordamiento en una palabra de la longitud especificada. [ocho]

se desborda en a C metro
2 20 106 1283 6075
2 21 211 1663 7875
222 _ 421 1663 7875
2 23 430 2531 11979
2 23 936 1399 6655
2 23 1366 1283 6075
2 24 171 11213 53125
2 24 859 2531 11979
2 24 419 6173 29282
2 24 967 3041 14406
2 25 141 28411 134456
2 25 625 6571 31104
2 25 1541 2957 14000
2 25 1741 2731 12960
2 25 1291 4621 21870
2 25 205 29573 139968
2 26 421 17117 81000
2 26 1255 6173 29282
2 26 281 28411 134456
2 27 1093 18257 86436
2 27 421 54773 259200
2 27 1021 24631 116640
2 28 1277 24749 117128
2 28 2041 25673 121500
2 29 2311 25367 120050
2 29 1597 51749 244944
2 29 2661 36979 175000
2 29 4081 25673 121500
2 29 3661 30809 145800
2 30 3877 29573 139968
2 30 3613 45289 214326
2 30 1366 150889 714025
2 31 8121 28411 134456
2 31 4561 51349 243000
2 31 7141 54773 259200
2 32 9301 49297 233280
2 32 4096 150889 714025
2 33 2416 374441 1771875
2 34 17221 107839 510300
2 34 36261 66037 312500
2 35 84589 45989 217728

El algoritmo RANDU "infructuoso" (en términos de la calidad de la secuencia de salida) , que se ha utilizado en varios compiladores durante muchas décadas, es infame.

Para mejorar las propiedades estadísticas de una secuencia de números, muchos generadores de números pseudoaleatorios usan solo un subconjunto de los bits de resultado. Por ejemplo, el estándar ISO/IEC 9899 C proporciona (pero no especifica como obligatorio) un ejemplo de una función rand() que obliga a descartar los 16 bajos y un dígito alto.

#definir RAND_MAX 32767 static unsigned long int next = 1 ; int rand ( vacío ) { siguiente = siguiente * 1103515245 + 12345 ; return ( int sin firmar ) ( siguiente / 65536 ) % ( RAND_MAX + 1 ); } void srand ( semilla int sin firmar ) { siguiente = semilla ; }

Así es como se usa la función rand() en los compiladores Watcom C/C++ . Se conocen los parámetros numéricos de otros algoritmos utilizados en varios compiladores y bibliotecas.

Fuente metro factorizar un término c brocas usadas
Recetas numéricas [9] 2 32 1664525 1013904223
Borland C/C++ 2 32 22695477 una bits 30..16 en rand() , 30..0 en lrand()
glibc (utilizado por GCC ) [10] 2 31 1103515245 12345 bits 30..0
ANSI C : Watcom , Digital Mars , CodeWarrior , IBM VisualAge C/C++ [11] 2 31 1103515245 12345 bits 30..16
C99 , C11 : Sugerencia en ISO/IEC 9899 [12] 2 32 1103515245 12345 bits 30..16
Borland Delphi , Virtual Pascal 2 32 134775813 una bits 63..32 de (semilla * L)
Microsoft Visual/C rápido/C++ 2 32 214013 ( 343FD16 ) 2531011 (269EC3 16 ) bits 30..16
Microsoft Visual Basic (6 y anteriores) [13] 2 24 1140671485 (43FD43FD 16 ) 12820163 (C39EC3 16 )
RtlUniform de la API nativa [14] 2 31 − 1 2147483629 (7FFFFED 16 ) 2147483587 (7FFFFFC3 16 )
Apple CarbonLib , C++11 [ minstd_rand015] 2 31 − 1 16807 0 ver MINSTD
C++11 [ minstd_rand15] 2 31 − 1 48271 0 ver MINSTD
MMIX por Donald Knuth 264 _ 6364136223846793005 1442695040888963407
nueva biblioteca 264 _ 6364136223846793005 una bits 63…32
MTH$RANDOM de VAX , [16] versiones antiguas de glibc 2 32 69069 una
Java 248 _ 25214903917 once bits 47…16
Anteriormente en muchos compiladores:
RANDU 2 31   65539 0

Posibilidad de uso en criptografía

Aunque el método de congruencia lineal genera una secuencia pseudoaleatoria estadísticamente buena de números, no es criptográficamente seguro. Los generadores basados ​​en el método de congruencia lineal son predecibles, por lo que no se pueden utilizar en criptografía. Los generadores lineales congruentes fueron pirateados primero por Jim Reeds y luego por Joan Boyar. También logró abrir generadores cuadráticos y cúbicos. Otros investigadores han ampliado las ideas de Boyar al desarrollar formas de romper cualquier generador de polinomios. Así, se demostró la inutilidad de los generadores basados ​​en métodos congruentes para la criptografía. Sin embargo, los generadores congruentes lineales siguen siendo útiles para aplicaciones no criptográficas como la simulación. Son efectivos y muestran un buen desempeño estadístico en la mayoría de las pruebas empíricas utilizadas [8] .

Véase también

Notas

  1. ↑ D.H. Lehmer, Métodos matemáticos en unidades informáticas a gran escala, Actas de un segundo simposio sobre maquinaria de cálculo digital a gran escala, 1949, Harvard University Press, Cambridge, Mass., 1951, págs. 141-146. MR 0044899 (13,495f) [1] Archivado el 24 de diciembre de 2013 en Wayback Machine .
  2. ↑ 1 2 3 Donald Knuth . Volumen 2. Métodos Derivados // El Arte de Programar. Decreto. Op. - S. 21-37.
  3. ↑ D. E. Knut, El arte de la programación. Volumen 2. Métodos derivados - Williams. 2001. págs. 21-37
  4. ↑ M. Greenberger, Método en aleatoriedad, Comm. ACM 8 (1965), 177-179. [2] Archivado el 24 de diciembre de 2013 en Wayback Machine .
  5. ↑ TE Hull y AR Dobell "Random Number Generators", SIAM Review 4-3(1962), 230-254 [3] Archivado el 24 de diciembre de 2013 en Wayback Machine .
  6. ↑ "D.M. Bucknell. Algoritmos fundamentales y estructuras de datos en Delphi. Biblioteca del programador. 2002. Revista Delphi Informant. Capítulo 6.
  7. ↑ Stephen K. Park y Keith W. Miller (1988). Generadores de números aleatorios: los buenos son difíciles de encontrar. Communications of the ACM 31 (10): 1192-1201 [4] Archivado el 4 de abril de 2019 en Wayback Machine .
  8. ↑ 1 2 Bruce Schneier . Capítulo 16. // Criptografía aplicada. Triumph. 2002. Decreto. Op. — P. 275. [5] Archivado el 28 de febrero de 2014 en Wayback Machine .
  9. ↑ Recetas numéricas en C. El arte de la computación científica. 2ª edición. - Cambridge University Press, 1992. - 925 págs.
  10. ↑ El rand() de la biblioteca C de GNU en stdlib.h usa un generador congruencial lineal simple (estado único) solo en caso de que el estado se declare como 8 bytes. Si el estado es más grande (una matriz), el generador se convierte en un generador de retroalimentación aditiva y el período aumenta. Ver el código simplificado Archivado el 2 de febrero de 2015 en Wayback Machine que reproduce la secuencia aleatoria de esta biblioteca.
  11. ↑ Una colección de generadores de números pseudoaleatorios seleccionados con estructuras lineales, K. Entacher, 1997 . Consultado el 16 de junio de 2012. Archivado desde el original el 5 de junio de 2013.
  12. ↑ Último borrador de comité público del 12 de abril de 2011, página 346f . Consultado el 21 de diciembre de 2014. Archivado desde el original el 25 de diciembre de 2021.
  13. ↑ Cómo Visual Basic genera números pseudoaleatorios para la función RND . Soporte técnico de Microsoft . Microsoft. Consultado el 17 de junio de 2011. Archivado desde el original el 17 de abril de 2011.
  14. ↑ A pesar de la documentación en MSDN Archivada el 8 de marzo de 2016 en Wayback Machine , RtlUniform usa LCG, y no el algoritmo de Lehmer, las implementaciones anteriores a Windows Vista son defectuosas, porque el resultado de la multiplicación se corta a 32 bits, antes de que se aplique el módulo
  15. ↑ 12 ISO/IEC 14882 :2011 . ISO (2 de septiembre de 2011). Consultado el 3 de septiembre de 2011. Archivado desde el original el 17 de mayo de 2013.
  16. ↑ Biblioteca científica GNU: Otros generadores de números aleatorios . Fecha de acceso: 10 de enero de 2015. Archivado desde el original el 11 de diciembre de 2014.

Literatura

  • Donald E. Knuth . Capítulo 3. Números aleatorios // El arte de la programación informática. - 3ra ed. - M. : Williams , 2000. - V. 2. Algoritmos obtenidos. — 832 pág. - 7000 copias.  - ISBN 5-8459-0081-6 (ruso) ISBN 0-201-89684-2 (inglés).

Enlaces