线性同余方法(LCG)是个产生伪随机数的方法。 它是根据递归公式: 其中是产生器设定的常数。 LCG的周期最大为,但大部分情况都会少于M。要令LCG达到最大周期,应符合以下条件: 互质;的所有质因数都能整除;若是4的倍数,也是;都比小;是正整数。
[micxp_threadbk]
[micxp_title]
随机性
参见
参考文献
外部链接
[/micxp_title]
[#]
因为通过线性同余方法构建的伪随机数生成器的内部状态可以轻易地由其输出演算得知,所以此种伪随机数生成器属于统计学伪随机数生成器。
设计密码学的应用必须至少使用密码学安全伪随机数生成器,故需要避免由线性同余方法获得的随机数在密码学中的应用。
[##]
[###]
- 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. doi:10.1090/S0025-5718-99-00996-5.
- 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, ISBN 978-0-521-88068-8
- 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
分类:隐藏分类:
[/micxp_threadbk] |