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

Question

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

PS：还问这个是因为 MySQL 语句 usingORDER BY RAND() LIMIT 1没有给出令人信服的结果。

score 18 · Accepted Answer

关于随机的事情是你无法判断随机函数的返回是否是随机的。

^...或者...

适当的随机使用可以真正随机的东西，例如白噪声。伪随机数通常是从数学公式或预先计算的表格中计算出来的。线性同余生成器是一种流行的生成方法。

要获得真正的随机数，您通常希望与有机生成某些东西的外部源进行交互。这称为真随机数生成器。

score 12 · Accepted Answer

啊哈！

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

在计算中，尤其是为了 IT 安全，我们通常希望有一个符合统一随机过程的生成器。有许多不同的过程，但我猜这是您所追求的统一过程。

NIST 已经发布了几份文件，其中包含关于伪随机数生成器以及如何测试它们的建议。查看 NIST 文件 SP 800-22 和 SP 800-20。

正如其他人指出的那样。如果你想要一个真随机数生成器 (TRNG)，你需要收集物理熵。此类源的示例是放射性衰变、宇宙辐射、熔岩灯等。最好您需要难以操纵的源。IETF 有一个 RFC，其中有一些很好的建议，请参阅 RFC 4086 - Source of Randomness for Security： https ://www.rfc-editor.org/rfc/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 已损坏时，您需要定义一个阈值。如果您看到 1000 万个相等的值并且值空间大于一个值（您看到的那个），那么您的 RNG 可能无法正常工作。Esp，如果看到的值是边缘值之一。例如 0x00000.... 或 0xfffff...
中值。如果您在生成一百万个值并具有均匀分布后，有一个中值严重倾向于值空间边缘之一，而不是靠近中间，那么可能也有问题。
方差。如果您在生成数百万个值后没有看到接近值空间的 MIN 和 MAX 的值，而是生成的值空间很窄，那么也有问题。

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

我希望这在某些方面有所帮助。

score 4 · Accepted Answer

您可以应用一些统计测试来查看给定的数字序列是独立的、同分布 (iid) 随机变量的可能性有多大。

看看George Marsaglia 的A Current View of Random Number Generators。特别是，看看第 6-12 节。这提供了对此类测试的介绍，然后是您可以应用的几个测试。

score 2 · Accepted Answer

诚然，我们不能保证随机数实际上是一个随机数。
关于伪随机数：是的，它们似乎是随机的（最初用于密码学）（伪随机函数），当发送加密文本和中间的邪恶陷阱时，消息认为他得到的加密文本是随机的，但消息是从某个函数计算出来的，此外，您将使用相同的函数和密钥（如果有的话，所以没有它们不是随机的，只是看起来像随机的，因为您无法创建它生成的原始文本/数字） .如散列函数(md5,sha1)和加密技术(des,aes等)。

score 1 · Accepted Answer

对于随机数，必须无法预测它。因此，任何生成“随机”数的算法都会生成伪随机数，因为始终可以使用先前使用的种子或在“随机化”期间使用的值生成相同的“随机”数序列。真正的随机数可以通过例如掷骰子生成，但不能通过计算机算法生成。

score 1 · Accepted Answer

理论计算机科学教导计算机是确定性机器。每个算法总是以相同的方式运行，所以你必须改变你的种子。但是计算机应该从哪里获得随机种子呢？从外部设备？CPU温度（变化不大）？

score -5 · Accepted Answer

要测试返回随机数的函数，您应该多次调用它并查看每个数字返回了多少次。

例如

For i := 1 to 1000000 do // Test the function 1.000.000 times
begin
   RandomNumber := Rand(9); // Random numbers from 0 to 9
   case RandomNumber of
      1 : Returned0 := Returned0 + 1;
      1 : Returned1 := Returned1 + 1;
      1 : Returned2 := Returned2 + 1;
      1 : Returned3 := Returned3 + 1;
      1 : Returned4 := Returned4 + 1;
      1 : Returned5 := Returned5 + 1;
      1 : Returned6 := Returned6 + 1;
      1 : Returned7 := Returned7 + 1;
      1 : Returned8 := Returned8 + 1;
      1 : Returned9 := Returned9 + 1;
   end;
end

WriteLn('0: ', Returned0);
WriteLn('1: ', Returned1);
WriteLn('2: ', Returned2);
WriteLn('3: ', Returned3);
WriteLn('4: ', Returned4);
WriteLn('5: ', Returned5);
WriteLn('6: ', Returned6);
WriteLn('7: ', Returned7);
WriteLn('8: ', Returned8);
WriteLn('9: ', Returned9);

每个随机输出的完美输出应该是相等的数字。就像是：

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

7 回答 7

Related

Reference