偽隨機性(英語:Pseudorandomness)是一個過程似乎是隨機的,但實際上並不是。例如偽隨機數是使用一個確定性的算法計算出來的似乎是隨機的數序,因此偽隨機數實際上並不隨機。在計算偽隨機數時假如使用的開始值不變的話,那麼偽隨機數的數序也不變。偽隨機數的隨機性可以用它的統計特性來衡量,其主要特徵是每個數出現的可能性和它出現時與數序中其它數的關係。偽隨機數的優點是它的計算比較簡單,而且只使用少數數值很難推算出計算它的算法。一般人們使用一個假的隨機數,比如電腦上的時間作為計算偽隨機數的開始值。
![]() | 此條目需要精通或熟悉相關主題的編者參與及協助編輯。 (2013年5月27日) |
計算機偽隨機數函數
用來計算偽隨機數的函數被稱為隨機函數,使用隨機函數產生隨機數的演算法稱為隨機數生成器。一些隨機函數是周期性的,雖然一般來說使用非周期性的函數要好得多,但周期性的隨機函數往往快得多。有些周期函數的係數可以調整,之後它們的周期非常大,基本上與非周期的函數效果一樣。
/* 使用 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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.