LCG周期与模的关系

17 2025-09-02 14:12

lcg的周期和模

线性同余生成器 (LCG) 的周期 与 模数 m 的关系一次性梳理清楚。只要记住下面两条主线即可：

加法 LCG（c≠0）——Hull-Dobell 定理
周期 = m（最大可能）的充要条件
• gcd(c, m) = 1
• 对 m 的每一个素因子 p，都有 p | (a − 1)
• 若 4 | m，则 4 | (a − 1)

此时与「原根」无关，因为序列里加入了“加法扰动” c。

乘性 LCG（c = 0）——原根登场
周期 ≤ m − 1（因为 0 一旦出现就锁死）。
若 m 为素数 p，且 a 是模 p 的原根，则周期恰为 p − 1。
若 m 为 2^k (k ≥ 3)，则周期 = 2^{k-2}（a 需满足 a ≡ 3 或 5 mod 8）。
若 m 为合数且非 2 的幂，周期 = λ(m)，其中 λ 为 Carmichael 函数；此时需要 a 与 m 互质且阶为 λ(m)。

小结一句话

有 c（加法）：用 Hull-Dobell，目标是把周期推到 m，与原根无关。
无 c（乘性）：周期上限由 m 的数论结构决定；当 m 为素数 p 时，把 a 选成 p 的原根即可让周期达到 p − 1。

这样就把「周期」和「模」的关系说全了。

为什么会有加法和乘法lcg有没有混合lcg

把问题分成三块：

为什么会有“加法”和“乘法”两条路线？
是否可以把两条路线混成一条？
如果真的混了，会得到什么？（答案：不仅存在，而且几乎全部现代 LCG 都是“混合型”。）

──────────────────

加法 vs. 乘法的历史动机

加法 LCG（c≠0）：早期硬件做乘法慢、除法更慢，于是 1960 年代的设计者（Lehmer、Greenberger 等）用“加法”来补周期。Hull-Dobell 定理保证只要满足三条简单数论条件，周期就能拉到 m，对素数或 2 的幂都管用，实现简单。
乘性 LCG（c=0）：去掉 c 后，每一步只剩一次乘法和一次模运算，速度更快，而且 0 永远不会出现（除非人为喂 0 做种子），所以 1970-1980 年代大量数值库采用它。代价是周期上限变成 m−1（或 2^{k-2}），而且选参数必须借助原根或 Carmichael 函数，数论条件更苛刻。

──────────────────
2. “混合型”其实早已是常态

从数学上讲，所有 LCG 本来就统一写成
X_{n+1} = (a·X_n + c) mod m
只是当 c=0 时大家口头叫它“乘性”，当 c≠0 时叫它“混和”或“加法”。
因此 “混合 LCG”并不是新概念，而是通用形式；真正的区别只在于设计者要不要把 c 设成 0。

──────────────────
3. 实际例子：混合 LCG 遍地都是

glibc 的 rand()：a = 1103515245，c = 12345，m = 2^31，典型的混合 LCG。
Numerical Recipes ran0/1/2 系列：c 非零，但数值很小，用来打散低位缺陷。
Java 的 java.util.Random：内部实际是 48-bit 的 LCG，c ≠ 0。
C++11 minstd_rand0：虽然名字带 minstd，其实 a = 16807，c = 0，是“乘性”特例。

──────────────────
一句话总结
“加法”与“乘法”只是参数 c 的取值不同；通用公式里 c 可以任意取，所以所有 LCG 本质上都是混合型。真正决定是否用 0 的只是性能、周期需求与数论复杂度三者的权衡。

为什么乘性法会少一个状态

根本原因只有一句：乘性 LCG 的递推式里没有“加法扰动” c，导致 0 成了一个“黑洞”状态——一旦进去就永远出不来，所以整个状态机必须主动把 0 排除，于是只剩 m−1 个可用状态。

分两步看：

为什么 0 进去就死
乘性 LCG：
X_{n+1} = (a·X_n) mod m
若某一步 X_k = 0，则
X_{k+1} = a·0 mod m = 0
X_{k+2} = 0 …
序列永远锁死在 0。因此，为了“看起来像个随机数生成器”，实现者绝不会允许 0 出现；要么把种子限制在 1…m−1，要么在检测到 0 时重新播种。
混合 LCG 为啥不怕 0
混合 LCG：
X_{n+1} = (a·X_n + c) mod m，c ≠ 0
即使 X_k = 0，下一步也会跳到
X_{k+1} = c mod m ≠ 0
于是 0 只是一个普通状态，可以被循环访问，整套状态空间 {0,1,…,m−1} 都能被遍历，周期自然就是 m。

结论：
乘性 LCG 的“少 1”不是数学上“算不出”第 m 个状态，而是为了避免 0 黑洞而主动放弃那个状态。

乘性lcg不会产生0是吗

理论上：只要初始种子 X₀ ≠ 0，乘性 LCG
Xₙ₊₁ = (a·Xₙ) mod m
永远不会出现 0。
原因：a 与 m 互质（这是 LCG 能取得最大周期的前提），于是 a 在模 m 下有乘法逆元；0 的倍数仍是 0，而任何非 0 数乘以 a 都不可能突然变成 0，因此 0 无法被“生成”。

实践中：

如果手滑把种子设成 0，或者中间计算溢出后变成 0，那么序列会立刻锁死在 0。
所以绝大多数库在初始化时都会强制把 0 替换为非 0 值，或者干脆把种子区间限制在 1 … m−1。

一句话：乘性 LCG 本身不会自然产生 0，但 0 仍是“危险输入”，需要人为堵住。

博客

LCG周期与模的关系

lcg的周期和模

小结一句话

为什么会有加法和乘法lcg有没有混合lcg

为什么乘性法会少一个状态

乘性lcg不会产生0是吗

全部评论

分类

热门文章

Tags

关于