電腦取隨機數是什麼原理,是真正的隨機數嗎?


首先,「真隨機」也有不同的含義,若想要「真正的真隨機」目測只能靠量子力學了。一般的所謂真隨機不是指這個,而是指統計意義上的隨機,也就是具備不確定性,可以被安全的用於金融等領域,下面說的也是這種。

答案是,計算機系統可以產生統計意義上的真隨機數。

大部分程序和語言中的隨機數(比如 C 中的,MATLAB 中的),確實都只是偽隨機。是由可確定的函數(常用線性同餘),通過一個種子(常用時鐘),產生的偽隨機數。這意味著:如果知道了種子,或者已經產生的隨機數,都可能獲得接下來隨機數序列的信息(可預測性)。

直觀來想,計算機是一種可確定,可預測的的設備,想通過一行一行的確定的代碼自身產生真隨機,顯然不可能。但是,我們或許可以迂迴一下……

實現方法簡單說就是軟硬結合,或者說,引入系統外的變數(把軟體,代碼,演算法想像成一個封閉的系統)。

一個典型的例子就是 UNIX 內核中的隨機數發生器(/dev/random),它在理論上能產生真隨機。即這個隨機數的生成,獨立於生成函數,這時我們說這個產生器是非確定的。

具體來講,UNIX 維護了一個熵池,不斷收集非確定性的設備事件,即機器運行環境中產生的硬體噪音來作為種子。

比如說:時鐘,IO 請求的響應時間,特定硬體中斷的時間間隔,鍵盤敲擊速度,滑鼠位置變化,甚至周圍的電磁波等等……直觀地說,你每按一次鍵盤,動一下滑鼠,鄰居家 wifi 信號強度變化,磁碟寫入速度,等等信號,都可能被用來生成隨機數。

更具體的,內核提供了向熵池填充數據的介面:

比如滑鼠的就是

void add_mouse_randomness(__u32 mouse_data)

內核子系統和驅動調用這個函數,把滑鼠的位置和中斷間隔時間作為噪音源填充進熵池。

所以,結論是,程序和演算法本身不能產生真隨機,但是計算機系統作為整體可以迂迴產生統計意義上的真隨機。

參考:

  • 內核源碼在/drivers/char/random.c
  • Windows 中也有相對的隨機數生成器,基本的思想是一致的
  • 如果要求更高的話,也有專用的設備,可收集附近的電磁場等環境噪音來產生隨機數

題目:電腦取隨機數是什麼原理,是真正的隨機數嗎?首先聲明,這種問題維基解釋的更好。
答案,不會扣源碼自己出來看看嗎?下面是VC++一直用的隨機函數,就一行。你覺得他是真隨機還是偽隨機?

int __cdecl rand (
void
)
{
_ptiddata ptd = _getptd();

return( ((ptd-&>_holdrand = ptd-&>_holdrand * 214013L
+ 2531011L) &>&> 16) 0x7fff );
}

這當然是偽隨機。其實偽隨機演算法就那麼幾類,
1.線性同餘,
2.平方取中,
3.其他

目前看到的大部分庫的默認實現都是線性同餘,怎麼解釋?看上面的例子就知道了。至於線性同餘的弱點?既然是同餘那麼就別一個周期後,你產生的隨機數又會重複出現了。這有什麼影響嗎?如果就是做個測試好玩,沒啥影響,如果你是根據數字生產卡號,密碼,影響就大了。(真事,當年一些電話卡被破解就是這樣來的),這個就涉及偽隨機的演算法循環長度。什麼叫循環長度?就是如果第一次產生數字55,第二個產生數字107,那麼循環多少次後,會繼續產生,55,107……這樣的序列。
大部分簡單演算法的循環長度都是2^32左右。

