偽隨機數(shù)的產(chǎn)生及其性能評價

1、偽隨機數(shù)的產(chǎn)生及其性能評價偽隨機數(shù)的產(chǎn)生及其性能評價吳軍1呂敏2雷金娥3（1.重慶大學(xué)光電工程學(xué)院，重慶4000301；2.中國科學(xué)技術(shù)大學(xué)計算機學(xué)院，合肥230026；3.南昌工程學(xué)院計算機系，南昌330099）摘要：摘要：系統(tǒng)仿真或加密算法中常需要產(chǎn)生滿足一定分布函數(shù)的偽隨機數(shù)，高級程序設(shè)計語言中的庫函數(shù)采用線性同余法產(chǎn)生一個在[032767]服從均勻分布的偽隨機數(shù)，但每次程序運行的結(jié)果都是相同的，利用當(dāng)前系統(tǒng)時間和數(shù)學(xué)方法可以產(chǎn)生

2、滿足各種分布要求的偽隨機數(shù)。以CC為例，采用概率統(tǒng)計的方法檢驗了產(chǎn)生的偽隨機數(shù)是否符合給定分布函數(shù)的要求，并且其隨機性、均勻性等統(tǒng)計特性是否滿足實際應(yīng)用的需要。關(guān)鍵字：關(guān)鍵字：偽隨機數(shù)CC統(tǒng)計檢驗；均勻分布；正態(tài)分布；指數(shù)分布中圖分類號：中圖分類號：TP文獻(xiàn)標(biāo)識碼：文獻(xiàn)標(biāo)識碼：1、引言、引言在計算機仿真和模擬、密碼學(xué)等應(yīng)用中，常需要產(chǎn)生一些隨機數(shù)，自然界中存在大量的隨機現(xiàn)象，但在計算機中，只能產(chǎn)生滿足一定要求的偽隨機數(shù)來模擬真實世界中的

3、隨機現(xiàn)象。產(chǎn)生偽隨機數(shù)的方法有硬件方法和軟件方法，硬件方法可以在計算機上附上一個硬設(shè)備或者采用移位寄存器來產(chǎn)生偽隨機數(shù)；軟件方法一般都采用數(shù)學(xué)公式法。近年來在計算機中，比較廣泛使用的方法就是同余法，而在高級程序設(shè)計語言中常采用線性同余法[8]。每次生成的偽隨機數(shù)需要滿足獨立的條件及給定分布函數(shù)的要求，但高級程序設(shè)計語言中提供的庫函數(shù)產(chǎn)生的偽隨機數(shù)都是滿足一定條件的均勻分布隨機數(shù)，且在同一次程序運行中，每次產(chǎn)生的偽隨機數(shù)是完全相同的，本文

4、將介紹利用一些數(shù)學(xué)變換方法產(chǎn)生在任意區(qū)間內(nèi)服從任意分布的偽隨機數(shù)，并進(jìn)行統(tǒng)計檢驗以檢查其是否能滿足要求。文獻(xiàn)[14]提出了一種比較好的尾數(shù)和檢驗法，但比較復(fù)雜，本文采用較為簡單的頻率統(tǒng)計法。2、R函數(shù)和線性同余算法函數(shù)和線性同余算法C語言中提供的r()函數(shù)可以產(chǎn)生一個從0到32767服從均勻分布的正整數(shù)，r()函數(shù)即采用了線性同余算法。該算法如下：取足夠大的正整數(shù)m（一般取計算機精度范圍內(nèi)能夠表示的最大整數(shù)）和任意的自然數(shù)a，X0，b。

