Twisted GFSR generators II

ABSTRACT

The twisted GFSR generators proposed in a previous article have a defect in k-distribution for k larger than the order of recurrence. In this follow up article, we introduce and analyze a new TGFSR variant having better k-distribution property. We provide an efficient algorithm to obtain the order of equidistribution, together with a tight upper bound on the order. We discuss a method to search for generators attaining this bound, and we list some of these such generators. The upper bound turns out to be (sometimes far) less than the maximum order of equidistribution for a generator of that period length, but far more than that for a GFSR with a working are of the same size.

REFERENCES

• 1: FREDRICSSON, S.A. 1975. Pseudo-randomness properties of binary shift register sequences. IEEE Trans. Inf. Theory IT-21, 115-120
• 2: M. Fushimi, Random number generation with the recursion Xt=Xt-3p⊕Xt-3q , Journal of Computational and Applied Mathematics, v.31 n.1, p.105-118, July 1990 [doi>10.1016/0377-0427(90)90341-V ]
• 3: M. Fushimi , S. Tezuka, The k-distribution of generalized feedback shift register pseudorandom numbers, Communications of the ACM, v.26 n.7, p.516-523, July 1983 [doi>10.1145/358150.358159]
• 4: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 5: Pierre L'Ecuyer, Testing random number generators, Proceedings of the 24th conference on Winter simulation, p.305-313, December 13-16, 1992, Arlington, Virginia, United States [doi>10.1145/167293.167354]
• 6: L'ECU~ER, P. 1994. Uniform random number generation. An. Oper. Res. To be published.
• 7: LINDHOLM, J. H. 1968. An analysis of the pseudo-randomness properties of subsequences of long m-sequences. IEEE Trans. lnf. Theory IT-14 (July), 569 576.
• 8: Makoto Matsumoto , Yoshiharu Kurita, Twisted GFSR generators, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.2 n.3, p.179-194, July 1992 [doi>10.1145/146382.146383]
• 9: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Recurrences and difference equations

General Terms:
Algorithms, Experimentation, Theory

Keywords:
k-distribution, m-sequences, GFSR, TGFSR, finite fields