novus log

很難得決定寫一篇比較普及性的文章，這是我去年 在PanSci 回答的一個問題 ，當初想到什麼就寫什麼，所以比較沒有系統，後來決定重新整理之後放上來。

原本的問題是：

在現實生活中要隨機,我們可以擲骰子

因為我們不能準確控制所有影響擲骰結果的因素

但是在電腦程式中,怎麼可能做到同一條算式運行多次但結果卻不同呢?

以及:那是真正的隨機(像量子的隨機) 還是類似骰子的隨機?謝謝!

相信很多剛接觸電腦亂數的人都會有相同的疑問。我想以比較淺白的方式說明背後的基本概念，盡量避開會讓一般人倒胃口的技術細節。另一方面，很多技術細節恐怕也超出我的能力範圍。

首先要知道，現代的計算機大都採用決定性的計算模型，相同的資料搭配相同的計算過程，必定會得到一模一樣的結果。若希望每次計算都得到不同的結果，最顯而易見的方法是每一次做完計算就改變程式的資料，於是下一次計算結果就會不同。但只用純數學方法時，並沒有新的資訊進來，要拿什麼東西去更新資料呢？其實也沒什麼好方法，只能拿每次新產生出來的數值作為下一次計算的依據，這就是為什麼計算機偽隨機數大都會表示成遞迴定義的數列。

說到遞迴定義的數列，很多人會想到費氏數列：

1, 1, 2, 3, 5, 8, 13, 21, ...

這個數列可由這個遞迴式產生： F[n] = F[n-1] + F[n-2]，顯然很有規律。在數學上這個數列會無窮無盡的遞增下去，那如果我們強迫數值超出某個範圍之後折回來會怎麼樣呢？假設每個整數最大只能到 100，上面的數列可改寫成：

F[n] = (F[n-1] + F[n-2]) mod 100

列舉前面幾項得到：

1, 1, 2, 3, 5, 8, 13, 21, 34, 55,
89, 44, 33, 77, 10, 87, 97, 84, 81, 65,
46, 11, 57, 68, 25, 93, 18, 11, 29, 40,
...

一開始仍然看得到規則，不過整體趨勢已經不再是單調遞增，當數值折回之後規律變得不太明顯。再加一點點變化就會變得相當有趣，舉例來說：

• 用加法以外的運算如何？例如令數值範圍動不動就溢位折回。
• 一定要用前兩項做運算嗎？用不相鄰的 n-i、n-j 項如何？用三項如何？加入額外的常數項呢？

這就是一類常用的偽隨機數產生器家族，稱為「延遲費氏數列（Lagged Fibonacci）」。用實際的例子來看，令前五項為 18, 83, 4, 42, 71，然後搭配以下算式：

F[n] = (F[n-2] + F[n-5]) mod 100

得到的數列為：

18, 83, 4, 42, 71, 60, 54, 64, 96, 35,
56, 89, 20, 85, 55, 41, 44, 61, 29, 16,
70, 60, 31, 89, 47, 59, 7, 90, 96, 37,
...

對人類來說，這個數列的規則已經非常不容易看穿，但是許多現實應用還會需要良好的分佈特性。雖然我沒有實際檢驗上面的數列，不過我猜像這樣隨便設計的數列在分佈特性方面大概不及格吧。若希望獲得可接受的統計特性，算式中的各項參數都必須藉由數學原理設計或者透過實驗小心選擇。

以上舉延遲費氏數列主要是因為我想大多數讀者對於費氏數列比較熟悉，在現實中，基於「線性同餘法（Linear congruential generator）」的偽隨機數產生器可能比延遲費氏數列更為常見。線性同餘法的計算方法如下：

x[n] = (a * x[n-1] + c) mod m

雖然計算方法大不相同，共同點在於內部都會維護由先前生成數值所構成的資訊，用以計算未來的數字。

更進階的演算法不只運用少許資訊，而是會維護一個相對大很多的位元池，使用比較複雜的方法從位元池組合出新數值，也會將新算出來的數攪拌到位元池中。近年來廣受歡迎的 Mersenne twister 使用的位元池可以高達上萬 bits。對了，C++11 已經將包含 Mersenne twister 在內的多種亂數引擎納入標準。

良好的分佈特性只是隨機數的其中一部份條件，對於一般遊戲趣味、統計模擬等應用已經足夠，至於資安領域對偽隨機數的不可預測性有更嚴格的要求。以上介紹的純數學方法理論上都是有可能預測的，例如我之前曾經介紹過一個 預測線性同餘數列的方法 ，示範如何從已經出現的數字回推相關參數。

本文開頭也提過，在採用決定性演算法的現代計算機上，相同的資料搭配相同的計算過程，必定會得到一模一樣的結果。因為演算法多是公開的，只要得知內部狀態就等於完全掌握整個序列。

在前面提到的方法中，每生成一個的數字所運用到的資訊都是來自先前生成過的數字，不管亂數產生器使用的位元池有多大，資訊量畢竟都是有限的。假如一個亂數引擎運用的資訊量只有 16 bits，根據鴿籠原理，只要取值超過 65536 次，程式至少會回到重複的狀態一次。而且這只是資訊量的上限，演算法本身不一定能達到這個週期。

就如同小說中東方不敗的劍法，不管劍招再如何變幻莫測，只要時間一久招式必定重複，難保不會被某個高手給破解。

為了滿足更嚴格的需求，現代的作業系統會定期蒐集硬體訊號攪拌入系統內建的位元池當中，供給應用程式作為產生亂數的依據。一些可能被使用的資訊像是：兩次鍵盤觸發的時間間隔、滑鼠移動距離、中斷觸發的時間間隔、甚至是各種硬體雜訊。這些資訊非常難以全盤掌握而且持續在更新，所以遠比純粹數學的方法安全，但也不是完全不可能破解。如果一個系統接受外部資訊的管道很少，理論上有可能被有心人士摸清內部狀態，甚至這些管道也有機會被操弄。

Linux 和 FreeBSD 提供了 /dev/random 和 /dev/urandom 這兩個虛擬檔案，實作了上述的硬體亂數的功能。微軟的 CryptoAPI 也使用了相關的方法。

所以，基於數學計算的偽隨機數本質上只是一個固定的數列而已，比骰子還糟。而使用外部資訊的偽隨機數則比較像骰子，儘管我們都知道其中運作的原理，但是由於無法掌握生成亂數的所有資訊，因此難以預測。