我需要测试一个随机数生成器,该生成器可以随机产生数字。如何确保所生成的数字是随机的。
我需要测试一个随机数生成器,该生成器可以随机产生数字。如何确保所生成的数字是随机的。
您只能测试随机性,这并不能证明数字序列在密码学上是强大的。统计测试 PRNG 需要生成大量的位数(10 或 100GB)。
Dieharder 是一个非常好的测试套件。
http://www.phy.duke.edu/~rgb/General/dieharder.php
TestU01 也很出名。
这里是如何开始的详细说明。任何随机数生成器的初步测试都是由NIST使用的单比特测试,它仅计算1和0的数量。http://csrc.nist.gov/groups/ST/toolkit/rng/stats_tests.html
关于测试随机数生成器的注意事项: 我们实际上不需要太多的RNG测试,因为许多测试“包含”彼此。
尽管如此,这里描述了一种简单而有效的新的有序频率测试,适用于位。该测试包含了任何期望50-50的频率测试,因为它更为严格。
定义:t=扔 / 试验 b=箱子 / 球 s=一组扔 n=一组组扔
由于硬币投掷通常不是50-50的,因此可以利用4000万个位的池以极大的效果进行这个新测试。
当硬币被投掷100次时,期望值为53.9795和46.0205,有时会出现更多的正面或反面。50-50不是有序箱子的期望值,所以这个测试比任何期望50-50的频率测试都要好。2000次100次抛硬币的期望值:
50-50 159.1784748 (注意,50-50仅发生了7.96%的时间。)
51-49 312.1146564
52-48 294.1080416
53-47 266.362
54-46 231.8335926
55-45 193.8971865
56-44 155.8102392
57-43 120.2745706
58-42 89.16907819
59-41 63.47629295
60-40 43.37546685
61-39 28.4429291
62-38 17.89152
63-37 10.79171042
64-36 6.238957586
65-35 3.455422663
66-34 1.832421109
67或更多 1.747439674
此方程适用于任何投掷次数。
步骤3:对这18个值进行17自由度的卡方检验,得到结果p值。
当p值大于0.999时,接近完美。随机数发生器是否会太过于接近完美?是的,太容易预测了。在0.001以下的范围内通常会出现明显问题。一个测试套件将小数点右侧的300个零视为微不足道的错误,而10-14个连续的零则相当糟糕。有些人认为6个零已经足以被视为明确的失败。出于安全考虑,有些人认为1或2个零就足够了,但其实是错误的。因此,为了获得优秀随机数发生器的p值低于0.01,需要采取多组会话。
步骤4:将p值输入到0-1.0直线Kolmogorov-Smirnov测试中。不同的专家建议将输入数量设置为10至1000。100还不够。200可以。500稍微过于激进。
下面是获取K-S最大差异的伪代码:
Set low := 0; Set n := 200;
Set ansForward := 0; Set ansBack := 0;
sort( pval [n] );
for (j := 0; j < n; j := j+1)
{ Set Kback := pval [ j ] - low;
Set low := low +1 / n; { Ranges from 0 to 1 }
Set Kforward := low - pval [ j ];
if (Kforward > ansForward) Set ansForward := Kforward;
if (Kback > ansBack) Set ansBack := Kback;
}
{ Separate analysis can perhaps be made here on ansForward and ansBack. Someone like Peter Brand might also examine and magnify the bottom 5% and the top 5%. }
if (ansForward > ansBack)
return ansForward;
else
return ansBack; ∎
LCG 134775813x + 1模2^31种子=11111: 高位:OFT KS:0.0841通过。LOR KS:0.04786通过。前200,000个数的单比特:-189通过。 第16位:OFT KS:0.5477失败。前200,000个数的单比特:114通过。 所有从0到15位的比特均未通过OFT测试,但通过了单比特测试。
常被诟病的LCG Randu:65539x + 0模2^31种子=11111: 高位:OFT KS:0.03567 LOR KS:0.07709。前200,000个数的单比特:-165 第18位:OFT KS:0.15143 前200,000个数的单比特:+204 所有从0到17位的比特均未通过OFT测试。
LCG 69069x + 1模2^32种子=11111: 高位:OFT KS:0.05547 LOR KS:0.0456 前200,000个数的单比特:-290 第17位:OFT KS:0.1467 前200,000个数的单比特:-193 所有从0到13位的比特均未通过OFT测试。
LCG 3141592653x + 2718281829模2^35种子=11111: 高位:OFT KS:0.02868 LOR KS:0.06117 前200,000个数的单比特:-69 第16位:OFT KS:0.240 前200,000个数的单比特:-13 所有从0到15位的比特均未通过OFT测试。
LCG 23x + 0模2^27种子=11111: 高位:OFT KS:0.5368 前200,000个数的单比特:-235 所有比特均未通过OFT测试。
详见Charmaine Kenny的研究部分,了解可运行的测试更多细节。
这是一件非常困难的事情。
你可以尝试使用ENT和Fourmilab,并将其与他们的RNG HotBits 的结果进行比较。你也可以查看Random.org。
这个看起来也很有趣:Diehard tests(不过我没有使用过它)。
cat /dev/random | dieharder -a -g 200
或者编写自己的脚本,创建一个带有随机数字的文件
dieharder -a -g 202 -f random.txt
仅仅因为随机数是随机的,你无法确保数字是随机的。
获得一百万个连续的9的字符串的概率与获得任何其他特定的一百万个字符长的序列相同。您可以检查的唯一一件事是正确分布在大样本集上。运行一个规模可观的测试,并计算每种可能结果的相对出现次数。
在足够大的样本中,它们应该大致相同。
另一个可能性是测试不可重复性。理想情况下,随机数不应依赖于之前的数字。非常简单(线性同余)的伪随机数生成器最终很可能会给您相同的数字序列,但在足够大的集合中,您可能不会关心(除非您非常关注随机性)。
这取决于你对随机性的要求有多严格。如果不是太严格,我通常会生成大量随机数,找到它们的频率,然后使用类似于Open Office中的电子表格来绘制一个图形。如果分布看起来正常,那么我就可以使用它。
除非您可以访问随机数生成器并使用它随意生成数字,否则您无法测试数字序列是否随机。想一想:您有一个随机数生成器。假设它是一个均匀分布的随机数生成器,在范围[0,9]内生成随机整数。给定一个序列:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
你能判断它是否是随机的吗?我们的均匀随机数生成器有一个有限的概率10−10会生成这个确切的序列。事实上,对于任何长度为10的序列,我们的均匀随机数生成器生成该序列的概率相同。因此,根据定义,您无法确定给定序列是否随机。
如果您可以访问生成器本身并可以使用它来生成多个序列,则检查随机性是有意义的。为此,我会看Diehard tests。有各种实现。