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

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

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

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

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

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

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

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

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

10、0; 獨立性檢驗    對獨立性檢驗中的相關(guān)檢驗基于相關(guān)系數(shù)r 。把隨機數(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 時, 認(rèn)為線性回歸效果顯著,拒絕獨立檢驗。    3.3  參數(shù)檢驗    隨機數(shù)列Xi

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

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

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