線性同餘方法

此條目已列出參考文獻，但因為沒有文內引註而使來源仍然不明。 (2014年9月16日) 请加上合适的文內引註来改善这篇条目。

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

它是根據以下的遞迴關係式：

${\displaystyle N_{j+1}\equiv (A\times N_{j}+B){\pmod {M}}}$

其中${\displaystyle A,B,M}$是產生器設定的常數。

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

1. ${\displaystyle B,M}$互質；
2. ${\displaystyle M}$的所有質因數都能整除${\displaystyle A-1}$；
3. 若${\displaystyle M}$是4的倍數，${\displaystyle A-1}$也是；
4. ${\displaystyle A,B,N_{0}}$都比${\displaystyle M}$小；
5. ${\displaystyle A,B}$是正整數。

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

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

• Mersenne Twister

• The simulation Linear Congruential Generator （页面存档备份，存于互联网档案馆） visualizes the correlations between the pseudo-random numbers when manipulating the parameters.
• Security of Random Number Generation: An Annotated Bibliography
• Linear Congruential Generators post to sci.math
• The "Death of Art" computer art project at Goldstein Technologies LLC, uses an LCG to generate 33,554,432 images （页面存档备份，存于互联网档案馆）
• P. L'Ecuyer and R. Simard, ``TestU01: A C Library for Empirical Testing of Random Number Generators, May 2006, Revised November 2006, ACM Transactions on Mathematical Software, 33, 4, Article 22, August 2007. （页面存档备份，存于互联网档案馆）
• Additive Congruential Method : maths and logic behind its spread