隨機數在我們生活工作中無處不在,一組真正的隨機數列呢,應該具有哪些特性呢?
等機率性
在隨機序列中,每個數字出現的機率應該相等,對應於二進位制,也就是
0和1的出現機率應該相等
。顯然這個樸素的,可以使用反證法。如果0和1出現的機率不一樣,比如1的機率為51,0點機率為49,則我們可以以51%的機率預測下一個數字為1,超過一半的機率了,顯然已經不隨機了。
滿足這個條件就一定是隨機數序列了嗎?顯然也不對。類似0101010101……這樣的迴圈序列顯然也不是隨機的。所以還需要下面的條件
獨立性
根據前面的已知資訊,無法以
大於1/2的機率推測出下一個數字為0或者為1
。就像彩票,知道了前面那麼多期的結果,可是還是中不了大獎。
如果給了一個電腦,如何編寫程式構造隨機序列呢?現在使用的方法主要有下面二種思路。
獲取物理資訊,轉換成隨機數。
Linux中專門提供了兩個隨機數生成裝置(也就是檔案,對於linux來說,一切皆是檔案),分別是
/dev/urandom和dev/random
。他們是利用
系統的熵
來生成隨機數。學過物理和資訊理論或者相關學科應該知道,熵是一種刻畫系統混亂程度的度量,隨著時間的流逝,封閉系統的熵會越來越大。對於計算機,有個熵池,專門收集記憶體、檔案、CPU、程序等的資訊來表徵熵。如果當前系統很穩定,比如剛開機的時候,或者待機的時候,熵增加的就慢,隨機性就不好。
對於 /dev/urandom和/dev/random來說,random依賴於系統中斷,當系統中斷數不足時,裝置會禁止訪問,其他程序會阻塞,直到根據熵池產生新的隨機位元組之後才返回。對於urandom,則不會(ublock),但是產生的隨機數效果就不太好了。
使用指令
rdrand
或者
rdseed
Inter對CPU提供了
rdrand
和
rdseed
指令,專門用來提供隨機數。具體的差別可以參考文件 The Difference Between RDRAND and RDSEED。Inter的建議如下:
如果您希望播種另一個偽隨機數生成器(PRNG),請使用RDSEED
出於所有其他目的,請使用RDRAND
上面的程式碼,透過rdrand讀取隨機數,放入暫存器r1、r2、r3、r4中。
使用偽隨機數生成器
使用random()或者rand()
C語言自帶的,對隨機性和安全性要求不高的,可以選擇使用。
使用密碼演算法生成偽隨機數
密碼演算法(加密演算法,雜湊演算法)等都有很好的偽隨機性。具體來說,給定輸入,不能預測輸出,即使知道很多對輸入和輸出。常見的一個應用場景就是網上銀行的u盾,會不斷的生成一串數字。這些演算法都是
偽隨機
的,在執行足夠長的時間後,將會變成迴圈序列,只不過迴圈的週期很長很長。很多的密碼庫和數學庫都提供有此類庫,比如openssl等。