如何"检查"函数是否真的给出了随机结果？

Question

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

PS:也问这个,因为使用的MySQL语句ORDER BY RAND() LIMIT 1没有给出令人信服的结果.

Answer 1

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

^...要么...

适当的随机使用可以真正随机的东西,例如白噪声.伪随机数通常根据数学公式或预先计算的表来计算.的线性同余发生器是产生它们的流行的方法.

要获得一个真正的随机数,您通常希望与外部源接口,其中某些东西是有机生成的.这称为真随机数发生器.

Answer 2

阿罗哈!

有几种方法和工具可用于测试随机性.这些应用于从待测试的发生器收集的一组数字上.也就是说,您根据生成的一组数据测试生成器.

在计算中,尤其是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已损坏时,您需要定义阈值.如果您看到1000万个相等的值,并且值空间大于一个值(您看到的那个),您的RNG可能无法正常工作.Esp,如果值正在查看是边缘值之一.例如0x00000 ....或0xfffff ...

• 中值.如果你在生成一百万个值并且具有均匀分布后,其中值很大程度上倾向于其中一个值空间边缘,而不是接近中间,那么某些可能也是错误的.

• 方差.如果你在生成数百万的值之后没有看到接近值空间的MIN和MAX的值,而是有一个狭窄的生成值空间,那么也有些不对劲.

最后.由于您希望使用良好的PRNG(例如基于AES),建议的原位测试可能会应用于熵源.

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