Post

使用Transformer学习伪随机数：置换同余生成器、课程与可解释性

Posted
By xiaoxiang
views 15 min read
使用Transformer学习伪随机数：置换同余生成器、课程与可解释性

论文信息

标题: Learning Pseudorandom Numbers with Transformers: Permuted Congruential Generators, Curricula, and Interpretability

作者: Tao Tao, Maissam Barkeshli

发布日期: 2025-10-30

arXiv ID: 2510.26792v1

PDF链接: 下载PDF

Transformer破解伪随机数生成器：PCG学习能力与内在机制解析

论文背景与研究动机

伪随机数生成器(PRNG)是现代计算系统的核心组件，广泛应用于密码学、模拟仿真和机器学习等领域。传统的线性同余生成器(LCG)虽然结构简单，但因其可预测性而存在安全隐患。置换同余生成器(PCG)作为LCG的增强版本，通过引入比特位移、异或操作、循环移位和截断等非线性变换，显著提高了随机性和安全性。

这篇论文的研究动机源于对Transformer模型推理能力的深入探索。随着大语言模型在各类序列任务中展现出惊人能力，一个自然的问题是：这些模型能否识别和学习高度结构化的伪随机序列模式？特别是对于设计上抵抗传统密码学攻击的PCG算法，Transformer是否能够突破其防御机制？

研究团队选择PCG作为研究对象具有重要理论价值：PCG结合了线性变换的简单性和非线性操作的复杂性，为研究模型在混沌与秩序边界的学习能力提供了理想测试平台。同时，这一研究对理解模型泛化能力、课程学习机制以及表示学习的本质都具有重要意义。

核心方法和技术细节

PCG算法结构分析

PCG家族算法在传统LCG的基础上增加了复杂的后处理步骤。基础LCG的递推公式为：

1

Xₙ₊₁ = (aXₙ + c) mod m

其中a为乘数，c为增量，m为模数。PCG在此基础上增加了：

  • 比特位移操作：改变数值的二进制表示结构
  • 异或运算(XOR)：引入非线性特性
  • 循环移位：保持比特数量不变的情况下重新排列
  • 输出截断：仅保留部分比特作为输出，隐藏内部状态

这些操作使得从输出序列推断初始种子或内部状态变得极为困难，远超传统LCG的可预测性范围。

Transformer模型架构与训练策略

研究采用了标准Transformer架构，但针对数值序列预测任务进行了优化：

  • 模型规模：参数规模从数百万到5000万，适应不同复杂度的PCG变体
  • 输入表示：整数输入通过嵌入层映射到高维空间，保留数值关系
  • 训练数据：使用高达50亿个令牌的大规模数据集，覆盖多种PCG变体
  • 课程学习：采用渐进式训练策略，从小模数开始逐步过渡到大模数

关键技术挑战与解决方案

状态空间爆炸问题：当模数m达到2²²时，可能的内部状态数量超过400万。研究通过注意力机制的并行处理能力和位置编码的时间依赖性建模来解决这一问题。

信息损失补偿：当输出被截断至单个比特时，模型需要从极有限的信息中重建完整状态。Transformer利用其强大的序列建模能力，通过多个时间步的累积证据进行概率推理。

多任务联合学习：当训练数据包含多个不同的PRNG时，模型需要同时学习多种生成规则。研究发现Transformer能够自动识别不同算法的结构特征，并在推理时正确应用相应规则。

创新点和贡献

理论创新

  1. 超越传统攻击的能力：证明了Transformer能够破解那些抵抗已知经典密码学分析的PCG变体，揭示了深度学习在密码分析中的新潜力。

  2. 缩放定律的发现：首次量化了模型预测能力与PCG模数之间的关系，提出了近乎完美预测所需上下文长度与√m成正比的缩放定律。

  3. 课程学习的必要性证明：通过系统实验证明，对于大模数(m ≥ 2²⁰)的学习，必须采用从小模数开始的课程学习策略，否则优化过程会陷入长期停滞。

技术突破

  1. 单比特预测的可行性：即使输出被截断至单个比特，Transformer仍能可靠预测后续序列，这一发现对随机性测试和密码分析具有重要意义。

  2. 多PRNG联合学习机制：模型能够同时学习多个不同的伪随机数生成算法，并根据上下文自动选择适用规则，展示了出色的模式分离能力。

  3. 旋转不变聚类现象：在嵌入层发现了新颖的表示学习行为——模型自发地将整数输入组织成比特旋转不变的簇，揭示了知识从小模数向大模数迁移的机制。

