偽隨機性
此條目需要精通或熟悉相關主題的編者參與及協助編輯。 (2013年5月27日) |
偽隨機性(英語:Pseudorandomness)是一個過程似乎是隨機的,但實際上並不是。例如偽亂數是使用一個確定性的演算法計算出來的似乎是隨機的數序,因此偽亂數實際上並不隨機。在計算偽亂數時假如使用的開始值不變的話,那麼偽亂數的數序也不變。偽亂數的隨機性可以用它的統計特性來衡量,其主要特徵是每個數出現的可能性和它出現時與數序中其它數的關係。偽亂數的優點是它的計算比較簡單,而且只使用少數數值很難推算出計算它的演算法。一般人們使用一個假的亂數,比如電腦上的時間作為計算偽亂數的開始值。
電腦偽亂數函式
編輯用來計算偽亂數的函式被稱為隨機函式,使用隨機函式產生隨機數的演算法稱為亂數生成器。一些隨機函式是周期性的,雖然一般來說使用非周期性的函式要好得多,但周期性的隨機函式往往快得多。有些周期函式的係數可以調整,之後它們的周期非常大,基本上與非周期的函式效果一樣。
/* 使用 ANSI C 可移植算法 */
static 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;
}
可見,偽亂數是由一套產生亂數的演算法實現的。
使用
編輯在電腦類比中偽亂數用來類比產生隨機的過程,背景雜訊產生器中也可應用偽亂數。由於偽亂數不是真的亂數,在有些方面它們不能被使用,例如在密碼學中使用偽亂數要小心,因為其可計算性是一個可以攻擊的地方。統計學、蒙特·卡羅方法上使用的偽隨機數也必須挑選週期極長、隨機性夠高的隨機函式,以確保計算結果有足夠的隨機性。
偽亂數的一個特別大的優點是它們的計算不需要外部的特殊硬體的支援,因此在電腦科學中偽亂數依然被使用。真正的亂數必須使用專門的裝置,比如熱噪訊號、量子力學的效應、放射性元素的衰退輻射,或使用無法預測的現象,譬如使用者按鍵盤的位置與速度、使用者運動滑鼠的路徑坐標等來產生。對於移動式計算,採用加速度感測器協助亂數生成亦是一種普遍做法。
參見
編輯延伸閱讀
編輯- Donald E. Knuth (1997) The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition). Addison-Wesley Professional, ISBN 0-201-89684-2
- Oded Goldreich. (2008) Computational Complexity: a conceptual perspective (頁面存檔備份,存於網際網路檔案館). Cambridge University Press. ISBN 978-0-521-88473-0.(Limited preview at Google Books)
- Salil P. Vadhan. Pseudorandomness. Foundations and Trends® in Theoretical Computer Science: 1–336. [2018-04-02]. doi:10.1561/0400000010. (原始內容存檔於2018-12-13).
外部連結
編輯- HotBits: Genuine random numbers, generated by radioactive decay (頁面存檔備份,存於網際網路檔案館)
- Using and Creating Cryptographic-Quality Random Numbers
- In RFC 1750, the use of pseudorandom number sequences in cryptography is discussed at length.