今天我們來和大家聊聊隨機數。
大家如果學過編程對于隨機數應該都不陌生，應該或多或少都用到過。再不濟我們每周的抽獎都是用隨機數抽出來的，我們用隨機數的時候，往往都會加一個前綴，說它是偽隨機數，那么這個偽隨機數的偽字該怎么解釋，什么又是真隨機數呢？
真偽隨機數
目前學界劃分真偽隨機數的方式非常簡單，一句話就能說明白，凡是用一定的算法使用程序生成的都是偽隨機數，通過物理現象產生的隨機數才是真隨機數。也就是說計算學家們已經證明了僅僅依靠算法是無法生成真隨機數的，也可以認為這是一個NP問題。
算法生成的都是偽隨機數的證明太過復雜我們可以不去深究，但是什么又叫做物理現象產生的隨機數呢？其實也很簡單，舉個很簡單的例子就是拋硬幣和擲骰子。當然物理現象不止這些，比如還有電子元件的噪音、元素的衰變等等。
真假隨機數之間的最大差別在哪里？其實就在是否可以預測上。計算機算法得出的各種隨機數之所以是偽隨機數是因為它們的結果都是可以預測的，只要我們知道算法和起始狀態以及各種參數，就可以預測下一次隨機出來的結果。而真隨機數則無法預測，就是純粹隨機的。
但問題來了，拋硬幣和擲骰子這些物理現象又是真的隨機嗎？如果我們知道了硬幣的起始狀態以及拋擲的角度和力度，是不是可以預測硬幣拋擲的結果呢？進一步我們是否可以假設，如果我們能知道所有例子的所有狀態，是否所有所謂的隨機數都是可以預測的呢？但根據量子力學的測不準原理，我們知道我們無法同時知道粒子的位置和動量，不僅說明了我們無法預測，也說明了我們無法假設預測。
所以某種程度上來說物理現象是不是就是真隨機，這就成了一個哲學問題。但至少在計算機領域當中，這個問題是明確的，算法得出的都是偽隨機數，只有通過物理現象得出的才是真隨機數。
在計算機系統當中，偽隨機數都是有周期的，只要我們持續的次數足夠多，就可以看到這種周期。而真隨機數則不存在這種周期，有一位前輩做過一個隨機數可視化實驗，也就是把隨機數得到的結果做成圖片。我們可以直觀地對比一下，這是真隨機數可視化之后的圖片：
看起來像不像是以前的電視收不到信號的時候顯示的內容？我們再來看看通過算法生成的偽隨機數可視化之后的結果：
對比一下還是挺明顯的，明顯可以看出來偽隨機數是有規律的，這個規律體現出來就是圖像當中的紋理。如果大家想要獲取真隨機數，可以訪問random.org這個網站，它是免費的，我們可以人為設置上下限來獲取指定范圍內的隨機數。
對比過真偽隨機數之后，我們再來看看現在計算機系統當中常用的偽隨機數生成算法的原理。
平方取中法
我們首先介紹的是平方取中法，這個方法非常簡單粗暴，是用來產生四位隨機數的。
具體的邏輯是怎樣的呢？首先我們需要一個隨機種子，比如2333，我們把這個隨機種子進行平方，得到5442889。這個數一共有6位，我們給它左邊填充一個0變成05442889，最后取出它的中間四位是4428，這就是我們隨機得到的結果。當我們下次再計算隨機數的時候，隨機數的種子就成了4428。
這個算法的作者是大名鼎鼎的計算機之父馮諾依曼，自從他確定了計算機體系結構之后一直沿用至今。他當時推崇這一算法的原因很簡單，計算方便，速度快，也容易排查錯誤。它認為如果真的設計一個復雜的算法來生成看起來比較好的隨機數，可能隱藏的bug比解決的問題還要多。
seed = 2333
def random():
global seed
seed = seed ** 2
return int(str(seed)[1:5])
我寫了代碼實際運行了一下，結果看起來其實沒有那么不靠譜。
LCG算法
馮諾依曼的隨機數算法雖然看起來簡單，但是非常草率，在很多場合下是顯然不能使用的。所以人們又想出了新的算法，這個算法也很簡單，看起來英文縮寫高大上，其實翻譯過來是線性同余法。也就是利用ax + b mod c來生成隨機數。
最后返回的結果是上述式子計算之后的結果，abc三個數都是我們選定的參數。當下一次隨機的時候，就將上次的結果作為新的種子進行計算。我們寫出它的遞推公式就是：
這個算法一眼就看明白了，它的核心完全在于abc這三個參數的選擇。如果選的不好就不能實現隨機數的效果，這里我給大家分享一個業內常用的選擇，a=25214903917，b=11，c=2^48。這些數不是拍腦袋隨便選的，而是計算學家們算出來的。實際上JAVA JDK當中Random的類采用的就是這樣的算法。
seed = 2
def lcg():
global seed
seed = (25214903917 * seed) & ((1 << 48) - 1)
return seed
這種算法實現方式也非常簡單，并且得到的效果也不錯。如果要增加隨機性，我們還可以在輸出結果上做一些優化，比如進行位移或者是調換二進制位的順序等等。但是這種算法也有缺點，就是它的計算方式是固定的，只是隨機種子未知。只要愿意，我們是可以通過得到的隨機結果去反推這些參數的。
這并不是一個復雜的算法，因此LCG算法得到的隨機數不能應用在一些高安全級別的應用上，否則可能會有安全隱患。
梅森旋轉算法
LCG算法實現的偽隨機數效果還不錯，但是周期不夠長，很容易被黑客推算出隨機種子。后來兩個日本學者又研究提出了新的偽隨機數算法，在這個算法當中用到了梅森素數，所以稱為梅森旋轉算法。
簡單介紹一下梅森素數，梅森素數的意思是形如2^n - 1 的素數。利用梅森素數的性質可以設計出周期長度為梅森素數長度的隨機數周期。比如目前Python、C++11等語言當中用的隨機數計算包都是用的這種算法。目前常用的版本周期是2^19937 - 1，這是一個巨大的天文數字。
梅森旋轉算法的實現原理非常復雜，網上的資料也不多，我看過一些都不是非常好懂。這里就不介紹了，大家感興趣可以去了解看看。但我個人覺得意義不大，因為實在是用不到，面試也完全不會考。
雖然梅森旋轉算法的周期非常非常長，但是仍不是安全的隨機數算法，仍然有可能會被黑客破解。只不過和LCG算法相比，被破解的概率以及難度增加了許多。
大家可能很好奇，什么樣的算法才是安全的呢？其實業內的安全算法其實挺取巧的，一般的常用方法就是利用一個數學界的難題來設計一個算法。比如RSA加密算法，利用的就是大整數因式分解的問題。這樣的問題業內除了暴力計算沒有好方法，而暴力計算的復雜度非常非常高，根本不可能在有限時間內有解，自然這個就是一個安全的算法了。如果某位黑客有能力設計出破解的算法來，他根本也不用破解啥，只要把解法發表成論文，自然可以名利雙收。
你看隨機數這么一個常見的功能下面居然隱藏了這么深的科學原理，而且更加震驚的是以我們人類如此厲害的文明，居然連隨機一個數都做不到。不知道大家看到這里又有何種感受呢？
今天的文章就到這里，衷心祝愿大家每天都有所收獲。如果還喜歡今天的內容的話，請來一個三連支持吧~（點贊、關注、轉發）
本文始發于公眾號：TechFlow，求個關注
