function - 如何“检查”一个函数是否确实给出了随机结果？

Question

如何确定一个函数确实是随机的或尽可能接近该概念？另外，随机和伪随机之间有什么区别？最后，哪些算法/源可用于生成随机数？

P.S：还要问这个问题，因为使用ORDER BY RAND() LIMIT 1的MySQL语句没有给出令人信服的结果。

Answer 1

阿罗哈！

有几种测试随机性的方法和工具。将这些应用于从生成器收集的一组要测试的数字。也就是说，您根据生成的一组数据来测试生成器。

在计算中，特别是在IT安全方面，我们通常希望有一个符合统一随机过程的生成器。有很多不同的过程，但是我猜想这是您要针对的统一过程。

NIST已发布了几份有关伪随机数生成器以及如何对其进行测试的建议的文档。查看NIST文档SP 800-22和SP 800-20。

正如其他人指出的那样。如果您需要真随机数生成器（TRNG），则需要收集物理熵。此类源的例子有放射性衰变，宇宙辐射，熔岩灯等。最好是您想要难以操纵的源。 IETF的RFC有一些好的建议，请参阅RFC 4086-安全性随机性源：
http://tools.ietf.org/html/rfc4086

通常，您要做的是从一种或多种（最好是一种以上）来源中收集熵。然后对收集的数据进行过滤（增白），并最终用于定期播种良好的PRNG。自然会有不同的种子。

这就是大多数现代优良随机发生器的工作方式。熵收集器，其馈送给使用诸如对称密码（例如AES）或哈希函数之类的密码基元创建的PRNG。参见例如Schneier的随机生成器Yarrow / Fortuna，它在FreeBSD中以修改的形式使用。

回到关于测试的问题。正如某人指出的那样，Marsaglia进行了一系列不错的测试，这些测试已编入DIEHARD测试中。现在在Dieharder测试中有更多的测试集：
http://www.phy.duke.edu/~rgb/General/dieharder.php

Dieharder是一个很好的工具，可以使您充满信心，它所提供的大量数字（从生成器中收集）是随机的（具有良好的质量）。运行Dieharder很容易，但需要一些时间。

随机性的原位测试很困难。您通常不需要在系统中实现Dieharder。您可以做的是实现一些简单的检测器，该检测器应检测出病理病例。我通常建议：


等值长度。当RNG生成的两个结果值不同时，将重置一个简单的计数器。然后，当您认为计数器显示RNG损坏时，需要定义一个阈值。如果看到一千万个相等的值，并且值空间大于一个值（您看到的一个值），则您的RNG可能无法很好地工作。如果看到的值是边缘值之一，则Esp。例如0x00000 ....或0xfffff ...
中值。如果在生成一百万个值并具有均匀分布后，中值严重偏向值空间边缘之一（而不是靠近中间值），则也可能不适合某些情况。
方差。如果在生成数百万个值之后，您没有看到接近值空间的MIN和MAX的值，而是生成的值空间狭窄，那么也有些不对劲。


最后。由于您希望使用的是良好的PRNG（例如，基于AES），因此建议将原位测试应用于熵源。

我希望这在某种程度上有所帮助。