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.
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.
Las ventajas que tiene es que es simple y fácil de implementar, mientras que 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"). Sin embargo, para criptografía y otras aplicaciones críticas, se requieren otro tipo de algoritmos mucho más robustos.
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 deba 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.