梅森旋转算法是一种好的二进制随机数生成器吗？

Question

我试图寻找一种RNG来生成伪随机位流。我发现Mersenne Twister（MT19937）是一种广泛使用的RNG，可以生成良好的32位无符号整数，并且已经实现了生成表面上好的双精度浮点数（生成53位整数）。但是，在位方面上，我似乎找不到任何关于它表现良好的参考资料。Marsaglia提出了有关Mersenne Twister随机性的一些问题，这让我对使用它产生怀疑。

是否有人知道Mersenne Twister在生成伪随机位时是否存在显著偏差？如果是这种情况，有没有人知道一个好的伪随机位生成器？

- Wilhelm

---

如果没有外部种子或抓取数字等外部来源，这个方法可能就可以了。而且计算速度也相当快，这是一个优点。我曾经工作的公司都使用它，所以这也是一个背书。你为什么担心它有多随机呢？你在做什么呢？ - Michael Dorgan

据我所知，它不应该用于统计/高安全性的事情，但对于大多数用途来说，它足够快且相当随机。(尽管根据维基百科文章，显然有更好的PRNGs比如“乘法进位”更快...如果我没记错的话。)它的初始值更接近于0，但经过一堆迭代后，它变得相当随机。 - Mateen Ulhaq

我想修改我的评论：Mersenne Twister 不适用于加密目的，但适用于蒙特卡罗方法。 - Mitch Wheat

好的。NO MT是一种糟糕的算法。推荐的方法是“自己动手写”。 - bobobobo

有比机器翻译更好的算法适用于几乎任何目的，但是如果不知道您打算使用的目的，我无法推荐其中一个。 - Lee Daniel Crocker

Answer 1

所有伪随机生成器都要求每一位都有高度的不可预测性。目前并没有办法能够在观察到624个值之前显著地优于随机情况预测梅森旋转算法的每一位。

所有形如“X随机数产生器好不好”这样的问题必须回答“你打算用它做什么？”梅森旋转算法在模拟方面取得了巨大的成功，因为它能够产生出极佳的频率分布。但在密码学中，它完全没有任何价值。通过连续观察624个输出，其内部状态就能被确定。布隆布隆沙布在密码学情景下表现非常强大，但在模拟中运行速度不理想。

- Cort Ammon

Answer 2

不推荐使用Mersenne Twister

除非是内置的，否则没人应该选择Mersenne Twister来生成随机数；而且如果您需要广泛地使用随机数，那么您应该替换它。Mersenne Twister未能通过基本的统计随机性测试，而那些更简单、更快的算法可以通过这些测试，并且通常都更可靠。

我目前推荐的不安全、非加密伪随机数生成器包括xoroshiro+和PCG family。xoroshiro+速度更快，质量稍微高一些，但PCG家族提供了更完整的库并可以扮演更多的角色。

然而，现代加密随机数生成器足够快。Rust的rand库默认使用ISAAC算法，也可以使用其他算法。在绝大部分情况下，这应该是您的默认选择。

- Veedrac