伪随机生成器

PRG 用一小段真正随机的均匀种子确定性扩展出更长比特串；输出并非“数学上随机”，而是要求任何高效测试都找不到可利用的偏差，无法将其与真正均匀串区分。信息论上它不可能均匀：输出支持集最多 $2^s$，远小于 $2^m$，安全完全依赖区分器无法高效识别这个稀疏集合。stretch 必须为正且通常为多项式，重复调用或扩展要保持整体不可区分。

线性同余发生器可通过线性关系被高效区分，不是密码学 PRG。把一个安全 PRG 的前缀直接公开并不必然泄漏其余位，正式结论需由不可区分混合论证给出。固定或低熵种子不符合定义；即使算法本身正确，重复种子也会重复全部输出。伸长必须超过种子长度，否则恒等映射会使定义失去生成随机性的意义。

若 $G:\{0,1{\}}^s\to \{0,1{\}}^{2s}$ 安全，则给定 $G(U_s)$ 或 $U_{2s}$，任何多项式算法只能以可忽略优势判断来源。简单输出 $G(x)=x\Vert x$ 显然不安全，区分器检查两半是否相等即可。

统计测试通过不是密码学证明；攻击者可利用任意高效结构。种子若低熵、重复或泄露，输出不再保密；普通模拟/游戏 PRNG 也未必达到密码学不可预测性。有种子提取器公理库有种子随机性提取器Seeded randomness extractor · Seeded extractor用独立均匀短种子把任意高最小熵弱源映为统计上接近均匀的输出。处理的是另一方向：它用独立均匀短种子净化较长的 min-entropy 弱源，输出通常更短但统计接近均匀；PRG 不能因输入“有一些熵”就替代 extractor。

PRG 把少量随机位扩展成流密码、其他密码原语和随机化算法去随机化所需的伪随机资源，也是计算安全公理库计算安全Computational security仅要求任何资源受限攻击者的成功优势足够小的安全概念。与信息论安全分界的典型对象。其存在与 单向函数公理库单向函数One-way function易于正向计算，但随机输入所产生的像难以被任何高效算法反演的函数族。的存在等价（标准理论意义），计算不可区分性公理库不可区分性Computational indistinguishability任意高效判别器区分两个分布族的优势都是可忽略量。给出安全目标；GGM 构造由 PRG 得 PRF公理库伪随机函数Pseudorandom function · PRF由短密钥索引且对高效查询者不可与真随机函数区分的函数族。，流密码、随机性扩展和去随机化都把短真随机种子转为长伪随机资源。提取器的统计误差与剩余哈希引理公理库剩余哈希引理Leftover hash lemma · LHL随机二通用哈希把高最小熵源压缩为即使公开哈希种子仍统计接近均匀的输出。属于弱源净化主线，不是 PRG stretch 的证明。