LCG

线性同余生成器（Linear Congruential Generator, 简称 LCG）是计算机科学中最古老且最广为人知的伪随机数生成算法之一。其核心优势在于极高的计算效率和极小的内存占用，但由于其数学特性的限制，生成的随机数序列在统计学上存在固有缺陷，不适用于密码学或高精度的科学模拟。

一、核心数学模型

LCG 基于一个简单的线性递推关系式，并通过取模运算将其结果限制在一个固定的范围内。其递推公式定义如下：

\[ X_{n+1} = (a \cdot X_n + c) \pmod m \]

参数解析：

\(X\)：伪随机数序列。
\(X_0\)：种子 (Seed)，即序列的初始值，需满足 \(0 \le X_0 < m\)。种子的选择决定了整个序列的起始点。
\(m\)：模数 (Modulus)，决定了生成随机数的最大范围（生成的数值在 \(0\) 到 \(m-1\) 之间），需满足 \(m > 0\)。通常选择 \(2\) 的幂（如 \(2^{32}\) 或 \(2^{64}\)）以便于计算机底层进行位截断优化。
\(a\)：乘数 (Multiplier)，需满足 \(0 < a < m\)。
\(c\)：增量 (Increment)，需满足 \(0 \le c < m\)。当 \(c = 0\) 时，该生成器被称为乘同余生成器 (MCG) 或 Lehmer 随机数生成器。

由于 LCG 的状态空间是有限的（最大为 \(m\)），经过一定次数的迭代后，生成的序列必然会发生重复。这个重复的间隔被称为周期。

LCG 的最大可能周期为 \(m\)。为了确保 LCG 能够达到全周期（即在重复前遍历 \(0\) 到 \(m-1\) 的所有整数），参数 \(m\)、\(a\) 和 \(c\) 必须严格满足 Hull-Dobell 定理的三个条件：

注：如果 \(c = 0\) (MCG)，则无法达到最大周期 \(m\)，其最大周期通常为 \(m-1\) 或更小，具体取决于 \(m\) 的素性。

可预测性（非密码安全）： 只要观察到序列中的连续几个输出，通过解线性同余方程组即可轻易反推算出 \(a\)、\(c\) 和 \(m\)，从而预测未来的所有随机数。
低维空间相关性 (Marsaglia 效应)：

如通过谱检验（Spectral Test）将连续的 \(k\) 个随机数作为 \(k\) 维空间中的坐标点 \((X_n, X_{n+1}, \dots, X_{n+k-1})\) 进行绘制，所有的点都会落在数量有限的平行超平面上。这意味着 LCG 在多维空间中存在严重的规律性，无法提供高质量的随机性分布。
低位周期短： 当模数 \(m\) 是 \(2\) 的幂时，生成的随机数的低位（右侧位）的周期极短且呈现明显的规律性交替（例如最低位往往是 \(0, 1, 0, 1\) 交替）。

许多经典的编程语言标准库在早期都采用了 LCG 作为默认的伪随机数生成器。以下是几个著名的参数配置：

环境 / 库	模数 (m)	乘数 (a)	增量 (c)	结果截取
glibc (C 标准库 `rand()`)	\(2^{31}\)	\(1103515245\)	\(12345\)	取位 30..16
Java (`java.util.Random`)	\(2^{48}\)	\(25214903917\)	\(11\)	取高位 (通常 32 位)
POSIX [c.1990]	\(2^{32}\)	\(1103515245\)	\(12345\)	取位 30..16
Apple CarbonLib	\(2^{31} - 1\)	\(16807\)	\(0\) (MCG)	无截取

注：现代编程语言由于对随机数质量要求的提升，已逐渐转向更先进的算法（如 Mersenne Twister、Xoshiro256 等），LCG 仅保留在对性能要求极高且对随机质量要求极低的场景中。