一種隨機(jī)數(shù)組合發(fā)生器的研究

1、    【摘要】  將基于混沌的隨機(jī)數(shù)產(chǎn)生算法和線性同余發(fā)生器進(jìn)行組合,產(chǎn)生隨機(jī)數(shù)列.經(jīng)過檢驗(yàn),隨機(jī)數(shù)列的統(tǒng)計(jì)性質(zhì)有了很大提高。 【關(guān)鍵詞】  混沌； 線性同余發(fā)生器； 隨機(jī)數(shù)1  引言    隨機(jī)數(shù)在信息加密、數(shù)值運(yùn)算及醫(yī)學(xué)中基因序列分析等研究中有著廣泛的應(yīng)用。比如數(shù)值運(yùn)算中,Monte Carlo方法占有重要的地位,隨機(jī)數(shù)是該方法的基礎(chǔ).隨機(jī)數(shù)的質(zhì)量影響了信息的安全和計(jì)算結(jié)果的精度。特別是一些安全級(jí)別比較高的應(yīng)用,對(duì)隨機(jī)數(shù)提出了很高的要求。隨機(jī)數(shù)可由硬件和軟件兩種方式產(chǎn)生

2、。在計(jì)算機(jī)中廣泛使用的是軟件方式,通過計(jì)算機(jī)利用數(shù)學(xué)模擬隨機(jī)過程產(chǎn)生隨機(jī)數(shù)。此方法有著自身的不足,數(shù)據(jù)之間有著關(guān)聯(lián)性,存在周期,并非真正的隨機(jī)數(shù),因此被成為偽隨機(jī)數(shù)。    常見的產(chǎn)生隨機(jī)數(shù)的方法有1：線性同余法（LCG,Linear Congruent Generators）、Tarsworthe位移計(jì)數(shù)器法、Fibonacci延遲產(chǎn)生器法等。為了克服以上方法的缺陷,人們還發(fā)展了許多新的方法。組合發(fā)生器就是著名的一種。它是將兩個(gè)隨機(jī)數(shù)發(fā)生器進(jìn)行組合,以一種發(fā)生器產(chǎn)生一個(gè)隨機(jī)數(shù)列,再用另一個(gè)隨機(jī)數(shù)發(fā)生器對(duì)隨機(jī)數(shù)列進(jìn)行重修排列,得到一個(gè)更為獨(dú)立,周期更長的隨機(jī)數(shù)列。已有一些利

3、用混沌序列轉(zhuǎn)換偽隨機(jī)數(shù)列的報(bào)道2,文獻(xiàn)3雖然提出了一種由logistic映射構(gòu)造具有均勻性數(shù)列的好方法,但數(shù)據(jù)之間的獨(dú)立性較差。本研究中提出了一種新的方法,利用混沌算法4和線性同余發(fā)生器相組合得到隨機(jī)數(shù)列,并就數(shù)據(jù)的均勻性和獨(dú)立性進(jìn)行了檢驗(yàn)。    2  理論基礎(chǔ)    2.1  混沌算法    混沌是一種確定性系統(tǒng)中出現(xiàn)的類似隨機(jī)的過程。它首先是由洛倫茲在流體熱對(duì)流的簡化模型計(jì)算中觀察到的?；煦绗F(xiàn)象可以用它某些非線性函數(shù)的迭代（映射）來表示類似隨機(jī)的輸出。一維迭代Logistic方程是一個(gè)很簡

4、單的非線性拋物線函數(shù),可以表示為：    xi+1=xi(1-xi),    (0xi1,    04)    (1)    xi 是i 次迭代的值。研究表明當(dāng)>3.57 時(shí),進(jìn)入混沌狀態(tài)。特征是表現(xiàn)為初值敏感性,既使初值相差非常小,經(jīng)過幾十次迭代，得到的值也會(huì)相差非常大，并且毫無關(guān)聯(lián)。當(dāng)=4 時(shí),序列xi 的概率分布服從    P(xi)=1xi(1-xi)(2)    所以xi 序列分布并不均勻，通過代換    ri=2arc

