现代编程语言,大都在标准库中包含了随机库。例如,C++ 在 C++11 标准中添加了 random
头文件,提供了现代的随机库;Python 则有 random。C++11 的随机库将生成随机数的过程在逻辑上切分成了两个步骤:随机数生成引擎和分布。在学习 C++11 的 random
库时,std::mt19937
这一随机数生成引擎的名字看起来十分奇怪,成功吸引了我的注意力。
查询后得知,std::mt19937
中的 MT 是 Mersenne Twister 的缩写,这是伪随机数生成算法的名字(梅森旋转算法);而 19937 则取自算法中用到的梅森素数 $2^{19937} - 1$。这里,梅森素数是算法生成伪随机数的循环长度(period),而旋转则说的是算法内部对定长二进制串循环位移的过程。
此篇讲解梅森旋转算法的一些原理,并介绍对其的一个「爆破」方法。