随机数生成器的种子

乔治·马
ACM通讯，2003年5月，第46卷第5期，90-93页
10.1145/769800.769827
评论

认为: 打印手机应用程序 ACM数字图书馆全文(PDF) 分享: 通过电子邮件发送在reddit分享在StumbleUpon分享分享到黑客新闻在推特上分享在Facebook上分享

相对较短的时间和有限的可能<我>米元组(<我>x_我_＋1,……，<我>x_我_+<我>米由单种子随机数生成器(rng)产生的随机数生成器(rng)已经导致了使用许多种子、具有极长的周期和产生所有或几乎所有可能结果的rng的发展<我>米元组,<我>米从几到几千不等。虽然这些属性可能是科学应用所需要的，但对于法律中的某些应用，或在监管机构的监督下，使用多种子rng可能是强制性的。本专栏讨论了这种情况，并提出了一些好的多种子rng，以及在可能需要很多种子并且需要记录这个过程时选择它们的方法。

回到顶部

随机数生成器和种子

这一列上下文中的RNG是一种计算机程序，给定一组随机值，称为种子，产生一个随机输出，其值是随机输入的固定函数。因此，RNG的输出完全由随机输入决定。如果有<我>N选择随机种子的方法，那么可能结果的数量不能超过<我>N．

种子的选择和数量对于在某些应用中正确使用RNG是至关重要的。下面的例子说明了rng的科学应用和社会应用之间的区别。假设RNG从集合1、2、3、…中返回6个不同的数字。49，也就是说，它选择一种特定的彩票。假设这个过程依赖于一个随机整数种子值。进一步假设，通常情况下，种子值是由CPU时钟寄存器中的16位决定的。

将只有65,536个可能的随机种子值，因此RNG只能选择其中的许多<我米g src="https://dl.acm.org/cms/attachment/b806f87e-d6d9-4445-9c7a-ad25a2b35a6e/c49ov6.gif" border="0" hspace="2" alt="c49ov6.gif">= 13,983,816张彩票。这可能适用于科学应用，例如，统计学家为了反驳彩票中包含一对相邻数字的概率很低的说法，让RNG从这个有限的集合中产生了10000张彩票，并发现其中4996张有相邻的数字，(例如:11,17,23,24,37,41)，这个结果与整个集合的概率0.5048相当一致。通常情况下，对于具有特定属性的元素，其在受限集中的分布与在整个受限集中的分布类似，因此，基于RNG从受限集中采样的模拟可以提供对真实情况的准确估计。

现在考虑一个社交应用程序:每周你在当地的便利店购买10张彩票，让商店的设备随机选择你的10张彩票。该设备使用它的16位时钟寄存器来启动它的RNG。你会想“没关系，任何一张票都有和其他票一样的机会。”但其他数百名售票员也在使用类似的设备;所有生产的门票都是13,983,816张门票中的一个小子集(65,536张)。如果你碰巧有一张中奖的彩票，你很有可能要和其他几个彩票来自这个限制性组合的人分享奖品。

我们将在后面讨论，这些考虑导致了对使用rng的游戏设备的重新评估。但首先，这是rng的一个社会应用，它在法律上引发了严重的问题:在大多数民事或刑事审判中，陪审团都是从一个陪审员召集令一组从公民名单中选出的潜在陪审员。大多数州的法规允许使用计算机进行随意选择，前提是选择是<我>抽签和随机．最常见的程序是使用带有单个种子的随机数生成器从合格列表中做出特定的选择，而种子通常是一个10位数字，通常由计算机时钟以隐藏在专有软件中的方式选择。

因此，venire选择过程只能提供10种左右¹⁰这是可能的venires，而且很难说这样的选择是，如法律要求的抽签和随机的。虽然它可以被认为是随机选择，但它不能被认为是“抽签选择”，因为绝大多数可能的选择永远不会被选择。

例如，考虑一个简单的例子:一个小县城必须从200个符合条件的名单中选择80个。有<我米g src="https://dl.acm.org/cms/attachment/14fa0443-6670-49a8-a305-843271b7e3ef/c200ov80.gif" border="0" hspace="2" alt="c200ov80.gif">选择这种权属的方法，因为，根据法律，所有权属都必须给予同等的重视。现在<我米g src="https://dl.acm.org/cms/attachment/14fa0443-6670-49a8-a305-843271b7e3ef/c200ov80.gif" border="0" hspace="2" alt="c200ov80.gif">是58位的数字。RNG只能选择整个集合中极小的一部分，这是一个简单的例子。考虑棕榈滩县50万名符合条件的人中的1200名。等权重可能性的个数是一个3662位的整数。

法律制度要求通过抽签和随机的方式进行选择，这意味着诉讼当事人有权获得他的陪审团所拥有的机会，如果不是多数，那么至少有几个陪审员可能倾向于支持他的案件。对使用单种子RNG来选择陪审团裁决的常见做法提出的问题(见[<一个href="#R1">1)，导致了对选拔程序的重新评估。新的程序要求可能的随机种子选择数量超过可能的venire数量，但另一个问题仍然存在:被定罪的重罪犯可能会要求新的审判，因为他们的venire选择过程不满足“抽签和随机”的要求。

关于在游戏机中使用rng的问题也出现了。例如，同时玩扑克的玩家应该有机会所有牌都是同花。因为一个普通的单种子RNG只能提供一副牌可能洗牌的一个相对较小的子集(52!> 10⁶⁷)，这样的RNG的社交应用需要有很多种子的RNG。例如，密歇根游戏控制委员会(Michigan Game Control Board)要求某些游戏机在获得授权前必须拥有多种子rng。

回到顶部

多种子随机数生成器

前面的例子表明，社交应用程序可能要求RNG能够从所有可能的结果中进行选择，这个要求可以通过RNG具有许多随机种子值来满足。在科学应用中，通常的单种子RNG可以用来解决这样的问题，即所讨论的特征预计在有限集中具有反映整个集中的分布，但只适用于小于可能种子数量的样本大小。单种子rng的周期通常在2左右³²通过它，现代计算机几分钟就可以运行。科学应用程序可能需要带有多个种子的rng，这有一个更重要的原因:每一个可能<我>米整数的-tuple应该对相当大的整数可用<我>米．rng的许多潜在问题来自于它们在高维中的性能，例如，大多数单种子rng只能产生1/2的结果³²可能的整数对(<我>x_我, x_{我+ 1}),只有1/2⁶⁴可能的三元组(<我>x_我, x_{我+ 1}, x_{我+ 2})，等等。

社交应用程序可能要求RNG能够从所有可能的结果中进行选择，而RNG具有许多随机种子值可以满足这一要求。

因此，对于某些应用程序来说，多种子rng似乎是可取的，而对于其他应用程序来说则是必须的。幸运的是，有几个很好的多种子rng可用。广泛使用的"通用" RNG [<一个href="#R3">3.]使用97个种子值，只使用减法直接返回统一的(0,1)浮点数。梅森龙卷风[<一个href="#R4">4是一个32位的RNG，使用了624个种子，并通过了大量的随机性测试。但它需要一个相对复杂的程序。最近开发的互补-携带繁殖rng使用的种子从几颗到几千颗不等。他们已经通过了所有的随机测试，尤其是“死忠”测试[<一个href="#R2">2]，可以用C、Java或其他语言编写简短的程序来实现。

下面的例子，在C语言中，有1024个种子:

静态无符号长Q[1024];

无符号长CMWC (void) {

t, a=123471786LL;

静态unsigned long c=362436,i=1023;

无符号长x, r = 0 xfffffffe;

我= (i + 1) &1023;

t = * Q[我]+ c;

c = (t > > 32);x = t + c;如果(x < c) {x + +, c++;}

返回(Q[我]= r×);}

这个补乘进位RNG是基于递归的

x_n= (<我>b1) - (<我>斧头_n_-1024年+<我>c_{n - 1}国防部<我>b)，
c_n＝<我米g src="https://dl.acm.org/cms/attachment/2f58a80a-b51c-4fab-a830-a56d03b4d50f/lfloor.gif" border="0" hspace="2" alt="lfloor.gif">（<我>斧头_n_-1024年+<我>c_{n - 1}/<我>b）<我米g src="https://dl.acm.org/cms/attachment/e01ca9bc-e70f-4c7b-874f-537625b17ce0/rfloor.gif" border="0" hspace="2" alt="rfloor.gif">

与<我>b= 2³²- 1和<我>x₀，<我>x₁,……，<我>x₁₀₂₃数组中最初的32位种子问[1024]初始值是c, 0的任意选项<我>c<<我>一个．这是一种很好的做法问[1024]数组中包含一组默认种子，例如with

j = 123456789;(我= 0;< 1024;我+ +){j ^ = < < 13;j ^ = > > 17;j ^ = < < 5;问[我]= j}

(也许使用种子选择而不是123456789作为移位寄存器RNG。)然后可以设置任意数量的种子，最多1024个问[0]Q [1],……补充默认设置。对于科学应用程序，少量的种子值可能就可以了，但对于必须能够返回大量可能结果中的任何一个的应用程序，必须选择足够多的种子来满足这一要求。

对于少于前面清单中1024个种子的版本，

使用问[512]而且一个= 123554632 ?用511替换1023。

使用问[256]而且一个= 8001634 ?用255替换1023。

使用问[128]而且一个= 8007626 ?用127替换1023。

使用问[64]而且一个= 647535442 ?用63替换1023。

使用问[32]而且一个= 547416522 ?用31代替1023。

使用问[16]而且一个= 487198574 ?用15代替1023。

使用问[8]而且一个= 716514398 ?用7代替1023。

对于种子表大小和乘数的任何一种选择都将提供一个通过大量随机性测试的RNG，特别是在[<一个href="#R3">3.，但它简单而快速，在850MHz的PC上每秒大约有3000万个随机32位整数。周期是<我>abⁿ,在那里<我>一个乘法器,<我>n种子表的大小<我>b= 2³²1。（<我>一个b是质数的原始根<我>abⁿ+ 1)。

回到顶部

把种子

对于那些需要使用许多随机种子的应用程序，如果程序像法律一样是一个正式的程序，可能需要审查和验证，那么获得它们的问题就不是微不足道的。最近可用的使用热噪声的设备可以向计算机提供适当的随机字节，如果这个过程不需要被记录或记录，就可以很好地服务。当然，一组证人和宣誓书的结果读取从一个随机噪声发生器的输出可以服务，但有一个更好的方法，不依赖于这种设备或正式的监测输出。

首先，假设我们需要几百个随机种子，它们可以被当作10位整数。这些数字可以每次随机选择一个，具体方法如下:在未来的某一天，依次使用在纽约证券交易所上市的3000多只股票的每日销售数字。这些数据几乎是不可预测的，很容易获得，而且在每次结案后都是公开记录。{0,1,2,3,4,5,6,7,8,9}中的单个数字可能不是均匀的，但它们可以导致如下结果:使用良好的单种子RNG生成从0到9的均匀随机数字序列。然后将这些数字与日销量数字相加，对结果取10余。很容易看出如果<我>我是一个均匀随机的数字，那么是<我>J+<我>我国防部10,<我>J任何数字，随机的或固定的，是独立的吗<我>我．

将未必统一的每日销售额数字mod 10与统一的RNG数字组合在一起的结果(每次取10)将提供必要的种子。具体说明收货日期、使用数字的销售的确切订单和数量，连同RNG及其种子，可以提供正式文件和验证手段。

例如,一个nyclose纽约证券交易所7月一个工作日公布了3,526只股票的数据。第一列给出股票代码，从(为节省空间将列改为行)开始:

AA, AAE AAGPRT,麦,AAR, AAS, AAT, ABB,沛富,ABG、ABI,这个,……

纽约证交所文件的最后一栏提供了这些股票当天的“总成交量”:

2943000, 2943000, 202200, 1300, 11200, 4600, 863600, 2600, 23300, 244000,…

每次取一个数字可以得到三行数字中的第一行。第二行是由RNG产生的一行随机数，然后将股票市场的数字和随机数相加，对10取模，得到最后一行:

2、9、4、3、0,0,0,2,2、7、7、3 0,0,2 0 2 2 0,0,1,3,0,0,1,1,2,0,0,4,6,0,0,8、6、3、6 0,0,2,6日……
2 6 4 9 0、4、7、2、1 9 0、4、3、2、7、6、9、3、7、7 0、3、2、5、9、3、8、7、9,9日,5、7、3、7、2、8 0 6 3,2,8,…
4、5、8、2 0、4、7、4、3、6、7、7、3、2、9、6、1、5、7、7、1、6 2 5 0 4 0 7日,9日,3,1,3,5,8,1、6、6、3、4、4、……

最后一个数字序列可以一次取10个，形成必要的10位随机种子序列:

4582047436, 7732961577, 1625040793, 1735816634，…

编写一个计算机程序，从指定的股票列表中提取总成交量值，依次取这些数字，然后将它们与单种子RNG中的随机数字组合(对10取模)，这是一项常规任务。然后，对结果数字进行分组，形成足够多种子RNG所需的10位随机种子，以提供尽可能多的可能结果。

上述程序被推荐用于法律等应用程序，在这些应用程序中，选择均匀随机种子的必要数量可能必须被记录下来，预先指定，“不可修复”，并在之后可用于审查。在许多应用中，这种预防措施可能不是必要的或可取的;人们可能只是想通过任何方便的方法获得应用程序中调用的均匀随机种子的数量。重要的一点是，记住RNG结果的随机性是其种子随机性的直接结果，其数量应受结果的总体不能超过种子选择的总体这一事实的支配。

回到顶部

参考文献

1.马萨格利亚，G.使用电脑选择陪审团的问题。<我>判决法理学41(2001年夏季),425427年。

2.马,G。<我>马萨格利亚随机数CD-ROM，带有随机性测试的死硬电池。在美国国家科学基金会的资助下，于1995年在佛罗里达州立大学制作;www.stat.fsu.edu/pub/diehard。新版本的Diehard可以在www.csis.hku.hk/~diehard上找到。

3.Marsaglia, G.， Zaman, A.和Tsang, W.迈向一个通用随机数发生器。<我>统计与概率(1990), 3539。

4.Matsumoto M.和Nishimura, T. Mersenne Twister: 623维等分布均匀伪随机数发生器。<我>美国计算机学会建模与计算机仿真学报， 1(1998)， 330。

回到顶部

作者

乔治马(geo@stat.fsu.edu)是位于塔拉哈西的佛罗里达州立大学的名誉教授。

允许制作本作品的全部或部分的数字或硬拷贝用于个人或课堂使用，但前提是该拷贝不是为了盈利或商业利益而制作或分发，并且该拷贝在第一页上带有本通知和完整引用。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或付费。