計算機是怎麼理解隨機的?

01-16

吶，我很好奇當我們要求計算機輸出一個隨機數，他是基於什麼邏輯，能搞出一個數呢？

1：正統的做法是構造一個函數，使得輸入輸出的響應呈現很長的周期性，這樣就難以預測下一個輸出，成為我們一般所說的「偽隨機」。由於這種方法計算量小，所以在沒有很高隨機性或者其他特殊要求的情況下，一般都是用這種方法輸出。

2：更高一點的就是隨機熵池。就是利用計算機系統的各種「隨機」事件（例如說io等），匯總到熵池中，然後再作為隨機數輸出。在很多對隨機數安全性要求較高的場合：例如說密碼、驗證碼、賭博洗牌等場合都會用這類方法。但是這方法本質上還是偽隨機（只要復現熵池加入元素及順序即可重現輸出序列），只是絕大多數情況下，這都是難以做到的。

3：真正隨機數必須通過硬體，然後放大某些物理理論上已經證明為隨機的事件，從而獲得輸出。最常見的就是放大電路的白雜訊，還有例如說放射性同位素的衰變等也可以。這些產生的就真的是隨機數，而且以現有物理學理論來看，在理論上和實踐上都是無法精確預測和復現的。

-------------------------------------------------------------------

後面再提一下「隨機」這個問題，其實這個問題之前還真的沒有仔細考慮過，昨晚仔細想了一下，還真的不那麼簡單。這裡先要感謝一下 @竹海的提問。

事實上隨機這個概念，在不同領域是有不同的表述的。而且從純邏輯來說，給你一串有限長度的數字序列，無論它有多長或者多短，其實你都是不可能證明它是隨機序列的一個子序列。

道理其實不難：假定你的數字序列為N位，那你是無法保證它是不是一個周期為大於等於N的周期重複序列的一個子序列。

至於是無限長的序列，那要看看數學上有沒有什麼工具來證明這點了，我對這方面不太熟。

在物理上，隨機性的概念來自於物理的隨機過程。

常見的在物理上的隨機過程大概有：熱力學領域的分子熱運動（各種雜訊、布朗運動等）、量子效應（不確定性原理、原子衰變等）、混沌效應（蝴蝶翅膀）等。

如果嚴謹的說證明，只能說前兩類是一個來源的：不確定性原理。但是這個隨機性到底是來自於它的本身特性呢？還是說因為我們某些未發現的物理定律呢（所謂的隱變數）？這個其實物理界一直都有爭論，只能按照我所知道的照本宣科：主流認為，這種隨機性是量子本身的特性。

混沌效應就真的不了解了，有知道的歡迎補充。

那麼由這裡產生的序列如何證明它的隨機性呢？我只能說是以現有的物理定律來保證了。但是如果說到以後會不會又發現個什麼理論來推翻這個呢？雖然我相信概率極低，但是我覺得是沒法保證這點的。

那對於計算機領域來說，「隨機」這個概念又和物理上和數學上的略有不同的。我們說一個輸出序列是「隨機」的，一般包含兩重意思：

1：知道有限長的歷史序列，無法（以較高的準確率）預測下一個輸出數字；

2：無法通過技術手段，使設備（軟體/硬體）重現一樣的輸出序列；

其中第一條是基本要求，而且可以允許攻擊者有一定的預測失誤概率。例如說如果我站在一台老虎機面前一天，連續記錄他的所有結果（有限長的歷史序列），如果這時我能以10%的準確率預測它下一次的結果，那接下來會發生什麼事情大家可以盡情猜想了。

第二條是要求更高一點的完全破解。因為能重現的話，基本上就意味著完全破解了演算法和各項細調參數。

但是，物理上的隨機過程，雖然無法精確預測下一個輸出序列是什麼，但是在統計意義上，是可以根據各種定理，判定下一個輸出有較大概率出現在哪個區間的（例如說正態分布、冪律分布等）。

所以，實際應用中，物理隨機源應該是在取出隨機數種子之後，要在內部做一層轉換，把這些統計規律給抹掉才行，要不然就真的可能出現以10%的準確率預測老虎機的下一個結果了---這點我之前也沒有注意到。

另外，在某些情況下，例如說做測試的時候，復現隨機序列是必須的。這時候，就只能使用偽隨機，而不能使用真隨機。所以在要求較高的開發中，一般會在隨機數模塊有一個開關，在測試環境用偽隨機源，而生產環境用真隨機源。

首先，取一個種子數，比如當前時間（秒數）T。

然後構造一個方程，使得連續的T代入方程後產生的數值相差很大，這樣就「製造」了一個隨機的假象。

比如最簡單的線性同餘法：

rand(n+1) = (A * rand(n) + B) % M

rand(0) = T

這裡A,B,M是滿足一定條件的幾個常數。

換句話說，如果知道了隨機種子和隨機方程，是完全可以預測出下一個隨機數是多少的。這就是「偽」隨機的意思。

貼一個《kr》的代碼

unsigned long int next = 1;

int rand(void)

{

next = next * 1103515245 + 12345;

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

}

void srand(unsigned int seed)

{

next = seed;

}

凱文米特尼克《入侵的藝術》的第一章，講的就是90年代幾個年輕人利用計算機產生偽隨機數的漏洞，在拉斯維加斯的賭博機上大賺特賺的故事。簡單來說，可以把偽隨機數產生的結果看成是一個很長的序列，這個演算法通常相當複雜，讓序列看上去毫無規律，而且通常還會加上當前時間之類的變數，讓這個序列變得更加不可捉摸。不過，只要知道了演算法，就能得到這個序列。問題是當你踏上賭博機的時候，不知道當前的一局處於序列中的什麼位置。這幾個年輕人通過認真研究，發現可以通過觀察計算機發給你的牌面來反推隨機數產生的結果，通過一段時間的觀察，獲得較長的序列片段，就能夠發現這個片段在序列中的位置。而一旦確定了序列位置，就能無往而不利。

當然現在的演算法更複雜了，但歸根到底，由人來產生「隨機」這事，根本就是騙人的，感覺而已。

我覺得，應該增加一個計算機硬體，裡邊放一些骰子。用的時候搖一搖。

應該是讀取硬體溫度之類的做隨機數種子的吧？