Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

An efficient implementation of linear feedback shift register sequences with a given characteristic polynomial is obtained by a new method. It involves a polynomial linear congruential generator over the finite field with two elements. We obtain maximal equidistribution by constructing a suitable output mapping. Local randomness could be improved by combining the generator's output with that of some other (e.g., nonlinear and efficient) generator.

REFERENCES

• 1: Raymond Couture , Pierre L'ecuyer, Lattice computations for random numbers, Mathematics of Computation, v.69 n.230, p.757-765, April 2000 [doi>10.1090/S0025-5718-99-01112-6]
• 2: L'Ecuyer, P. 1994. Uniform random number generation. Annals of Operations Research, 53:77-120.
• 3: Pierre L'Ecuyer, Maximally equidistributed combined Tausworthe generators, Mathematics of Computation, v.65 n.213, p.203-213, Jan. 1996 [doi>10.1090/S0025-5718-96-00696-5]
• 4: Gregory W. Fischer , Ziv Carmon , Dan Ariely , Gal Zauberman , Pierre L'Ecuyer, Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators, Operations Research, v.47 n.1, p.159-164, January 1999 [doi>10.1287/opre.47.1.159]
• 5: Pierre L'Ecuyer, Tables of maximally equidistributed combined LFSR generators, Mathematics of Computation, v.68 n.225, p.261-269, Jan. 1999 [doi>10.1090/S0025-5718-99-01039-X]
• 6: Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
• 7: Lindholm, J. H. 1968. An analysis of the pseudo-randomness properties of subsequences of long m-sequences. IEEE Transactions on Information Theory, IT-14(4):569-576.
• 8: Makoto Matsumoto , Yoshiharu Kurita, Twisted GFSR generators II, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.3, p.254-266, July 1994 [doi>10.1145/189443.189445]
• 9: Makoto Matsumoto , Takuji Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.3-30, Jan. 1998 [doi>10.1145/272991.272995]
• 10: Tausworthe, R. C. 1965. Random numbers generated by linear recurrence modulo two. Mathematics of Computation, 19:201-209.
• 11: Tezuka, S. 1995. Uniform random numbers: Theory and practice. Norwell, Mass.: Kluwer Academic Publishers.
• 12: Shu Tezuka , Pierre L'Ecuyer, Efficient and portable combined Tausworthe random number generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.2, p.99-112, April 1991 [doi>10.1145/116890.116892]
• 13: J. P. R. Tootill , W. D. Robinson , D. J. Eagle, An Asymptotically Random Tausworthe Sequence, Journal of the ACM (JACM), v.20 n.3, p.469-481, July 1973 [doi>10.1145/321765.321778]