計算機是如何實現「隨機生成一個數字」這種功能的？

01-14

本人大學信息專業，上學時就對random之類的函數特別好奇。計算機是一種說1就是1的機器，生成隨機數這種動作是如何完成的？把時間作為參數？或者什麼東西？
網頁上登錄帳號時生成的驗證碼，還有播放歌曲時隨機播放的排序，原理又是什麼樣的？

偽隨機數

就是那種從種子挨個生成的隨機數，一般是用線性同餘： $N_{j+1}=A N_j+B mod M$ ，如 GCC 里 $M=2^{31}$ ，A = 1103515245，B = 12345

比較高端的是梅森旋轉，可以產生質量更好的隨機數。

真隨機數

用於密碼的真隨機數一般是靠收集硬體信息，可以利用硬體的雜訊來生成，當前時間也有用處。

不過我也見過喪心病狂的，比如一些 FC 遊戲會用未初始化的內存作為隨機數種子……

還有一些是用用戶操作生成的，比如叫你劃屏幕一段時間，然後傅里葉出高頻部分……

事實上絕大多數random函數都是用偽隨機數生成器的方式來做的，一種最普遍的方法就是確定四個係數x0, a, b, m

然後有x[i] = (a * x[i - 1] + b) mod m

其中x0就叫做隨機數種子，一般開放給程序員修改的就是這個種子了

例如c中的srand函數，其參數就是程序員想要設置的種子

unix系統通常會有一個真隨機數設施，通過電腦當前的一些狀態生成，會比較慢。

偽隨機數演算法很多，你自己搜pseudo random number generator好了。

現在性能比較好的一個PRNG是MT旋轉法（常用MT19337）。只是它不加密，得到兩個相鄰的輸出就可以推出prng的內態。

無恥的複製粘貼：

真隨機數

　　如果電腦是靠代碼生成隨機數，是不是意味著隨機數可以被預測?

　　根據隨機數的生成原理，我們把電腦隨機數分為兩類：「真」隨機數和偽隨機數。

　　要生成一個「真」隨機數，電腦會檢測電腦外部發生的某種物理現象。比如說，電腦可以測量某個原子的放射性衰變。根據量子理論，原子衰變是隨機而不可測的，所以這就是宇宙中的「純粹」隨機性。攻擊者永遠無法預測原子衰變的發生時間，也就不可能猜出隨機值。

　　舉個更實際的例子，電腦會根據環境中的噪音或者採取你敲擊鍵盤的精確時間作為隨機數據或熵的生成依據。舉個例子，你的電腦監測到你某天下午2點以後敲擊鍵盤的精確時間是0.23423523秒，有足夠的這些特定長數字你就能得到一個熵源，也就可以生成「真」隨機數。由於人不是機器，所以攻擊者無法掌握你的敲擊時間。Linux中的/dev/隨機設備生成隨機數，「阻攔」訪問直到熵積累量足夠才返回一個真隨機數。

真隨機數

　　如果電腦是靠代碼生成隨機數，是不是意味著隨機數可以被預測?

　　根據隨機數的生成原理，我們把電腦隨機數分為兩類：「真」隨機數和偽隨機數。

以上

以下，作為信息專業畢業，簡單的編碼應該是沒問題了，實際上面的問題「random之類的函數特別好奇。計算機是一種說1就是1的機器，生成隨機數這種動作是如何完成的？把時間作為參數？或者什麼東西？

網頁上登錄帳號時生成的驗證碼，還有播放歌曲時隨機播放的排序」

我所了解的random這類的函數基本都是使用的偽隨機數，像上面的兄弟們說的，選取某個時間seed，或者硬體中間某個可取值之類的，作為熵源，再根據你的隨機數長度類型要求生成。

播放歌曲隨機，實際就是你建了個list，random這個list下的某個序列，具體參考以上。

驗證碼，我了解的應該是兩類。

1、此類是圖靈系可以參考圖靈的資料，相對較全。

2、此類是google提出的一個原始書籍翻譯計劃，實際上google也做不到文本書籍整理成電子書籍，成本太高，所以為了節省人力識別成本，將書籍中的片段截取，作為一類驗證碼，要求登陸用戶輸入，並作多次驗證確認，這樣就對抗的ai機器人登陸灌水，又能夠保護文化資料的傳承。

另外該技術進入中國後，就變成了廣告推廣的了，具體參考某軍軟體下載的下載驗證碼。

最後，忘記是再哪兒看到的，09-10年期間，yuange1975和tk之間貌似有過一次關於硬體隨機數生成的交流，資料沒存腦子裡，下次找到再發。

根據拉普拉斯的宿命論（唯一性定理）可知，所有隨機函數都是偽隨機函數。

《csapp》上有一個非常naive的rand()實現方法可以作為參考：

/* $begin rand */ unsigned int next = 1;


/* rand - return pseudo-random integer on 0..32767 */

int rand(void)

{

    next = next*1103515245 + 12345;

    return (unsigned int)(next/65536) % 32768;

}

/* srand - set seed for rand() */ void srand(unsigned int seed) { next = seed; } /* $end rand */

srand() 函數的種子由位移寄存器生成，一般來說是來自一個不會重複的數比如時間，對cpu來說就是本身的時鐘頻率。得到種子以後交給rand()，由rand()來生成隨機數，得出的隨機數是int型。

說的可能有不對的地方望指正，都是以前上計算機組織結構留下的一點記憶

用時間做種子或者用外部輸入的信息比如開機以來按了多少次鍵，主板電壓是多少，啟動了多少個進程，當前所有pid總和是多少之類的信息做種子。