茶年 · 中文维基百科

線性同餘方法

Wikipedia · 2025-12-14 维基百科 👁 1 阅读

線性同餘方法（LCG）是個產生偽隨機數的方法。

它是根據以下的遞迴關係式：
: N_{j+1} \equiv (A \times N_j + B ) \pmod{M}

其中A,B,M是產生器設定的常數。

LCG的週期最大為M，但大部分情況都會少於M。要令LCG達到最大週期，應符合以下條件：

B,M互質；

M的所有質因數都能整除A-1；

若M是4的倍數，A-1也是；

A,B,N_0都比M小；

A,B是正整數。

随机性
因为通过线性同余方法构建的伪随机数生成器的内部状态可以轻易地由其输出演算得知，所以此种伪随机数生成器属于统计学伪随机数生成器。

设计密码学的应用必须至少使用密码学安全伪随机数生成器，故需要避免由线性同余方法获得的随机数在密码学中的应用。

參見
*Mersenne Twister

參考文獻
*

  • D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Section 3.2.1: The Linear Congruential Method, pp. 10–26.

*
*
Gentle, James E., (2003). Random Number Generation and Monte Carlo Methods*, 2nd edition, Springer, ISBN 0-387-00178-6.

  • (in this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators).

外部連結

#同余 #伪随机数生成器

评论 (0)

  • 还没有评论，来抢沙发吧。