实验结果分析

预测准确性与缩放行为

实验结果显示，Transformer在不同PCG变体上都达到了接近完美的预测准确率。特别值得注意的是预测性能与模数大小的关系：当模数m增加时，模型需要更多的上下文元素才能达到高准确率，且这一需求按照√m的比例增长。

例如，对于m=2¹⁰，仅需要约32个上下文元素；而对于m=2²⁰，则需要约1024个元素。这一发现不仅具有理论价值，还为实际应用中模型规模和训练数据的配置提供了指导。

课程学习的关键作用

在没有课程学习的情况下，直接训练模型学习大模数PCG(m ≥ 2²⁰)会导致优化过程陷入数天甚至数周的停滞期。而采用渐进式课程学习——先训练小模数，然后逐步增大——能够将训练时间缩短数个数量级。

这一现象表明，PCG学习任务具有明显的层次结构特性，小模数问题的解决方案为更大模数问题提供了必要的先验知识和表示基础。

表示学习的可解释性发现

通过对嵌入层的可视化分析，研究人员发现了令人惊讶的聚类模式：模型自发地将数值组织成基于比特旋转不变性的簇。这意味着模型学会了识别那些通过循环移位相互转换的数值，从而构建了对PCG操作的内在理解。

这种表示不仅高效，而且具有强大的泛化能力。当面对训练中未见的大模数时，模型能够利用已学习的旋转不变性概念快速适应新的数值范围。

实践应用建议和未来发展方向

在量化交易中的应用

伪随机数生成在金融模拟和算法交易中具有重要作用：

  • 随机性检验：使用类似技术检验交易策略中使用的随机数生成器的质量，避免因伪随机算法的缺陷导致策略失效
  • 市场模拟：基于PCG的Transformer模型可以用于生成更真实的市场数据模拟，捕捉市场微观结构中的复杂模式
  • 风险建模：改进蒙特卡洛模拟中的随机数生成，提高风险度量的准确性

在密码安全领域的应用

  • 密码强度评估：开发基于Transformer的密码分析工具，评估现有PRNG算法的实际安全性
  • 随机性测试增强：将学习到的特征纳入传统随机性测试套件(如NIST测试)，提高对弱随机性的检测能力
  • 后量子密码学：为后量子密码系统的随机数需求提供新的安全评估框架

在人工智能系统中的应用

  • 数据增强：利用可控的伪随机序列生成进行更有效的训练数据增强
  • 强化学习：改进环境随机性建模，提高智能体在随机环境中的泛化能力
  • 联邦学习：开发更安全的随机数共享协议，保护隐私的同时维持系统随机性需求

未来研究方向

  1. 扩展到更复杂的PRNG：研究Transformer对密码学安全PRNG(如ChaCha20、AES-CTR)的学习能力
  2. 理论分析深化：从计算复杂性理论角度分析Transformer学习PRNG的极限能力
  3. 防御技术开发：基于研究结果设计抵抗深度学习攻击的新型PRNG
  4. 脑启发计算：将发现的表示学习机制应用于更广泛的序列处理任务

总结与展望

本研究通过系统实验证明，Transformer模型能够学习包括PCG在内的复杂伪随机数生成算法，甚至在输出被严重截断的情况下仍能保持预测能力。研究揭示了几个关键发现：预测难度与模数平方根成正比的缩放定律、课程学习在大模数学习中的必要性，以及模型自发形成的比特旋转不变表示。

这些发现不仅对理解Transformer的推理机制具有重要意义，也为多个领域的实际应用提供了新思路。在量化交易中，可以用于开发更可靠的随机模拟系统；在密码学中，为随机性测试和安全评估提供了新工具；在人工智能领域，增进了我们对模型泛化能力和表示学习的理解。

展望未来，随着模型规模的进一步扩大和训练技术的持续改进，深度学习模型有望在更复杂的密码分析任务中发挥作用。同时，这一研究方向也催生了新的安全问题——如何设计抵抗智能体学习的随机数生成器将成为后量子时代的重要课题。这项研究为人工智能与密码学的交叉领域奠定了坚实基础，开辟了富有前景的研究方向。

This post is licensed under CC BY 4.0 by the author.