伪随机つくえ数すう生成せいせい器き

伪随机つくえ数すう生成せいせい器き（英語えいご：pseudo random number generator，PRNG），又また被ひ称しょう为确定性せい随ずい机つくえ比ひ特とく生成せいせい器き（英語えいご：deterministic random bit generator，DRBG），是ぜ一いち个生成せいせい数字すうじ序列じょれつ的てき算法さんぽう，其特性せい近似きんじ于随ずい机つくえ数すう序列じょれつ。伪随机つくえ数すう生成せいせい器き生成せいせい的てき序列じょれつ并不是ぜ真ま随ずい机つくえ，因いん此它的てき每ごと一个数完全由一个初始值决定，这个初はつ始はじめ值被称しょう为随ずい机つくえ种子（seed种子有ゆう时使用しよう接近せっきん于真随ずい机つくえ的てき硬かた件けん随ずい机つくえ数すう生成せいせい器き生成せいせい）。尽つき管かん接近せっきん于真随ずい机つくえ的てき序列じょれつ可か以通过硬件けん随ずい机つくえ数すう生成せいせい器き生成せいせい，但ただし伪随机つくえ数すう生成せいせい器き因いん为其生成せいせい速度そくど和わ可か再さい现的优势，在ざい实践中ちゅう显得尤ゆう为重要じゅうよう。

PRNG是ぜ仿真（例れい如蒙こうむ特とく卡洛方法ほうほう）、电子游ゆう戏（例れい如过程生成せいせい）以及密みつ码学等とう应用的てき核心かくしん。加か密みつ程ほど序じょ不能ふのう从以前まえ的てき输出中ちゅう预测输出，而要采さい用よう更さら复杂的てき、不ふ具有ぐゆう简单PRNGs线性特性とくせい的てき算法さんぽう。

PRNG的てき核心かくしん是ぜ良好りょうこう的てき统计特性とくせい，通常つうじょう需要じゅよう严格的てき数学すうがく分析ぶんせき来らい证明PRNG生成せいせい的てき序列じょれつ的てき准じゅん确性足あし够接近せっきん真ま随ずい机つくえ以满足あし预期用途ようと。

周期しゅうき性せい

PRNG可か以使用しよう随ずい机つくえ种子（和わ种子状じょう态）从任意にんい初はつ始はじめ状じょう态启动，使用しよう同どう一状态进行初始化时，它将始はじめ终生成せいせい相しょう同どう的てき序列じょれつ。PRNG的てき周期しゅうき定てい义为：序列じょれつ的てき无重复前缀长度ど在ざい所有しょゆう起おこり始はじめ状じょう态中的てき最大さいだい值。周期しゅうき受状态数的てき限きり制せい，通常つうじょう用よう比ひ特とく位くらい数表示すうひょうじ。然しか而，每まい增加ぞうか一いち个比特とく位い，周期しゅうき长度就可能かのう增加ぞうか一いち倍ばい，所以ゆえん构建周期しゅうき足あし够长的てきPRNG对于许多实际应用程ほど序じょ来らい说是很容易えき的てき。

如果PRNG的てき内部ないぶ状じょう态包含ほうがん$n$位くらい，那な么它的てき周期しゅうき不ふ会かい超ちょう过$2^{n}$，甚至可能かのう非常ひじょう短たん。对于大だい多数たすうPRNG，周期しゅうき长度的てき计算并不需要じゅよう遍へん历整个周期き。线性反はん馈移位寄いき存そん器き（LFSR）的てき周期しゅうき通常つうじょう正ただし好こう是ぜ$2^{n}-1$。線せん性せい同どう餘よ方法ほうほう的てき周期しゅうき可か以通过因式しき分解ぶんかい进行计算。 尽つき管かんPRNG在ざい达到周期しゅうき之の后きさき会かい出で现重复的结果，但ただし重じゅう复序列じょれつ的てき出で现并不ふ意味いみ着ぎ到いた达了一いち个周期き，因いん为它的てき内部ないぶ状じょう态可能かのう比ひ输出要よう大だい很多。对于输出为1位い的てきPRNGs，这一点尤其明显。

确定性せい生成せいせい器き的てき潜在せんざい问题