那麼有沒有更好的演算法。更好的循環長度讓人無法破解呢。有。就是其他。其實數學界的人才很多的。推薦一個MT隨機數演算法。(Mersenne Twister),日本人發明的。 Mersenne Twister梅森旋轉演算法,這真不是在大家都反日的時候給大家添亂,這個演算法的確是日本人發明的。而且還是目前可以看到最好隨機數演算法,歡迎愛國青年滅了他(找出比他更好的演算法)Makoto Matsumoto(松本真) 和Takuji Nishimura(西村拓士)在1997年開發的,基於有限二進位欄位上的矩陣線性遞歸field F_{2}。 可以快速產生高質量的偽隨機數, 修正了古典隨機數發生演算法的很多缺陷。
這貨的循環長度能到多少?一個常用的實現是產生32位數字,循環長度 2^19937。一般來說只要你不搞天文運算。都可以輕鬆應對了。當然這還不算什麼,人家還快。這個演算法的普通實現不必函數庫的rand慢多少,大約只慢10%,而且這2個人了還搞了一個SSE的庫(不好移植沒用過),據說超快。
這已經是偽隨機的最高峰(之一)了。

什麼,你還不滿意?那軟體陣營已經無法幫助你了。找硬體把。


如果我只告訴你一串數字,不說怎能來的,有辦法區分真隨機還是偽隨機嗎?答案是沒有,你能做的就是進行隨機性測試,但偽隨機數也能通過這種測試,所以真偽隨機數是外延等價的東西。換句話就是,對於我們來說,或者對於產生它的系統之外的世界來說,兩者完全一樣。一不小心又奧卡姆剃刀了啊。


電腦產生的是偽隨機數。偽隨機數的產生方法很多,一般用線性同餘迭代,即 Rand_Number = (Rand_Seed * X + Y) mod Z 那個RandSeed就是「種子」一般取時鐘周期,也就是GetTickCount()。


我開個腦洞啊

電腦物理方法取得隨機數

1、利用匯流排統計,比如數據匯流排上每個時刻傳輸的數據量的平方除100等等

2、利用高精度時鐘的抖動,比如取高精度時鐘的最後幾位小數,那個會抖動

3、探測網卡上的數據流,可以是流量,也可以比如偶數的個數等等。

4、CPU溫度探測器的抖動,最後幾位小數會抖動

5、磁碟轉速探測抖動

6、磁碟溫度抖動

7、顯卡緩存的統計值

我很奇怪各位沒想到過這些方法?我上初中的時候就想到過利用匯流排數據的統計量作為隨機數來源了。


目前隨機數的生成都是偽隨機的,偽隨機就是在相同條件下,能重複生成的
密碼學的一個理論基礎是隨機數,但是實際應用上都是psudorandom,於是大量的工作都在論證生成的psudorandom和random的關係,以及對安全性的影響
目前hash value被認為是一個相對隨機串


如果不考慮浮點精度,偽隨機數和真隨機的統計規律完全一致,也就是人類無法通過不斷嘗試並統計來判斷隨機數產生器是偽隨機還是真隨機,當贗品和真品各方面表現都一致的時候,實用角度就不需要真品了。糾結產生方式沒有意義的。
但是偽隨機畢竟是數學運算模擬的,它存在精度問題,現在一般都採用64位精度的數字,雖然演算法是完美的,但精度問題會導致在低概率下隨機數曲線偏離正態分布,以至於需要更高精度諸如128,256位的計算。
但這至少需要計算億分之一的概率,感受出這個隨機的不準需要百億級別的樣本。通常情況下偽隨機都是準確的。你覺得隨機有問題,一定是你有問題而不是隨機有問題。
此外,對隨機數錯誤的操作確實會導致不準,比如多個隨機數發生器複合使用,錯誤的重置隨機種子,胡亂拋棄隨機結果。但靠譜的程序是不會犯這種錯的,還是不要考慮這種情況好了


電腦隨機數都是偽隨機數。有很多隨機數的生成演算法。不過幾年前新加坡南洋理工大的電子電器系設計了一款晶元,可以搜集周圍電磁場的噪音進而生成號稱真正的隨機數,不過沒有見到任何實際應用。


電腦只能儲存有限精度的數字,它產生的隨機數自然是偽隨機數了。

