如果给定序列,如何确定伪随机数生成器的初始值?

计算科学 随机数生成 逆问题
2021-12-08 05:52:34

假设我知道一个随机数序列是由一个线性同余生成器生成的。那是,

xn+1=(aXn+c)modm

如果给我整个周期(或至少它的一个大的连续子序列),我如何重建产生这个序列如果伪随机数生成器已知,我正在寻找一种能够确定初始参数的通用方法。a,c,mx0

1个回答

请参阅论文How to crack a Linear Congruential Generator,Haldir(“逆向工程团队”,2004 年 12 月):

在本文中,我将介绍一种解决 LCG 的所有值的方法,包括具有六个或更多连续 PRNG 输出的模数。

该论文包括用 C 语言编写的“概念证明”源代码,使用 Victor Shoup 的 NTL 进行扩展精度算术。