在ざい实践中ちゅう，许多常つね见的PRNG会かい显示出で导致统计模も式しき检测测试失しつ败的情じょう况。约翰·冯诺依曼警告けいこく不要ふよう把わPRNG错误地ち解かい释为真ま随ずい机つくえ数すう生成せいせい器き，还开玩笑说：“任にん何なん使用しよう算ざん术方法ほう生成せいせい随ずい机つくえ数すう的てき人じん，都みやこ是ただし有罪ゆうざい的てき”。

• 某ぼう些种子こ状じょう态的周期しゅうき比ひ预期的てき短たん(在ざい这种情じょう况下，这种种子状じょう态可以称为“弱じゃく”)；
• 生成せいせい的てき大量たいりょう数字すうじ分布ぶんぷ不ふ均ひとし匀；
• 连续值的关联性せい；
• 输出序列じょれつ的てき维数分布ぶんぷ差さ；
• 某ぼう些值出で现的位置いち之の间的距离与随ずい机つくえ序列じょれつ分布ぶんぷ的てき距离不同ふどう。

在ざい很多领域，21世せい纪之前まえ的てき很多依よ赖于随ずい机つくえ选择、蒙こうむ特とく卡洛模も拟或者しゃ以其他た方式ほうしき依よ赖PRNG的てき研究けんきゅう工作こうさく，由ゆかり于使用しよう了りょう品ひん质较差さ的てきPRNGs，其可靠もたれ性せい比ひ可能かのう的てき结果要よう低てい得とく多た。 即そく使つかい在ざい今こん天てん，有ゆう时也需要じゅよう谨慎，如下面めん的てき来らい自じ国くに际统计科学かがく百科ひゃっか全ぜん书的てき警告けいこく所しょ示しめせ:

The list of widely used generators that should be discarded is [long] ... Check the default [PRNG] of your favorite software and be ready to replace it if needed. This last recommendation has been made over and over again over the past 40 years. Perhaps amazingly, it remains as relevant today as it was 40 years ago.

举例来らい说，考こう虑一下か广泛使用しよう的てき编程语言Java。Java仍然使用しよう線せん性せい同どう餘よ方法ほうほう (LCG)来らい实现PRNG。 然しか而其的てき品質ひんしつ很差。

第だい一个避免了主要问题而且运行速度很快的PRNG是ぜ1998年ねん发布的てきMersenne Twister。此后还开发了其他高だか品質ひんしつ的てきPRNG。

基もと于线性せい递归的てき生成せいせい器き

在ざい20世せい纪下した半はん叶かのう，PRNG的てき标准算法さんぽう由ゆかり線せん性せい同どう餘よ方法ほうほう（LCG）构成。众所周知しゅうち，LCG的てき质量不ふ优，但ただし也没有ゆう更さら好このみ的てき方法ほうほう。Press et al. (2007) 描述了りょう这种情じょう况：“如果所有しょゆう因いん为LCG而受质疑的てき科学かがく论文从书架か上じょう消失しょうしつ，那な么每一个架子上都会有一个拳头大小的空隙”。

伪随机つくえ生成せいせい器き构造的てき重大じゅうだい进展，是ぜ在ざい二元域中引入的线性递归技术，这种生成せいせい器き和わ线性反はん馈移位寄いき存そん器き有ゆう关。

1997年ねん发明的てき梅森うめもり旋转算法さんぽう，避免了りょう很多问题。梅森うめもり旋转算法さんぽう的てき周期しゅうき长达$2^{19937}-1$，被ひ证明在ざい623个维度ど上じょう是ぜ均ひとし匀分布ぶんぷ的てき（对于32位い数すう值），同どう时它的てき运行速度そくど比ひ其他统计方法ほうほう快かい。

在ざい2003年ねん，George Marsaglia提出ていしゅつ了りょうxorshift生成せいせい器き家族かぞく，它也基もと于线性せい递归。这种生成せいせい器き的てき运行速度そくど非常ひじょう快かい，再さい结合非ひ线性操作そうさ，通つう过了强きょう有力ゆうりょく的てき统计测试。

在ざい2006年ねん，WELL家族かぞく的てき生成せいせい器き被ひ提出ていしゅつ。 WELl生成せいせい器き在ざい某ぼう些方面めん提ひさげ高だか了りょう梅森うめもり旋转算法さんぽう的てき质量，梅森うめもり旋转算法さんぽう具有ぐゆう非常ひじょう大だい的てき状じょう态空间，而且从含有がんゆう大量たいりょう0值的状じょう态空间中的てき恢复非常ひじょう缓慢。

