如何测试 RNG 的质量?

机器算法验证 随机生成
2022-03-29 19:59:32

在electronics.stackexchange 上,我们有一个关于构建真随机数生成器的问题。由于该方法依赖于不确定性的噪声,因此测试 RNG 质量的唯一方法似乎是经验性的。
作为一名统计学家,我建议测试一个长比特序列的正态性,但我不知道什么结果是可以接受的,什么不是。例如计算单个位,我想我们对 499500/500500 分布表示赞同,但是什么时候该比率过于偏斜而无法接受?对于 2 位和更长的序列也是如此。
当然,如果测试正常性是一个坏主意™,我想听听它,包括更好的替代方案。

编辑
死硬被提到了几次,但我不确定这是否能回答我的问题。正态性检验应该给出一个正态分布,对于较长的序列具有更好的钟形曲线近似值。顽固分子似乎也有测试应该导致正态分布或指数分布。但我的问题仍然存在:我如何判断结果?只是通过观察曲线并辨别其中的钟形曲线?回到我的第一个例子,499500/500500 分布肯定是可以的,而 950000/50000 分布肯定是不行的,那么切换发生在哪里呢?

2个回答

JM 已经提到了George Marsaglia的原始Diehard 测试据我所知,该测试集已不再维护。

多年来,罗伯特·布朗一直在为《DieHarder》工作

  • DieHard 套件的 GPL 重新实现
  • 加上来自 NIST 套件的额外测试
  • 加上新测试的开发

你可能会发现 DieHarder 很有用。

你是对的:测试是经验性的。这一切都是在一个标准的假设检验框架中完成的。应用不同的测试来评估 RNG 的不同替代行为。与往常一样,用户可以自由选择进行每个测试的置信水平。这个级别决定了每个测试的关键区域,即“显着”结果和不被认为显着的结果之间的“切换”。

在实践中,置信水平无关紧要,因为大多数 RNG 可以生成如此长的一系列值,最终任何长期偏离完全、独立、均匀分布的随机性的结果都可以以高置信度检测到。(这是正确应用像 DieHard 这样的测试套件要求您至少生成大量位的主要原因。我记得——已经有一段时间了——早期版本需要 8000 万位。)通常,一个RNG 将通过许多对其进行的测试(否则它永远不会看到曙光),但它显然会破坏其中的一些。