📚 课程目录第2章随机数生成器基础与分类

2. 随机数生成器基础与分类

在仿真、密码学、统计抽样和蒙特卡洛计算中，“随机数”几乎无处不在。但不同场景对随机性的要求并不相同：密码系统要求不可预测，统计模拟要求分布均匀且可复现，数值积分则更关心样本在空间中的覆盖质量。因此，随机数生成器（Random Number Generator，RNG）并不是单一技术，而是一类按原理和目标划分的工具族。本节围绕三类生成器——真随机数生成器（TRNG）、伪随机数生成器（PRNG）与准随机数生成器（QRNG）——比较其原理、典型算法与适用边界，并给出可操作的选型依据。

三类生成器的原理差异

真随机数生成器从物理熵源提取随机性，例如热噪声、环形振荡器的相位抖动、光子到达时间或放射性衰变。其输出不可预测、不可复现，理论上不依赖算法。工程上通常把物理熵源与后处理电路（如去偏、白化、健康检测）组合，形成真随机数模块。TRNG 的瓶颈在于速率较低、成本较高，且输出质量依赖熵源状态，需要在线健康测试来发现熵源失效。

伪随机数生成器是确定性算法：给定种子，输出序列完全确定。它通过有限状态机迭代产生看似随机的比特流，周期长度、均匀性和不可预测性由算法与状态空间决定。PRNG 速度快、可复现、易于移植，是仿真与统计计算的主力；但它不具备信息论意义上的随机性，种子泄露或状态被恢复即可预测后续输出。

准随机数生成器并不追求“像随机”，而是刻意构造低差异序列，使样本点在单位超立方体中尽可能均匀分布。Halton、Sobol、Faure 等序列属于此类。QRNG 的确定性更强，单点看不出随机性，但用于数值积分时收敛速度往往优于伪随机抽样。它不适合需要不可预测性的场景，也不适合直接当作独立同分布样本做统计推断。

典型算法：线性同余与梅森旋转

线性同余生成器（LCG）是最经典的 PRNG，递推式为 x_n+1 = (a·x_n + c) mod m。其中 m 为模数，a 为乘子，c 为增量，x₀ 为种子。它的优点是实现极简、速度快，适合资源受限环境；缺点是低位随机性差、周期受参数选择影响大，且高维分布会出现明显的晶格结构。经典参数如 m = 2³¹、a = 1103515245、c = 12345 常见于教学与旧式库中，但不宜用于高维蒙特卡洛或对统计质量要求较高的场合。

梅森旋转（Mersenne Twister，MT19937）是应用最广的 PRNG 之一，状态空间为 19937 位，周期为 2¹⁹⁹³⁷−1，具有很好的均匀性和高维分布性质，Python 的 random 模块、MATLAB 的默认随机流、许多 C++ 实现都曾以它为默认引擎。其核心是通过状态数组的旋转与 tempering 变换产生 32 位输出。MT19937 的短板在于状态较大、初始化成本较高，且不具备密码学安全性——观测到 624 个连续输出即可恢复内部状态，因此不能用于密钥生成或安全令牌。

下面给出一个可直接运行的最小示例，用固定种子观察 LCG 与 MT19937 的可复现性差异（示例参数与输出为教学演示，非实测数据）：

# 线性同余：x_{n+1} = (a*x_n + c) mod m
def lcg(seed, n, a=1103515245, c=12345, m=2**31):
    x = seed
    out = []
    for _ in range(n):
        x = (a * x + c) % m
        out.append(x / m)      # 归一化到 [0,1)
    return out

# 梅森旋转：Python 内置实现
import random
random.seed(20240501)
mt = [random.random() for _ in range(5)]

print([round(v, 4) for v in lcg(20240501, 5)])
print([round(v, 4) for v in mt])
# 同一 seed 重复运行，两组输出完全一致 → 可复现

运行后应观察到：同一 seed 下两次运行结果逐位相同，这正是 PRNG 可复现性的体现。若把 seed 换成系统时间或熵源输出，序列就不可复现，但依然不是真随机——只是种子不可预知而已。这一点在仿真实验中非常关键：报告结果时应记录种子，否则他人无法复现你的实验。

如何选择：按目标而非按名气

选型的第一问不是“哪个算法最好”，而是“我要的随机性用来做什么”。若目标是不可预测（密钥、令牌、抽奖公证），必须使用 TRNG 或经密码学强化的 PRNG（如基于 ChaCha20 的 DRBG），普通 PRNG 一律不合格。若目标是可复现的统计模拟（蒙特卡洛、排队仿真、随机测试），应选择周期足够长、统计性质良好的 PRNG，如 MT19937 或 PCG 系列，并固定种子、记录引擎类型。若目标是高维数值积分或空间均匀采样，QRNG 的低差异序列通常能以更少样本达到同等精度，但要注意它不满足独立同分布假设，不能直接套用基于 i.i.d. 的置信区间公式。

实践建议：在仿真项目中同时记录“引擎名称 + 种子 + 样本数量”三项元数据。若使用 QRNG，还应记录序列类型与维度，因为 Sobol 序列在高维下需要跳过前若干点（burn-in）以改善均匀性。

常见误区：把 MT19937 当作“真随机”用于生成密码或会话令牌。MT19937 的输出可被状态恢复攻击预测，安全场景应使用操作系统提供的密码学安全随机源，如 secrets 模块或 /dev/urandom。

最后需要强调，三类生成器并非互相替代，而是常组合使用：用 TRNG 产生种子，喂给 PRNG 产生高速长序列；在需要均匀覆盖的积分任务中，用 QRNG 生成样本点，再用随机化（如随机平移、随机置换）消除序列的规则性偏差。理解每种生成器的“随机性来源”和“失效边界”，比记住某个算法名字更重要。