密みつ码安全的ぜんてき伪随机つくえ数すう生成せいせい器き

主しゅ条目じょうもく：密みつ码学安全あんぜん伪随机つくえ数すう生成せいせい器き

适合于加密みつ应用程ほど序じょ的てきPRNG称しょう为加か密みつ安全あんぜん的てきPRNG（CSPRNG）。CSPRNG的てき一いち个必要ひつよう条件じょうけん是ぜ不知ふち道どう初はつ始はじめ种子的てき敌人在ざい分ぶん辨べん生成せいせい器き的てき输出序列じょれつ和わ真ま随ずい机つくえ序列じょれつ时只有可ゆか忽ゆるがせ略りゃく的てき优势。换句话说，若わかPRNG只ただ需要じゅよう通どおり过特定とくてい统计测试时，则CSPRNG必须通どおり过种子こ规模的てき多た项式复杂度ど内的ないてき所有しょゆう统计测试。尽つき管かん这一性质的证明超出了计算复杂性理论目前的技术水平，大量たいりょう的てき证据如下，把わCSPRNG规约到计算困こま难的数学すうがく问题，例れい如整数すう分解ぶんかい。 通常つうじょう，在ざい一个算法被认证为CSPRNG之の前ぜん需要じゅよう多年たねん的てき检验。

CSPRNG的てき类别包括ほうかつ：

• stream ciphers
• 技わざ术模式しき或ある输出反はん馈模式しき的てき块加密みつ
• 保ほ证密码安全的ぜんてきPRNG，例れい如微软的密みつ码学应用编程接せっ口こう函数かんすうCryptGenRandom，Yarrow algorithm（集成しゅうせい进Mac OS X和わFreeBSD）以及Fortuna
• 组合PRNG把わ多た个PRNG算法さんぽう组合在ざい一起以移除可检测的非随机性
• 基もと于数学がく难题假かり设的设计，例れい如Micali–Schnorr generator、Naor-Reingold伪随机つくえ函数かんすう、Blum Blum Shub算法さんぽう，这些算法さんぽう具有ぐゆう较强的てき安全あんぜん性せい。相そう比ひ于传统方法ほう，这些算法さんぽう的てき速度そくど非常ひじょう缓慢，对于许多应用是ぜ不ふ实际的てき。

通用つうようPRNG。已やめ经证明あきら，密みつ码安全的ぜんてきPRNG可か以通过单向こう函数かんすう构造。然しか而，这些构造在ざい实际应用中ちゅう非常ひじょう缓慢，主要しゅよう用よう于理论研究けんきゅう。 有ゆう证据表示ひょうじ，NSA向むかいNIST认证的てき伪随机つくえ生成せいせい器きDual_EC_DRBG注入ちゅうにゅう了りょう非ひ对称后きさき门。

大だい多数たすう使用しようPRNG的てき密みつ码算法的ほうてき安全あんぜん性せい是ぜ基もと于下面めん的てき假かり设：PRNG和わ真ま随ずい机つくえ序列じょれつ的てき分ぶん辨べん是ぜ不可ふか行ぎょう的てき。

BSI评估标准

德とく国こく联邦信しん息いき安全あんぜん办公室しつ(德とく語ご：Bundesamt für Sicherheit in der Informationstechnik, BSI)制せい订了四条评估确定性随机生成器的标准。 如下：

• K1 - 产生的てき随ずい机つくえ数すう序列じょれつ彼此ひし不同ふどう的てき概がい率りつ应该是ぜ很高的てき
• K2 - 根ね据すえ某ぼう些统计测试，无法分ぶん辨べん产生的てき序列じょれつ和わ真ま随ずい机つくえ序列じょれつ。这些测试包括ほうかつ： monobit测试（序列じょれつ中ちゅう的てき0和わ1的てき数量すうりょう相等そうとう）、poker测试（chi-squared测试的てき特殊とくしゅ情じょう况）、runs测试（不同ふどう长度运行的てき频率）、来き自じ于BSI 和わNIST,的てきlongruns测试、autocorrelation测试。
• K3 - 给定任にん何なん子し序列じょれつ，任にん何なん攻おさむ击者都と无法计算后きさき续序列じょれつ或ある者もの生成せいせい器き的てき内部ないぶ状じょう态
• K4 - 给定生成せいせい器き的てき内部ないぶ状じょう态，任にん何なん攻おさむ击者都と无法计算之の前まえ的てき序列じょれつ或ある者もの生成せいせい器き之の前まえ的てき状じょう态

