wrhwww

偽隨機數生成

摘要偽隨機數在計算機軟件設計中有很廣泛的用途。本文介紹了基于數學方法的利用計算機產生偽隨機數的一種方法，即線性同余法，任何偽隨機數的產生都是運用遞推的原理來生成的。

以及在Visual C++環境中產生偽隨機數的兩個重要函數，rand和srand函數，正確地使用這兩個函數是產生性能良好的偽隨機數的關鍵，最后介紹了利用偽隨機數生成技術在MFC中生成基于C/S模式應用程序的隨機校驗碼以及利用一種軟件工具ImagePassword產生隨機密碼。

　　關鍵詞偽隨機數生成；線性同余法；Visual C++；隨機校驗碼

　　為追求真正的隨機序列，人們曾采用很多種原始的物理方法用于生成一定范圍內滿足精度（位數）的均勻分布序列，其缺點在于：速度慢、效率低、需占用大量存儲空間且不可重現等。為滿足計算機模擬研究的需求，人們轉而研究用算法生成模擬各種概率分布的偽隨機序列。偽隨機數是指用數學遞推公式所產生的隨機數。從實用的角度看，獲取這種數的最簡單和最自然的方法是利用計算機語言的函數庫提供的隨機數發生器。典型情況下，它會輸出一個均勻分布在0和1區間內的偽隨機變量的值。其中應用的最為廣泛、研究最徹底的一個算法即線性同余法。

　　線性同余法LCG（Linear Congruence Generator）

　　選取足夠大的正整數M和任意自然數n0，a，b，由遞推公式：

ni+1=（af（ni）+b）mod M i=0，1，…，M-1
　　生成的數值序列稱為是同余序列。當函數f（n）為線性函數時，即得到線性同余序列：

ni+1=（a*ni+b）mod M i=0，1，…，M-1
　　以下是線性同余法生成偽隨機數的偽代碼：

Random（n，m，seed，a，b）
{
　r0 = seed；
　for （i = 1；i<=n；i++）
　ri = （a*ri-1 + b） mod m
}

　　其中種子參數seed可以任意選擇，常常將它設為計算機當前的日期或者時間；m是一個較大數，可以把它取為2w，w是計算機的字長；a可以是0.01w和0.99w之間的任何整數。

　　應用遞推公式產生均勻分布隨機數時，式中參數n0，a，b，M的選取十分重要。

　　例如，選取M=10，a=b =n0=7，生成的隨機序列為{6，9，0，7，6，9，……}，周期為4。

　　取M=16，a=5，b =3，n0=7，生成的隨機序列為{6，1，8，11，10，5，12，15，14，9，0，3，2，13，4，7，6，1……}，周期為16。

　　取M=8，a=5，b =1，n0=1，生成的隨機序列為{6，7，4，5，2，3，0，1，6，7……}，周期為8。

　　Visual C++中偽隨機數生成機制

　　用VC產生隨機數有兩個函數，分別為rand（void）和srand（seed）。rand()產生的隨機整數是在0~RAND_MAX之間平均分布的，RAND_MAX是一個常量（定義為：#define RAND_MAX 0x7fff）。它是short型數據的最大值，如果要產生一個浮點型的隨機數，可以將rand()/1000.0，這樣就得到一個0~32.767之間平均分布的隨機浮點數。如果要使得范圍大一點，那么可以通過產生幾個隨機數的線性組合來實現任意范圍內的平均分布的隨機數。

　　其用法是先調用srand函數，如

srand( (unsigned)time( NULL ) )
　　這樣可以使得每次產生的隨機數序列不同。如果計算偽隨機序列的初始數值（稱為種子）相同，則計算出來的偽隨機序列就是完全相同的。要解決這個問題，需要在每次產生隨機序列前，先指定不同的種子，這樣計算出來的隨機序列就不會完全相同了。以time函數值（即當前時間）作為種子數，因為兩次調用rand函數的時間通常是不同的，這樣就可以保證隨機性了。也可以使用srand函數來人為指定種子數。
分析以下兩個程序段，

　　程序段1：

//包含頭文件 
void main() {
　int count=0;
　for (int i=0;i<10;i++){
　　srand((unsigned)time(NULL)); 
　　count++;
　　cout<<"No"<
　　程序段1中由于將srand（）函數放在循環體內，而程序執行的CPU時間較快，調用time函數獲取的時間精度卻較低（55ms），這樣循環體內每次產生隨機數用到的種子數都是一樣的，因此產生的隨機數也是一樣的。而程序段2中第1次產生的隨機數要用到隨機種子，以后的每次產生隨機數都是利用遞推關系得到的。
基于MFC的隨機校驗碼生成





　　Web應用程序中經常要利用到隨機校驗碼，校驗碼的主要作用是防止黑客利用工具軟件在線破譯用戶登錄密碼，校驗碼、用戶名、密碼三者配合組成了進入Web應用系統的鑰匙。在利用VC開發的基于客戶機/瀏覽器（Client/Server）模式的應用軟件系統中，為了防止非法用戶入侵系統，通常也要運用隨機校驗碼生成技術。

　　本實現要用到以上介紹到的偽隨機數生成技術。校驗碼數據將以16進制碼方式顯示。主要代碼如下：

void CRandompasswordDlg::OnCreatekey() {
　int RanCheckNum = 0;
　char out[25]={0};
　char keytemp[5]={0};
　memset(out,0x30,18);
　srand((unsigned)timeGetTime());//產生隨機數種子
　for(int i=0;i<6;i++){ 
　　RanCheckNum = rand();//產生隨機數
　　_itoa(RanCheckNum,keytemp,16);//將隨機數轉換成16進制
　　memcpy(&out[i*4],keytemp,strlen(keytemp));
　}
　out[24]=0x00;
　strcpy(m_key.GetBuffer(18),out);
　UpdateData(FALSE);
}
　　運行結果如圖1所示：



圖1 利用偽隨機數生成隨機校驗碼
　　程序運行時，由于每一次點擊"產生隨機校驗碼"的系統時間不同，生成隨機數的種子就不一樣，因此產生的隨機數也是不一樣的，從而保證了校驗碼生成的隨機性。

　　利用ImagePassword工具產生隨機密碼

　　ImagePassword提供一個可選擇的圖形陣列，通過隨機改變圖形陣列中的陣點圖形來產生隨機密碼。當隨機點擊圖象陣列中的圖象陣點，該陣點中的圖象發生變化。其運行界面如圖2所示：



圖2 ImagePassword運行界面
　　點擊OK按鈕后所產生的隨機密碼如圖3所示： 



圖3 ImagePassword運行結果
　　ImagePassword產生的密碼的隨機性依賴于用戶對圖象陣列中陣點圖象的隨機選擇，一般來說用戶在圖象陣列中隨機點擊鼠標的次數越多，最后產生的密碼的隨機性越強。

　　結束語

　　偽隨機數在不同的軟件系統中都得到了很廣泛的應用，如何選擇隨機數生成種子使得生成的偽隨機數性能更佳是軟件設計者追求的目標之一。本文提到了利用系統時間作為種子參數在一定條件下可以滿足軟件的隨機性需要。利用所產生的隨機數在游戲編程，如撲克類游戲中的隨機發牌，俄羅斯方塊的隨機生成等等其他應用中都起到很重要的作用。