5、其中i＝1、2、3……，mod表示取余。（1）mbaXXiimod)(1???（1）式中a為乘子，X0為種子，b為常數(shù)，m為模。線性同余法是一種遞歸算法，即先提供一個種子X0，逐次遞歸即得到一個不超過模m的整數(shù)數(shù)列?？梢钥闯鲇纱水a(chǎn)生的數(shù)列并不是真正的隨機數(shù)，但是提供一個隨機的種子，產(chǎn)生的數(shù)列在0～m循環(huán)，如果產(chǎn)生大量的整數(shù)密集分布在[0，m]上，就可以近似認(rèn)為服從[0，m]上的均勻分布。把數(shù)列除以m，就得到服從[0，1]上的均勻分布。3

6、、偽隨機數(shù)性能評價的基本原理、偽隨機數(shù)性能評價的基本原理隨機性和均勻性檢驗采用頻率統(tǒng)計檢驗法，該算法原理如下：收稿日期：收稿日期：200941基金項目：基金項目：南昌工程學(xué)院青年基金科技項目(2006KJ029)作者簡介：作者簡介：吳軍（1977），男，四川達(dá)州人，在讀博士，主要從事嵌入式和操作系統(tǒng)方面的研究。Email:wj2135187@，手機：13668013619通訊作者：通訊作者：吳軍，wj2135187@選法的效率。③組合法

7、：如果需要生成的偽隨機數(shù)服從分布函數(shù)F(x)，F(xiàn)(x)可以用其他更簡單的分布函數(shù)F1，F(xiàn)2，…，F(xiàn)m的凸組合表達(dá)時，即假定對所有的x，，其中???miiixFpxF1)()(pi≥0，。則可以先產(chǎn)生服從Fi的m個隨機數(shù)數(shù)列，然后再利用這些隨機數(shù)數(shù)列11???miip的組合得到服從F(x)分布的偽隨機數(shù)。④經(jīng)驗分布法：主要用于產(chǎn)生離散分布的隨機數(shù)?，F(xiàn)實中很多隨機現(xiàn)象的理論分布往往無法確切得出，但可以根據(jù)它們的經(jīng)驗公式來模擬抽樣。⑤近似法：

8、對于分布函數(shù)比較復(fù)雜，難以對其求解的情況下，可以利用一些定理或公式來近似產(chǎn)生偽隨機數(shù)。比如正態(tài)分布的分布函數(shù)比較復(fù)雜，對其求反函數(shù)也比較困難，則可以利用中心極限定理來近似得出服從正態(tài)分布的偽隨機數(shù)。5、各種偽隨機數(shù)的生成方法及其評價、各種偽隨機數(shù)的生成方法及其評價①均勻分布偽隨機數(shù)的產(chǎn)生：設(shè)r_MAX＝32767、dR＝r()r_MAX，則dR就是一個滿足[0，1]均勻分布的偽隨機數(shù)，其中r()函數(shù)是CC中的庫函數(shù)，r_MAX是16位字

9、長計算機中int型變量能夠表示的最大正整數(shù)。如果要產(chǎn)生[a，b]上均勻分布的偽隨機數(shù)，可以采用適當(dāng)?shù)木€性變換。文獻(xiàn)[13]中為了提高隨機性，采用了平方的方法，可以證明均勻分布的變量平方后不再服從均勻分布，頻率直方圖也出現(xiàn)了較大的跳躍，所以不能滿足要求。CC中可以用如下的代碼來實現(xiàn)任意區(qū)間[a，b]上均勻分布的偽隨機數(shù)。產(chǎn)生[a，b]上均勻分布的偽隨機數(shù)可以用如下的偽代碼來實現(xiàn)：voidEquR(doubledRan，doublea，do

10、ubleb)unsignedintseedValstructtimebtimeBufftime(seedVal=((((unsignedint)timeBuf.timesr((unsignedint)seedVal)f(i=0inum_MAXi)dTemp=(double)r()r_MAX(dRani)=dTemp(ab)bCC中需要提供一個種子給r()函數(shù)，該算法中用系統(tǒng)當(dāng)前時間來作種子，以保證每次得到的偽隨機數(shù)都不同，即各次產(chǎn)生的偽