Generador lineal congruencial

Un generador lineal congruencial (GLC) es un algoritmo que permite obtener una secuencia de números pseudoaleatorios calculados con una función lineal definida a trozos discontinua.[1]​ La teoría que sustenta el proceso es relativamente fácil de entender, el algoritmo en sí es de fácil implementación y su ejecución es rápida, especialmente cuando el hardware del ordenador puede soportar aritmética modular al truncar el bit de almacenamiento correspondiente.(la semilla o valor inicial) son números enteros no negativos.Se dice que un generador congruencial cumple un ciclo cuando el número entero, cuando sucede esto, la secuencia de números generados se repetirá en el mismo orden.y en tal caso diremos que el generador congruencial tiene un periodo completo.Si un generador congruencial tiene un periodo completo entonces para cualquier valor que tome la semillaEl generador congruencial lineal dado por tendrá período completo[4]​[5]​ El Generador Congruencial Lineal Multiplicativo (GLMC) no cumple la primera condición, pues[aclaración requerida] Históricamente, elecciones inadecuadas llevaron a implementaciones inefectivas de GLC.Un ejemplo que ilustra esta situación es el generador RANDU, que fue ampliamente utilizado a inicios de los 1970, y ha llevado a que en la actualidad, varios resultados sean puestos en entredicho por el uso de este GLC inefectivo., porque esto permite que el operador módulo opere tan solo truncando todos los bits excepto los 32 o 64 bits más cercanos a la derecha (de hecho, esto puede lograrse simplemente al no computar en absoluto los bits más significativos).La siguiente tabla enlista los parámetros de varios GLC comúnmente usados, incluyendo las funciones "rand()" presentes en las bibliotecas runtime de varios compiladores.random0[14]​[15]​[16]​[17]​[18]​ Si Xn es par, entonces Xn+1 será impar, y viceversa—el bit más bajo oscila a cada paso.Como se puede observar, los GLC no siempre usan todos los bits en el valor que producen.Los GLC son rápidos, y requieren poca memoria (normalmente 32 o 64 bits) para retener su estado.Los GLC no deberían ser usados en aplicaciones para las que se requiera aleatoriedad de alta calidad.Por ejemplo, esta técnica es inadecuada para el uso en una simulación de Monte Carlo debido a la correlación serial de la secuencia (entre otros motivos).Tampoco deberían usarse para aplicaciones criptográficas; ejemplos de generadores más adecuados para esta función se pueden encontrar en Generador de números pseudoaleatorios criptográficamente seguro.Si un GLC es sembrado con un carácter e iterado una única vez, el resultado es un sencillo cifrado afín clásico, el cual puede ser descifrado con un análisis de frecuencia estándar.Por ejemplo, si un GLC es usado para elegir puntos en un espacio n-dimensional, los puntos yacerán ,a lo sumo, sobre (n!m)1/n hiperplanos (teorema desarrollado por George Marsaglia).Esto se debe a la correlación serial entre valores sucesivos en la secuencia Xn.En términos generales, el bit menos significativo, ocupando el lugarSin embargo, para varias aplicaciones los GLC son una buena opción.Un ejemplo puede verse en los sistemas embebidos, en los que la memoria disponible se ve severamente limitada.Varios ejemplos pueden encontrarse en la familia de generadores Xorshift.y uniformidad variada, pero no supera algunas pruebas estadísticas.[21]​ Una implementación común del Mersenne twister, usa un GLC para generar su semilla.El registro de desplazamiento con retroalimentación lineal tiene una fuerte relación con los GLCs.[23]​ Dados algunos valores en la secuencia, ciertas técnicas pueden predecir los siguientes valores en la secuencia, no solo para los GLC, sino también para cualquier otro generador congruencial polinomial.