查看“︁線性同餘方法”︁的源代码

{{no footnotes|time=2014-09-16T20:37:20+00:00}}
'''線性同餘方法'''（LCG）是個產生[[偽隨機數]]的方法。

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

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

LCG的週期最大為<math>M</math>，但大部分情況都會少於M。要令LCG達到最大週期，應符合以下條件：
# <math>B,M</math>[[互質]]；
# <math>M</math>的所有質因數都能整除<math>A-1</math>；
# 若<math>M</math>是4的[[倍數]]，<math>A-1</math>也是；
# <math>A,B,N_0</math>都比<math>M</math>小；
# <math>A,B</math>是正整數。

== 随机性 ==

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

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

==參見==
*[[Mersenne Twister]]

==參考文獻==
{{refbegin}}
* {{cite journal | author = S.K. Park and K.W. Miller |title=Random Number Generators: Good Ones Are Hard To Find |journal=[[Communications of the ACM]] |year=1988 |volume=31 |issue=10 |pages=1192–1201 |url=http://portal.acm.org/citation.cfm?id=63042 |doi=10.1145/63039.63042}}
* [[Donald Knuth|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.&nbsp;10–26.
* {{cite journal |author=P. L'Ecuyer |title=Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure |journal=[[Mathematics of Computation]] |volume=68 |issue=225 |pages=249–260 |year=1999 |url=http://citeseer.ist.psu.edu/132363.html |doi=10.1090/S0025-5718-99-00996-5 |access-date=2012-12-30 |archive-date=2005-05-16 |archive-url=https://web.archive.org/web/20050516033120/http://citeseer.ist.psu.edu/132363.html |dead-url=no }}
* {{Citation | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press | publication-place=New York | isbn=978-0-521-88068-8 | chapter=Section 7.1.1. Some History | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=343 | accessdate=2012-12-30 | archive-date=2011-08-11 | archive-url=https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=343 | dead-url=no }}
*Gentle, James E., (2003). ''Random Number Generation and Monte Carlo Methods'', 2nd edition, Springer, ISBN 0-387-00178-6.
* {{cite journal |author=Joan Boyar |title=Inferring sequences produced by pseudo-random number generators |journal=[[Journal of the ACM]] |year=1989 |volume=36 |issue=1 |pages=129–141 |url=http://portal.acm.org/citation.cfm?id=59305&dl=ACM&coll=portal |doi=10.1145/58562.59305}} (in this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators).
{{refend}}

==外部連結==
* The simulation [http://www.vias.org/simulations/simusoft_lincong.html Linear Congruential Generator] {{Wayback|url=http://www.vias.org/simulations/simusoft_lincong.html |date=20210427234950 }} visualizes the correlations between the pseudo-random numbers when manipulating the parameters.
* [https://web.archive.org/web/20081211083300/http://www.cs.virginia.edu/~rjg7v/annotated.html Security of Random Number Generation: An Annotated Bibliography]
* [https://web.archive.org/web/20090108194540/http://www.math.niu.edu/~rusin/known-math/99/LCG Linear Congruential Generators post to sci.math]
* [http://www.goldsteintech.com/art/deathofart.html The "Death of Art" computer art project at Goldstein Technologies LLC, uses an LCG to generate 33,554,432 images] {{Wayback|url=http://www.goldsteintech.com/art/deathofart.html |date=20160409005539 }}
* [http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf  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.] {{Wayback|url=http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf |date=20210428031200 }}
* [https://web.archive.org/web/20120304102404/http://www.paragarora.com/2010/03/additive-congruential-method-maths-and-logic-behind-its-spread/ Additive Congruential Method : maths and logic behind its spread ]

[[Category:伪随机数生成器]]
[[Category:同余]]