Generalized Lehmer-Tausworthe random number generators

ABSTRACT

We study a general class of random number generators which includes Lehmer's congruential generator and the Tausworthe shift-register generator as special cases. The generators in this class use a general linear recurrence relation defined by a primitive polynomial over a large finite field. This generator, like the Tausworthe generator, has the property of the k-space equi-distribution. We give some theoretical and heuristic justification for its asymptotic uniformity as well as asymptotic independence from a statistical theory viewpoint. In this paper, we also propose an efficient method of finding primitive polynomials in a large finite field. Several generators with extremely long cycles are presented.

REFERENCES

• 1: Stuart L. Anderson, Random number generations generators on Vector supercomputers and other advanced architectures, SIAM Review, v.32 n.2, p.221-251, June 1990 [doi>10.1137/1032044]
• 2: Alanen, J. D. and D. E. Knuth (1964), "Tables of finite fields," Sankhyfi, Series A, 26,305-328.
• 3: Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 4: Deng, L. Y. (1990), "Elements of maximum order in a matrix group," SIAM Review, Problems and Solutions Section, 32, No. 3,479.
• 5: Dung, L. Y. (1992), "Asymptotic independence of pseudorandom sequence generated by combination generators,"submitted.
• 6: Lih-Yuan Deng , Yu-Chao Chu, Combining random number generators, Proceedings of the 23rd conference on Winter simulation, p.1043-1046, December 08-11, 1991, Phoenix, Arizona, United States
• 7: Deng, L. Y. and E. O. George (1990), "Generation of uniform variates from several nearly uniformly distributed variables," Communications In Statistics B 17, No. 1,145-154.
• 8: Lih-Yuan Deng , E. Olusegun George , Yu-Chao Chu, On improving pseudo-random number generators, Proceedings of the 23rd conference on Winter simulation, p.1035-1042, December 08-11, 1991, Phoenix, Arizona, United States
• 9: Deng, L. Y. and C. Rousseau (1991), "Recent development in random number generation", in: Proceedings of the 29th Annual ACM Southeast Regional Conference, Auburn Alabama, April 10-12, 89-94.
• 10: Deng, L. Y., C. Rousseau and .Y. Yuan (1992), "A study of two extensions of Lehmer's congruential generator,"submitted.
• 11: Franklin, J. N. (1964), "Equidistribution of matrixpower residues modulo one," Math. Comp. , 18, 560-568.
• 12: Grothe, H. (198"/), "Matrix generators for pseudorandom vector generation ," Statist. Papers, 28, 233-238.
• 13: Solomon W. Golomb , Soloman Golomb, Shift Register Sequences, Aegean Park Press, Laguna Hills, CA, 1981
• 14: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 15: P. L'Ecuyer, Efficient and portable combined random number generators, Communications of the ACM, v.31 n.6, p.742-751, June 1988 [doi>10.1145/62959.62969]
• 16: P. L'Ecuyer, A tutorial on uniform variate generation, Proceedings of the 21st conference on Winter simulation, p.40-49, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76744]
• 17: Pierre L'Ecuer , François Blouin, Linear congruential generators of order K>1, Proceedings of the 20th conference on Winter simulation, p.432-439, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318229]
• 18: Pierre L'Ecuyer, Random numbers for simulation, Communications of the ACM, v.33 n.10, p.85-97, Oct. 1990 [doi>10.1145/84537.84555]
• 19: Lehmer, D. H. (1951), "Mathematical Methods in Large-scale Computing Units", in: Proceedings of the Second Symposium on Large Scale Digital Computing Machinery, Harvard University Press: Cambridge, 141-146.
• 20: Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
• 21: Marsaglia, G. (1968), "Random numbers fall mainly in planes," Proceedings of the National Academic of Sciences, 61, 25-28.
• 22: Marsaglia, G. (1985), "A current view of random number generators", in: Proceedings of the 16th Symposium on the Interface, (editor L. Billard) , 3-10, Elsevier Science Publishers: North-Holland.
• 23: Niederreiter , H. (1984), "The performance of kstep pseudorandorn number generation under the uniformity test," SIAM J. Sci. Star. Comput. , 5, 798-810.
• 24: Niederreiter , H. (1986), "A pseudorandom vector generator based on finite field arithmetic ," Math. Japon., 31,759-774.
• 25: W. H. Payne , J. R. Rabung , T. P. Bogyo, Coding the Lehmer pseudo-random number generator, Communications of the ACM, v.12 n.2, p.85-86, Feb. 1969 [doi>10.1145/362848.362860]
• 26: Stahnke, W. (1973), "Primitive binary polynomials ," Math. Comp., 27,977-980.
• 27: Tausworthe, It. C. (1965), "Random numbers generated by linear recurrence modulo two," Math. Comp. , 19,201-209.
• 28: Watson, E. J. (1962), "primitive polynomials (rood 2)," Math. Comp., 16,368-369.
• 29: Wichmann, B. A. and I. D. Hill (1982), "An efficient and portable pseudo-random number generator ," Appl. Statist, 31,188-190.
• 30: Zierler, N. (1959), "Linear recurring sequences," J. SIAM, 7, 31-48.
• 31: Zierler, N. and J. Brillhart (1968), "On primitive trinomials (Mod 2), I," Information Control, 13, 541-554.
• 32: Zierler, N. and J. Brillhart (1969), "On primitive trinomials (Mod 2), II," Information Control, 14, 566-569.