5、sinxi(3)    就可以得到均勻的ri 數(shù)列。    2.2  線性同余發(fā)生器    線性同余發(fā)生器是現(xiàn)在使用最多的隨機(jī)數(shù)發(fā)生器之一，該方法利用同余運(yùn)算產(chǎn)生隨機(jī)數(shù)。    Ii+1=(aIi+b)mod m    xi=Iim  (4)    其中m 為模數(shù), a為乘子, b為增量,并且a,b,m,I1 均為非負(fù)整數(shù)。如何選擇他們就決定了產(chǎn)生器的質(zhì)量。在計(jì)算中取a=16807,b=0,m=231-1,I1=12546863 。顯然

6、,由公式(4)得到的Ii 滿足：0Ii m,所以0xi1 。線性同余法的優(yōu)點(diǎn)就是速度快,每次調(diào)用只需幾個(gè)操作步驟即可,因此最為常用.缺點(diǎn)就是數(shù)據(jù)序列的有著關(guān)聯(lián)性,表現(xiàn)為高維稀疏網(wǎng)格結(jié)構(gòu)5。特別是當(dāng)a 和m 的值較小時(shí),這種現(xiàn)象更為明顯。    2.3  組合發(fā)生器    20世紀(jì)70年代就有人提出用用組合發(fā)生器來產(chǎn)生高質(zhì)量的偽隨機(jī)數(shù)。有文獻(xiàn)6對(duì)此進(jìn)行了理論分析并指出：幾個(gè)獨(dú)立且近似的隨機(jī)變量的線性組合也是一個(gè)近似均勻的隨機(jī)變量,其分布比組成它的任何一個(gè)變量更接近U（0，1）。    該算法是分別用兩個(gè)發(fā)生器各自產(chǎn)生

7、一組隨機(jī)數(shù)列,然后再把它們進(jìn)行相互組合,以期得到一個(gè)統(tǒng)計(jì)結(jié)果更好的隨機(jī)數(shù)列。具體步驟如下：    N個(gè)不同的隨機(jī)數(shù)發(fā)生器各自產(chǎn)生一組隨機(jī)數(shù)列 Xi（j)(i=1,2,L,  j=1,2,N)。    令c1,c2,cN 為N個(gè)非負(fù)整數(shù)。    Ui=Nj=1c(j)Xi(j)    ri=Ui mod 1    i=1,2,   (5)    按上述算法把混沌算法和線性同余產(chǎn)生的隨機(jī)數(shù)組合在一起。在計(jì)算中,取c1=2,c2=5 。每個(gè)發(fā)

