一维均匀分布随机数序列的产生方法.doc

一维均匀分布随机数序列的产生方法 引言： 随机数序列主要应用于序列密码（流密码）。序列密码的强度完全依赖于序列的随机性与不可预测性。随机数在密码学中也是非常重要的，主要应用于数字签名（如美国数字签名标准中的数字签名算法）、消息认证码（如初始向量）、加密算法（如密钥）、零知识证明、身份认证（如一次性nonce）和众多的密码学协议。 关键词：随机数、随机数序列、均匀分布 一、随机数及随机数序列的简介 在统计学的不同技术中需要使用随机数，比如在从统计总体中抽取有代表性的样本的时候，或者在将实验动物分配到不同的试验组的过程中，或者在进行蒙特卡罗模拟法计算的时候等等 产生随机数有多种不同的方法这些方法被称为随机数发生器。随机数最重要的特性是它所产生的后面的那个数与前面的那个数毫无关系。设连续型随机变量X的分布函数为 F(x)=(x-a)(b-a)，a≤x≤b，则称随机变量X服从[a,b]上的均匀分布记为XU[a，b]。 若[x1,x2]是[a,b]的任一子区间,则 P{x1≤x≤x2}=(x2-x1)/(b-a)这表明X落在[a,b]的子区间内的概率只与子区间长度有关而与子区间位置无关因此X落在[a,b]的长度相等的子区间内的可能性是相等的所谓的均匀指的就是这种等可能性 三、一维均匀分布随机数序列的产生方法 1、迭代取中法：??? 这里在迭代取中法中介绍平方取中法,其迭代式如下: ??? 其中，是迭代算子，而则是每次需要产生的随机数。 第一个式子表示的是将平方后右移s位，并截右端的2s位，而第二个式子则是将截尾后的数字再压缩2s倍，显然: 0≤≤1。 但是，迭代取中法有一个缺点，即它比较容易退化成0。 平方取中法的实现结果： 前96个测试生成的随机数序列: 0.399000 0.920100 0.658400 0.349000 0.180100 0.243600 0.934000 0.235600 0.550700 0.327000 0.692900 0.011000 0.012100 0.014600 0.021300 0.045300 0.205200 0.210700 0.439400 0.307200 0.437100 0.105600 0.115100 0.324800 0.549500 0.195000 0.802500 0.400600 0.048000 0.230400 0.308400 0.511000 0.112100 0.256600 0.584300 0.140600 0.976800 0.413800 0.123000 0.512900 0.306600 0.400300 0.024000 0.057600 0.331700 0.002400 0.000500 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 从上述数据容易看出其易退化成0的缺点。 2、乘同余法： 乘同余法的迭代式如下: ??????? 各参数意义及各步的作用可参见1 当然，这里的参数的选取是有一定的理论基础的，否则所产生的随机数的周期将较小，相关性会较大。 经过前人检验的两组性能较好的素数取模乘同余法迭代式的系数为: 1） 2）。 3、混合同余法： 混合同余法是加同余法和乘同余法的混合形式,其迭代式如下: 经前人研究表明，在的条件下，参数按如下选取可保证周期较大，概率统计特性好： ? 但是，仔细研究可以看出它的一个致命的弱点，即随机数的生成在某一周期内成线性增长的趋势，显然，在大多数场合，这种极富“规律”型的随机数是不应当使用的。 4、反函数法： 当随机变量为连续型时，可以用到反函数法。 ? 采用概率积分变换原理，对于随机变量X的分布函数F(X)可以求其反函数。 其中, 为一个0-1区间内的均匀分布的随机变量。 F(X