線性同餘方法

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

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

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

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

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

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

隨機性

因為通過線性同餘方法構建的偽隨機數生成器的內部狀態可以輕易地由其輸出演算得知，所以此種偽隨機數生成器屬於統計學偽隨機數生成器。

設計密碼學的應用必須至少使用密碼學安全偽隨機數生成器，故需要避免由線性同餘方法獲得的隨機數在密碼學中的應用。

參見

• Mersenne Twister

參考文獻

• S.K. Park and K.W. Miller. Random Number Generators: Good Ones Are Hard To Find. Communications of the ACM. 1988, 31 (10): 1192–1201. doi:10.1145/63039.63042. 
• 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.
• P. L'Ecuyer. Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure. Mathematics of Computation. 1999, 68 (225): 249–260 [2012-12-30]. doi:10.1090/S0025-5718-99-00996-5. （原始內容存檔於2005-05-16）. 
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP, Section 7.1.1. Some History, Numerical Recipes: The Art of Scientific Computing 3rd, New York: Cambridge University Press, 2007 [2012-12-30], ISBN 978-0-521-88068-8, （原始內容存檔於2011-08-11） 
• Gentle, James E., (2003). Random Number Generation and Monte Carlo Methods, 2nd edition, Springer, ISBN 0-387-00178-6.
• Joan Boyar. Inferring sequences produced by pseudo-random number generators. Journal of the ACM. 1989, 36 (1): 129–141. doi:10.1145/58562.59305.  (in this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators).

外部連結

• 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