对于密みつ码学应用，只ただ有ゆう满足K3和わK4标准的てき生成せいせい器き是ぜ可か以接受せつじゅ的てき。

数学すうがく定てい义

给定

• $P$ - $\left(\mathbb {R} ,{\mathfrak {B}}\right)$上うえ的てき概がい率りつ分布ぶんぷ，其中${\mathfrak {B}}$是ぜ实数集しゅう上じょう的てきBorel set
• ${\mathfrak {F}}$ - 非ひ空そら子こ集しゅう${\mathfrak {F}}\subseteq {\mathfrak {B}}$，例れい如 ${\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$
• $A\subseteq \mathbb {R}$ - 非ひ空そら集合しゅうごう

称たたえ一いち个函数すう$f:\mathbb {N} _{1}\rightarrow \mathbb {R}$（$\mathbb {N} _{1}=\left\{1,2,3,\dots \right\}$是正ぜせい整数せいすう的てき一いち个子集しゅう）为一个伪随机生成器，当とう且仅当とう：

• $f\left(\mathbb {N} _{1}\right)\subseteq A$
• $\forall E\in {\mathfrak {F}}\quad \forall 0<\varepsilon \in \mathbb {R} \quad \exists N\in \mathbb {N} _{1}\quad \forall N\leq n\in \mathbb {N} _{1},\quad \left|{\frac {\#\left\{i\in \left\{1,2,\dots ,n\right\}:f(i)\in E\right\}}{n}}-P(E)\right|<\varepsilon$

相關そうかん條目じょうもく

• 随ずい机つくえ数すう生成せいせい
• 随ずい机つくえ性せい
• 偽にせ亂數らんすう二に進しん位い數列すうれつ
• 硬かた件けん随ずい机つくえ数すう生成せいせい器き
• Random.org

參考さんこう書目しょもく

• Barker E., Kelsey J., Recommendation for Random Number Generation Using Deterministic Random Bit Generators （页面存そん档备份，存そん于互联网档案あん馆）, NIST SP800-90A, January 2012
• Brent R.P., "Some long-period random number generators using shifts and xors", ANZIAM Journal, 2007; 48:C188–C202
• Gentle J.E. (2003), Random Number Generation and Monte Carlo Methods, Springer.
• Hörmann W., Leydold J., Derflinger G. (2004, 2011), Automatic Nonuniform Random Variate Generation, Springer-Verlag.
• Knuth D.E.. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Chapter 3. [Extensive coverage of statistical tests for non-randomness.]
• Luby M., Pseudorandomness and Cryptographic Applications, Princeton Univ Press, 1996. ISBN 9780691025469
• von Neumann J., "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U.S. Government Printing Office, 1951): 36-38.
• Peterson, Ivars. The Jungles of Randomness : a mathematical safari. New York: John Wiley & Sons. 1997. ISBN 0-471-16449-6. 
• Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2007), Numerical Recipes (Cambridge University Press).
• Viega J., "Practical Random Number Generation in Software （页面存そん档备份，存そん于互联网档案あん馆）", in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.

外部がいぶ連結れんけつ

• TestU01 （页面存そん档备份，存そん于互联网档案あん馆）: A free, state-of-the-art (GPL) C++ Random Number Test Suite.
• DieHarder （页面存そん档备份，存そん于互联网档案あん馆）: A free (GPL) C Random Number Test Suite.
• "Generating random numbers （页面存そん档备份，存そん于互联网档案あん馆）" (in embedded systems) by Eric Uner (2004)
• "Analysis of the Linux Random Number Generator （页面存そん档备份，存そん于互联网档案あん馆）" by Zvi Gutterman, Benny Pinkas, and Tzachy Reinman (2006)
• "Better pseudorandom generators （页面存そん档备份，存そん于互联网档案あん馆）" by Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan (Microsoft Research, 2012)