El Generador Lineal Congruencial (LCG, Linear Congruential Generator) es un algoritmo de números pseudoaleatorios que tiene la particularidad de ser fácil de implementar y reproducible ya que con la misma semilla siempre se obtiene la misma secuencia. Se denomina Lineal porque utiliza como base la ecuación de primer grado del estilo y = mx + b y Congruencial debido a que aprovecha la operación modular, habilitando la "congruencia" entre varios números, es decir, pueden tener el mismo resto o residuo al dividir por otro número específico.
Fue introducido en los años 1950 por Derrick Henry Lehmer y otros matemáticos como una forma práctica de producir secuencias de números “aleatorios” en computadores de la época.
Como se mencionó anteriormente, las ventajas que tiene este algoritmo es que es simple y fácil de implementar, sin embargo, si se eligen incorrectamente los valores el ciclo de repetición de los números es corto y con mala distribución.
Ha sido utilizado en diferentes aplicaciones, siendo la más conocida el juego Freecell de Microsoft en sus primeras versiones (con 32.000 juegos o "semillas"). Para criptografía y otras aplicaciones críticas, se requieren otro tipo de algoritmos mucho más robustos que el LCG.
Consta de la siguiente fórmula:
xn+1 = (a * xn + c) mod m
Donde:
x = Número aleatorio.
a, c, m = Constantes del modelo.
n = Iteración.
Este algoritmo funciona con un valor "semilla", es decir, un x0 que puede ser cualquier valor entero. Para obtener una buena "performance" de este algoritmo, es decir, garantizar que el LCG tenga un ciclo completo, o sea, recorrer todos los valores antes de repetirse, es útil de que:
- c y m deban ser coprimos.
- a - 1 debe ser divisible por todos los factores primos de m.
- Si m es múltiplo de 4, entonces a − 1 debe ser múltiplo de 4.
Estas condiciones son probadas mediante el Teorema de Hull - Dobell.
Ejemplo práctico
Establecer un LCG que genere números aleatorios entre 1 y 10. En este caso tomaremos un a de 2 y un m de 11, ya que, ambos son coprimos, y además, con un c de 3, la multiplicación y la suma la hacen fácil.
x0 = 1 => Semilla
x1 = (2 * 1 + 3) mod 11 = 5
x2 = (2 * 5 + 3) mod 11 = 2
x3 = (2 * 2 + 3) mod 11 = 7
x4 = (2 * 7 + 3) mod 11 = 6
x5 = (2 * 6 + 3) mod 11 = 4
x6 = (2 * 4 + 3) mod 11 = 0 => Recalcular, ya que está fuera de rango
x7 = (2 * 0 + 3) mod 11 = 3
x8 = (2 * 3 + 3) mod 11 = 9
x9 = (2 * 9 + 3) mod 11 = 10
x10 = (2 * 10 + 3) mod 11 = 1 => Vuelve al inicio, x10 = x0
Si escogemos, en este ejemplo una semilla de 8, el algoritmo queda en un bucle infinito, sin despegarse del número 8. Es un punto fijo. Por lo tanto, no conviene utilizarlo para esta situación.