The k-distribution of generalized feedback shift register pseudorandom numbers

ABSTRACT

A necessary and sufficient condition is established for the generalized feedback shift register (GFSR) sequence introduced by Lewis and Payne to be k-distributed. Based upon the theorem, a theoretical test for k-distributivity is proposed and performed in a reasonable amount of computer time, even for k = 16 and a high degree of resolution (for which statistical tests are impossible because of the astronomical amount of computer time required). For the special class of GFSR generators considered by Arvillias and Maritsas based on the primitive trinomial Dp + Dq + 1 with q = an integral power of 2, it is shown that the sequence is k-distributed if and only if the lengths of all subregisters are at least k. The theorem also leads to a simple and efficient method of initializing the GFSR generator so that the sequence to be generated is k-distributed.

REFERENCES

• 1: A. C. Arvillias , D. G. Maritsas, Partitioning the Period of a Class of m-Sequences and Application to Pseudorandom Number Generation, Journal of the ACM (JACM), v.25 n.4, p.675-686, Oct. 1978 [doi>10.1145/322092.322106]
• 2: Arvillias, A.C., and Maritsas, D.G. Toggle registers generating in parallel k kth decimations of m-sequences x p + x k + 1---design tables. IEEE Trans. Camput. C-28, 2(Feb. 1979), 89-101.
• 3: Herbert S. Bright , Richard L. Enison, Quasi-Random Number Sequences from a Long-Period TLP Generator with Remarks on Application to Cryptography, ACM Computing Surveys (CSUR), v.11 n.4, p.357-370, Dec. 1979 [doi>10.1145/356789.356795]
• 4: Fushimi, M., and Tezuka, S. A method for generating a sequence of pseudorandom numbers with multidimensional eqnidistributivity (in Japanese). Japanese J. Appl. Star. 10, 30Vlar. 1982), 151-163.
• 5: Solomon W. Golomb , Soloman Golomb, Shift Register Sequences, Aegean Park Press, Laguna Hills, CA, 1981
• 6: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 7: Latawiec, K.J. New method of generation of shifted linear pseudorandom binary sequences. Proc. IEEE (London) 121, 8(Aug, 1974), 905-906.
• 8: T. G. Lewis , W. H. Payne, Generalized Feedback Shift Register Pseudorandom Number Algorithm, Journal of the ACM (JACM), v.20 n.3, p.456-468, July 1973 [doi>10.1145/321765.321777]
• 9: Marsaglia, G. Random numbers fall mainly on the planes. Prac. Nat. Acad. Sci. 61, l(sapt. 1968), 25-28.
• 10: Marsaglia, G. The structure of linear congruential sequences. In S.K. Zaremba (Ed.) Applications of Number Theory to Numerica/Ana/ysis, Academic Press, New York, 1972.
• 11: W. H. Payne , K. L. McMillen, Orderly enumeration of nonsingular binary matrices applied to text encryption, Communications of the ACM, v.21 n.4, p.259-263, April 1978 [doi>10.1145/359460.359464]
• 12: Anthony Ralston, Encyclopedia of Computer Science, Van Nostrand Reinhold Co., New York, NY, 1976
• 13: Tausworthe, R.C. Random numbers generated by linear recurrence modulo two. Math. Comp. 19(1965), 201-209.
• 14: J. P. R. Tootill , W. D. Robinson , A. G. Adams, The Runs Up-and-Down Performance of Tausworthe Pseudo-Random Number Generators, Journal of the ACM (JACM), v.18 n.3, p.381-399, July 1971 [doi>10.1145/321650.321655]
• 15: 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]
• 16: Zierler, N., and Brinhart, J. On primitive trinomials (mod 2), II. Inf. Control 14(1969), 566-569.

INDEX TERMS

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

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

General Terms:
Algorithms

Keywords:
K-distribution, M-sequences, feedback shift registers, linear computation on GF(2)