8、生器都有其各自的周期Period(Xi) ,如果它們互素,則組合后的周期是各自周期的最小公倍數(shù)（LCM）。Period(Xi)=LCM(Period(Xi(1)）,Period(Xi(2),)。因此組合發(fā)生器產(chǎn)生數(shù)據(jù)的周期會(huì)大大增加,實(shí)際應(yīng)用中可視為無窮大。    3  隨機(jī)數(shù)的統(tǒng)計(jì)檢驗(yàn)    隨機(jī)數(shù)的好壞是通過各種統(tǒng)計(jì)檢驗(yàn)來確定的,這些檢驗(yàn)包括均勻性檢驗(yàn)、獨(dú)立性檢驗(yàn)、參數(shù)檢驗(yàn)等。其中最基本的是均勻性檢驗(yàn)和獨(dú)立性檢驗(yàn)。在隨機(jī)數(shù)的檢驗(yàn)中獨(dú)立性檢驗(yàn)是首要的,如果不存在獨(dú)立性就無所謂隨機(jī)。也希望得到的隨機(jī)數(shù)在區(qū)間0，1 上出現(xiàn)的概率是相同的

9、,所以均勻性檢驗(yàn)也起著決定作用。    3.1  均勻性檢驗(yàn)    假設(shè)區(qū)間0，1上的隨機(jī)數(shù)列Xi(i=1,2,n)。如果隨機(jī)數(shù)分布均勻,則把區(qū)間分成k 個(gè)相等的子區(qū)間后,落在每個(gè)子區(qū)間的隨機(jī)數(shù)個(gè)數(shù)ni 近似等于n / k 。統(tǒng)計(jì)量2 按定義為:    2=ki=1(ni-n / k)2n / k   (6)    2 應(yīng)服從2(k-1) 分布,在給定一個(gè)顯著水平 下,可查表得到臨界值2(k-1)。如果2>2 ,則拒絕均勻假設(shè)。    3.2

10、0; 獨(dú)立性檢驗(yàn)    對(duì)獨(dú)立性檢驗(yàn)中的相關(guān)檢驗(yàn)基于相關(guān)系數(shù)r 。把隨機(jī)數(shù)列ri(i=1,2,2n) 分成兩部分Xi(i=1,3,2n-1),Yi(i=2,4,2n ,相關(guān)系數(shù)r 為:    r=1nni=1(Xi-)(Yi-)1nni=1(Xi-)2  1nni=1(Yi-)2  (7)    當(dāng)=(1.96)2+n-2 |r|1.96 時(shí), 認(rèn)為線性回歸效果顯著,拒絕獨(dú)立檢驗(yàn)。    3.3  參數(shù)檢驗(yàn)    隨機(jī)數(shù)列Xi

11、(i=1,2,n) ,其一階矩、二階矩和二階中心矩分別為:    =1nni=1Xi,  2=1nni=1Xi2, s2=1nni=1(Xi-12)2   (8)    對(duì)于均勻分布的數(shù)列,其值分別為12, 13,112 。如果與理論值沒有顯著差別，則通過參數(shù)檢驗(yàn)。    檢驗(yàn)中,3種發(fā)生器分別生成100000個(gè)數(shù)據(jù),對(duì)其統(tǒng)計(jì)性質(zhì)進(jìn)行了分析。取檢驗(yàn)的置信度=0.05 ,在均勻檢驗(yàn)中，檢驗(yàn)區(qū)間k=500 ,2(500)>552.78 時(shí)拒絕均勻假設(shè)7；獨(dú)立性檢驗(yàn)中=(1.96)2+n-2 |

12、r|1.96,拒絕獨(dú)立假設(shè)。表1  隨機(jī)數(shù)列的統(tǒng)計(jì)結(jié)果 從表1的統(tǒng)計(jì)結(jié)果可以看出,組合后的發(fā)生器表現(xiàn)出了更為優(yōu)秀的統(tǒng)計(jì)結(jié)果.在數(shù)據(jù)的獨(dú)立性和均勻性上都大大增加。    混沌算法雖然可以通過均勻性檢驗(yàn),但獨(dú)立性較差,沒有通過獨(dú)立性檢驗(yàn),不宜單獨(dú)作為隨機(jī)數(shù)發(fā)生器使用.如果把數(shù)列中相鄰兩個(gè)數(shù)據(jù)作為（x,y) ,分別作出各個(gè)數(shù)列的二維散布圖。不難看出,圖1混沌算法得到的隨機(jī)數(shù)列,數(shù)據(jù)之間有著強(qiáng)烈的關(guān)聯(lián),數(shù)據(jù)之間并不獨(dú)立。圖2和圖3數(shù)據(jù)分布則比較均勻。   4  結(jié)論    計(jì)算機(jī)模擬、信息加密或Mont

13、e Carlo方法成功的基礎(chǔ)是實(shí)現(xiàn)真正的隨機(jī)抽樣,隨機(jī)抽樣的基礎(chǔ)是隨機(jī)數(shù)。從以上統(tǒng)計(jì)結(jié)果可以看出,兩種發(fā)生器組合之后,得到的隨機(jī)數(shù)列具有更好的統(tǒng)計(jì)結(jié)果,在保持均勻性的基礎(chǔ)上,獨(dú)立性有了較大的提高。并且組合后,隨機(jī)數(shù)列的周期可視為無窮大。因此該方法具有良好的統(tǒng)計(jì)性質(zhì),符合隨機(jī)數(shù)的要求?！緟⒖嘉墨I(xiàn)】  1 楊自強(qiáng),魏公毅. 產(chǎn)生偽隨機(jī)數(shù)的若干新方法.數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用,2001,3:210216.2 孫霞,吳自勤,黃畇,分形原理及其應(yīng)用.中國科學(xué)技術(shù)大學(xué)出版社 2003,122.3 盛利元,肖燕予,盛喆,將混沌序列變換成均勻偽隨機(jī)序列的普適算法.物理學(xué)報(bào),2008,57：44074412.4 周燕,覃朝玲 用混沌法產(chǎn)生隨機(jī)數(shù)發(fā)生器的研究.西南師范大學(xué)學(xué)報(bào),2000,25：150154.5 羅平. 線性同余發(fā)生器的缺陷及其改進(jìn).計(jì)算機(jī)工程,1995,21：295297.6 De