我們一般認為的真隨機數——比如用量子力學、借用蓋格米勒計數器計得的隨機數,生成速度都非常慢,且它們的具體分布我們是不清楚的,所以不常用。更糟糕的是, 就算我們有足夠時間和精力,把這些真隨機數記錄下來並加以運用,也會面臨"梅林的鬍子!隔壁的哈利和我用的數據一模一樣啊!」的尷尬局面,無法「耗盡」概率空間。
而電腦生成的偽隨機數就不一樣了,它可以高效地生(偽)產(造)隨機數,而且可以被再利用。

生產偽隨機數的原理是非常非常簡單的:
第一步:假設我們手頭已經有一串數字,我們稱它們為種子。對這些種子用遞歸法,「隨機地(其實並不是)」生成一連串0到某個自然數N之間的自然數
第二步:把這些隨機生成的自然數轉換成0到1直接的實數 (比如通過除以N來得到)。如果這樣生成的偽隨機數能夠通過許多不同的統計檢驗,達到了「以假亂真」的程度,我們就厚臉皮地認為自家程序已經聰明地會生成[0,1]上均勻分布的獨立樣本啦!
第三步:利用這串「從零到一均勻分布的隨機數」,把它們用某些演算法來轉換成其他分布的隨機數

反正大體上就是遵循上面這三步,下面具體列舉一下每一步里的比較常見的方法。
其中第一步里,比較著名的有:
線性同餘法(比如RANDU) (但是如果是multiplicativ的話,在n維空間里的點都在有限個超平面里,這些偽隨機數的獨立性不佳)
梅森旋轉法(循環周期長,速度快)
平方取中法(速度快,但是很容易生成循環周期短的數列,還有很多不動點)
Lagged Fibonacci generator(獨立性不好)

檢驗這些偽隨機數的方法就更多了,比如卡方Goodness-of-fit檢驗,QQ圖, Wald-Wolfowitz遊程檢驗,Diehard tests,NIST tests suite 和 TestU01 等等等等。

第三步裡面,利用均勻分布來生成其他分布的方法也有很多。
常見的有:
逆函數法Inverse transform sampling(為了提高速度,會用數值方法取逆函數,這樣做的缺點是會產生誤差)
Von Neumann舍選法Rejection samplin(提高其效率的關鍵是講其中的常數C取得越小越好)
Box Muller演算法(Box 生成正太分布)
Marsaglia polar method (對Box Muller演算法的改進,不需要用到sin和cos函數)
Marsaglia-Bray method(生成正態分布,97%的情況下無需用到複雜函數)
以及 Ziggurat algorithm (其中用到了 Marsaglia polar method 和舍選法,優化計算過程中用到其他函數和隨機數的次數)。


use noise.


偽隨機數,真正的隨機數是物理現象產生的,如拋硬幣,量子力學效應等,計算機產生隨機的方法主要有線性同餘方法,平方取中法,
M-sequence,
梅森旋轉演算法,
線性同餘方法。產生的都是為隨機數。


不是真正的隨機數,偽隨機數是也,拿matlab來說,其隨機數生成都是由種子遞推出來的,相同的種子,遞推出相同的隨機數。matlab剛運行起來時種子都為初始值,因此每一次第一次執行rand得到的隨機數相同;除了種子遞推還有取當前時鐘來產生隨機數的,這些都是偽隨機數,看過一個網站通過取當前大氣雜訊再怎麼處理一下得到隨機數,這個比較隨機···


計算機的隨機是為了避免確定性。只要達到這個目的就可以了。偽不偽是看破解強度標準咯。 從人類現有知識來看,真隨機也許只能從量子物理層次去產生了。


[Numberphile] 關於隨機數 看看這個


偽隨機數的一個特別大的優點是它們的計算不需要外部的特殊硬體的支持,因此在計算機科學中偽隨機數依然被使用。真正的隨機數必須使用專門的設備,比如熱噪訊號、量子力學的效應、放射性元素的衰退輻射,或使用無法預測的現象,譬如用戶按鍵盤的位置與速度、用戶運動滑鼠的路徑坐標等來產生。——————wiki 偽隨機性


圓周率小數部位數字出現的頻率是否是真隨機數呢?這個應該是天然的


推薦閱讀:

你碰到過的最難調試的 Bug 是什麼樣的?

TAG:演算法 | 編程 | 計算機 | 隨機數 |