一种随机数组合发生器的研究

【摘要】  将基于混沌的随机数产生算法和线性同余发生器进行组合,产生随机数列.经过检验,随机数列的统计性质有了很大提高。

【关键词】  混沌； 线性同余发生器； 随机数

1  引言

    随机数在信息加密、数值运算及医学中基因序列分析等研究中有着广泛的应用。比如数值运算中,Monte Carlo方法占有重要的地位,随机数是该方法的基础.随机数的质量影响了信息的安全和结果的精度。特别是一些安全级别比较高的应用,对随机数提出了很高的要求。随机数可由硬件和软件两种方式产生。在计算机中广泛使用的是软件方式,通过计算机利用数学模拟随机过程产生随机数。此方法有着自身的不足,数据之间有着关联性,存在周期,并非真正的随机数,因此被成为伪随机数。

    常见的产生随机数的方法有［1］：线性同余法（LCG,Linear Congruent Generators）、Tarsworthe位移计数器法、Fibonacci延迟产生器法等。为了克服以上方法的缺陷,人们还了许多新的方法。组合发生器就是著名的一种。它是将两个随机数发生器进行组合,以一种发生器产生一个随机数列,再用另一个随机数发生器对随机数列进行重修排列,得到一个更为独立,周期更长的随机数列。已有一些利用混沌序列转换伪随机数列的报道［2］,［3］虽然提出了一种由logistic映射构造具有均匀性数列的好方法,但数据之间的独立性较差。本研究中提出了一种新的方法,利用混沌算法［4］和线性同余发生器相组合得到随机数列,并就数据的均匀性和独立性进行了检验。

    2  理论基础

    2.1  混沌算法

    混沌是一种确定性系统中出现的类似随机的过程。它首先是由洛伦兹在流体热对流的简化模型计算中观察到的。混沌现象可以用它某些非线性函数的迭代（映射）来表示类似随机的输出。一维迭代Logistic方程是一个很简单的非线性抛物线函数,可以表示为：

    xi+1=λxi(1-xi),    (0≤xi≤1,    0≤λ≤4)    (1)

    xi 是i 次迭代的值。研究表明当λ>3.57 时,进入混沌状态。特征是表现为初值敏感性,既使初值相差非常小,经过几十次迭代，得到的值也会相差非常大，并且毫无关联。当λ=4 时,序列xi 的概率分布服从

    P(xi)=1πxi(1-xi)(2)

    所以xi 序列分布并不均匀，通过代换

    ri=2arcsinxiπ(3)

    就可以得到均匀的ri 数列。

    2.2  线性同余发生器

    线性同余发生器是现在使用最多的随机数发生器之一，该方法利用同余运算产生随机数。

    Ii+1=(aIi+b)mod m

    xi=Iim  (4)

    其中m 为模数, a为乘子, b为增量,并且a,b,m,I1 均为非负整数。如何选择他们就决定了产生器的质量。在计算中取a=16807,b=0,m=231-1,I1=12546863 。显然,由公式(4)得到的Ii 满足：0≤Ii≤ m,所以0≤xi≤1 。线性同余法的优点就是速度快,每次调用只需几个操作步骤即可,因此最为常用.缺点就是数据序列的有着关联性,表现为高维稀疏网格结构［5］。特别是当a 和m 的值较小时,这种现象更为明显。

    2.3  组合发生器

    20世纪70年代就有人提出用用组合发生器来产生高质量的伪随机数。有文献［6］对此进行了理论分析并指出：几个独立且近似的随机变量的线性组合也是一个近似均匀的随机变量,其分布比组成它的任何一个变量更接近U（0，1）。

    该算法是分别用两个发生器各自产生一组随机数列,然后再把它们进行相互组合,以期得到一个统计结果更好的随机数列。具体步骤如下：

    ① N个不同的随机数发生器各自产生一组随机数列 { Xi（j)(i=1,2,…,L,  j=1,2,…,N)。

    ② 令c1,c2,…,cN 为N个非负整数。

    Ui=∑Nj=1c(j)Xi(j)

    ri=Ui mod 1    i=1,2,…   (5)

    按上述算法把混沌算法和线性同余产生的随机数组合在一起。在中,取c1=2,c2=5 。每个发生器都有其各自的周期Period(Xi) ,如果它们互素,则组合后的周期是各自周期的最小公倍数（LCM）。Period(Xi)=LCM(Period(Xi(1)）,Period(Xi(2),…)。因此组合发生器产生数据的周期会大大增加,实际应用中可视为无穷大。

    3  随机数的统计检验

    随机数的好坏是通过各种统计检验来确定的,这些检验包括均匀性检验、独立性检验、参数检验等。其中最基本的是均匀性检验和独立性检验。在随机数的检验中独立性检验是首要的,如果不存在独立性就无所谓随机。也希望得到的随机数在区间［0，1］ 上出现的概率是相同的,所以均匀性检验也起着决定作用。

    3.1  均匀性检验

    假设区间［0，1］上的随机数列{Xi}(i=1,2,…,n)。如果随机数分布均匀,则把区间分成k 个相等的子区间后,落在每个子区间的随机数个数ni 近似等于n / k 。统计量χ2 按定义为:

    χ2=∑ki=1(ni-n / k)2n / k   (6)

    χ2 应服从χ2(k-1) 分布,在给定一个显著水平α 下,可查表得到临界值χα2(k-1)。如果χ2>χ2α ,则拒绝均匀假设。

    3.2  独立性检验

    对独立性检验中的相关检验基于相关系数r 。把随机数列{ri}(i=1,2,…,2n) 分成两部分{Xi}(i=1,3,…,2n-1),{Yi}(i=2,4,…,2n} ,相关系数r 为:

    r=1n∑ni=1(Xi-)(Yi-)1n∑ni=1(Xi-)2  1n∑ni=1(Yi-)2  (7)

    当ρ=(1.96)2+n-2 |r|≥1.96 时, 认为线性回归效果显著,拒绝独立检验。

    3.3  参数检验

    随机数列{Xi}(i=1,2,…,n) ,其一阶矩、二阶矩和二阶中心矩分别为:

    =1n∑ni=1Xi,  2=1n∑ni=1Xi2, s2=1n∑ni=1(Xi-12)2   (8)

    对于均匀分布的数列,其值分别为12, 13,112 。如果与理论值没有显著差别，则通过参数检验。

    检验中,3种发生器分别生成100000个数据,对其统计性质进行了分析。取检验的置信度α=0.05 ,在均匀检验中，检验区间k=500 ,χ2(500)>552.78 时拒绝均匀假设［7］；独立性检验中ρ=(1.96)2+n-2 |r|≥1.96,拒绝独立假设。表1  随机数列的统计结果 从表1的统计结果可以看出,组合后的发生器表现出了更为优秀的统计结果.在数据的独立性和均匀性上都大大增加。

    混沌算法虽然可以通过均匀性检验,但独立性较差,没有通过独立性检验,不宜单独作为随机数发生器使用.如果把数列中相邻两个数据作为（x,y) ,分别作出各个数列的二维散布图。不难看出,图1混沌算法得到的随机数列,数据之间有着强烈的关联,数据之间并不独立。图2和图3数据分布则比较均匀。

    4  结论

    计算机模拟、信息加密或Monte Carlo方法成功的基础是实现真正的随机抽样,随机抽样的基础是随机数。从以上统计结果可以看出,两种发生器组合之后,得到的随机数列具有更好的统计结果,在保持均匀性的基础上,独立性有了较大的提高。并且组合后,随机数列的周期可视为无穷大。因此该方法具有良好的统计性质,符合随机数的要求。

【】
  1 杨自强,魏公毅. 产生伪随机数的若干新方法.数值计算与计算机应用,2001,3:210～216.

2 孙霞,吴自勤,黄畇,分形原理及其应用.技术大学出版社 2003,1～22.

3 盛利元,肖燕予,盛喆,将混沌序列变换成均匀伪随机序列的普适算法.物报,2008,57：4407～4412.

4 周燕,覃朝玲 用混沌法产生随机数发生器的研究.西南师范大学学报,2000,25：150～154.

5 罗平. 线性同余发生器的缺陷及其改进.计算机工程,1995,21：295～297.

6 Deng L Y, George E O. Generation of Uniform Variate from Several Nearly Uniformly Distributed Variables. Comm Statist Simu, 1990,19:145～154.

7 王萍,许海洋. 一种新的随机数组合发生器的研究 计算机技术与， 2006,16：79～81.