为什么谷歌浏览器的Math.random数字生成器不是那么随机？

Question

今天在各种浏览器上运行单元测试时，我遇到了一个奇怪的“错误”。我以前在Firefox和IE上运行过这些测试，但显然还没有在Chrome（v19-dev）上运行。在Chrome中进行测试时，由于我计算的两个值不匹配，其中一个测试始终失败。

当我深入研究发生的情况时，我意识到问题在于，我假设如果我用100,000个 Math.random() 值填充一个数组，它们都将是唯一的(不会有任何碰撞)。结果在Chrome上并非如此。

在Chrome中，我始终从 100,000 个数中至少获得了两个匹配的值。Firefox 和 IE9 从未遇到碰撞。这里是我专门为测试编写的 jsfiddle，创建了包含1M个 Math.random() 条目的数组：http://jsfiddle.net/pseudosavant/bcduj/ 有人知道为什么 Chrome 用于 Math.random 的伪随机数生成器实际上并不是那么随机吗？看起来，这可能会对任何客户端 JS 加密程序使用 Math.random 的影响。

- pseudosavant

---

存在重复并不意味着缺乏随机性。参见：http://zh.wikipedia.org/wiki/生日悖论 - Oliver Charlesworth

当然，伪随机生成器根据定义完全不是随机的。 - Oliver Charlesworth

@NayukiMinase：Math.random() 生成双精度浮点数，但 OP 的等式测试首先将这些数字转换为字符串，因此除非浏览器决定在其字符串表示中包括十五个小数点后面的更多位数，否则 OP 正在比较的值的熵要远远小于那个。 - ruakh

@delnan：您误读了您链接的答案。根据那个答案，100.0和100.1之间大约有7,036,874,417,766个双精度浮点数。在0.0和1.0之间，大约有2的62次方个双精度浮点数。 - ruakh

@pseudosavant：你确定吗？我本以为将 5555555.5555555555555 转为字符串可能包括相似数量的有效数字，且小数点后的位数比 5.5555555555555 要少。 - ruakh

Answer 1

显然，V8中的Math.random()仅适用于32位值（过去甚至没有正确随机化所有这些值）。 当使用32位时，碰撞的概率在2^16 = 65k个值左右达到50％...

- Michael Borgwardt

---

这个问题在另一个漏洞报告中更直接地得到了解决。 - Olathe

Answer 2

请见 https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d：

如果我们独立分析第一个子生成器，我们会发现它有32位的内部状态。它不是一个完整的循环发生器 - 它的实际循环长度约为5.9亿（18,030*2¹⁵-1，数学很棘手，但在这里和这里解释了，或者您可以相信我）。因此，我们只能使用该生成器最多生成590百万个不同的请求标识符。如果它们是随机选择的，则在生成30,000个标识符后，发生冲突的概率为50％。

- dbkaplun

Answer 3

其他答案已经解释了这个问题。如果您想在JavaScript中获得更好的伪随机数生成，我建议从这个页面开始：

http://baagoe.com/en/RandomMusings/javascript/

我适应了此页面上的算法之一，用于我正在使用的在浏览器中生成UUID的脚本，并且在我的测试中没有发生冲突。

更新于2013年10月22日

上面链接的页面已不再有效。这里是Wayback Machine的快照链接:

http://web.archive.org/web/20120502223108/http://baagoe.com/en/RandomMusings/javascript/

这里有一个链接到包含Alea.js的Node.js模块：

https://npmjs.org/package/alea

- Tim Down

---

@BrianBallsun-Stanton：是的，我已经添加了该页面的快照链接。 - Tim Down

那个也挂了，现在只剩下哎呀了 :( - WetlabStudent

@user1544793：又发现一个了。 - Tim Down