测试PRNG的质量

 

我在玩PRNGs（比如stdlib的Mersenne Twister和rand()函数），我想要一个很好的测试来帮助我确定PRNG产生的随机数据的质量。 我使用PRNG生成的随机数计算了Pi的值，并且我发现rand()和Mersenne Twister非常接近以提供区分（我需要在10个小数点后面仔细检查？）。

我对蒙特卡洛模拟没有太多的想法; 请让我知道一些算法/应用程序（可能简单但可以提供很好的推论），这将帮助我在质量方面区分它们。

编辑1：我没有注意过，但有一个类似的线程：如何测试随机数字？

编辑2：我无法解释NIST的结果，如其中一条评论所述。 我有了这个想法，可以直观地解释random.org中的模式（如果有的话），并且因为它很简单，所以我会这么做。 如果有人能评论我的测试过程，我会很高兴：

  • 使用rand（）和MT1997从[0,1]生成N个随机数
  • 如果(round(genrand_real1() / rand_0_1()))红色像素，否则为黑色

    • 据我所知，这不是一个非常精确的解决方案，但如果这提供了一个合理的估计，那么我现在可以忍受这一点。

    有两个用于测试随机数的标准测试套件。

  • NIST测试套件。 他们在C中有一个实现。
  • Diehard测试套件（由George Marsaglia开发）。 这些测试有一个C库实现。

    • Dieharder图书馆有一个名为RDieHarder的R接口。 该库提供了NIST和Diehard测试套件的接口。

    有几个统计测试套件可用。 我编写，复制并收集了120个PRNG，并使用各种测试套件对每个测试套件进行了测试，每个测试套件每个PRNG测试套件4个小时：

  • PractRand（标准1 TB）在78个PRNG中发现了偏见
  • TestU01（BigCrush）在50个PRNG中发现了偏见
  • RaBiGeTe（扩展，512兆，x1）在40个PRNG中发现偏见
  • Dieharder（自定义命令行选项）在25个PRNG中发现了偏见
  • Dieharder（ - 一个命令行选项）在13个PRNG中发现了偏见
  • NIST STS（默认64兆比特x128）在11个PRNG中发现偏差

    • PRNG中有多少人其他测试套件都漏掉了？

  • PractRand（标准，1兆兆字节）发现了22种独特的偏见，种类繁多。
  • RaBiGeTe（扩展，512兆，x1）发现5个独特的偏见，所有这些都在LCG和LCG中。
  • TestU01 BigCrush发现了两个独特的偏见，都在小混乱的PRNG中。
    没有其他测试套件发现任何独特的偏见。

    • 总之，只有PractRand，TestU01和RaBiGeTe才值得使用。

    充分披露：我写了PractRand，因此无论是PRNG还是任何其他非定性措施都可能对其有利。

    其他优点：

  • 在我看来，PractRand和TestU01往往是最容易解释输出的。
  • 我认为PractRand和Dieharder往往是通过命令行界面自动化测试的最简单方法。
  • PractRand和RaBiGeTe是唯一支持多线程测试的软件。

    • 其他缺点：

  • PractRand需要比其他测试套件更多的输入来测试 - 如果您的RNG非常缓慢或者对生成的数据量有限制，可能会出现问题。
  • RaBiGeTe和NIST STS都有接口问题。
  • Dieharder和NIST STS都有假阳性问题。
  • 在我看来，NIST STS的界面最差。
  • 我无法让Dieharder在Windows上编译。 我设法让TestU01在Windows上编译，但它花了一些工作。
  • RaBiGeTe的最新版本是封闭源代码和仅限于Windows。

    • 测试的PRNG集： PRNG集包括1个大型GFSR，1个大型LFSR，4个xorshift型PRNGs，2个xwwow型PRNGs，以及3个其他不完全LFSR PRNGs。 它包括10个简单的2功率模数LCG（其丢弃低位以达到可接受的质量水平），10个2幂模数非完全LCG以及主要基于LCG和不相当LCG的9个组合发生器。 它包括19个强度较低的CSPRNG版本，以及一个完整强度的CSPRNG。 其中14个基于间接/动态S盒（例如RC4，ISAAC），4个是ChaCha / Salsa参数化，其余2个是Trivium变体。 它包括11个大致可分类为LFib型或类似的PRNG，不包括LFSR / GFSR。 其余（约35）是小状态混沌PRNGs，其中10个使用乘法，其他则仅限于算术逻辑和按位逻辑。

    编辑：在gjrand中也有测试集，这是非常模糊和有点奇怪，但实际上做得非常好。

    此外，所有测试的PRNG都被列为PractRand中不推荐的PRNG。

    你最好看看Knuth系列的第2卷。

    对于较短的读数，请查阅数值配方的相应章节。

    如果你只对MC模拟的基线感兴趣 - 最好避免使用线性同余发生器，Mersenne Twister在绝大多数情况下都足够好。

    链接地址: http://www.djcxy.com/p/37267.html

    上一篇: Testing the quality of PRNGs

    下一篇: Trying to write an invertible PRNG of 8 bits, not a cipher