Digital inversive pseudorandom numbers

ABSTRACT

A new algorithm, the digital inversive method, for generating uniform pseudorandom numbers is introduced. This algorithm starts from an inversive recursion in a large finite field and derives pseudorandom numbers from it by the digital method. If the underlying finite field has q elements, then the sequences of digital inversive pseudorandom numbers with maximum possible period length q can be characterized. Sequences of multiprecision pseudorandom numbers with very large period lengths are easily obtained by this new method. Digital inversive pseudorandom numbers satisfy statistical independence properties that are close to those of truly random numbers in the sense of asymptotic discrepancy. If q is a power of 2, then the digital inversive method can be implemented in a very fast manner.

REFERENCES

• 1: CHOU, W.-S. 1995. On inversive maximal period polynomials over finite fields. Appl. Algebra Eng. Commun. Comput. Forthcoming.
• 2: EICHENAUER-HERRMANN, J. 1995. Pseudorandom number generation by nonlinear methods. Int. Stat. Rev. Forthcoming.
• 3: EICHENAUER-HERRMANN, J. 1992. Inversive congruential pseudorandom numbers: A tutorial. Int. Stat. Rev. 60, 167-176.
• 4: HANSEN, T. AND MULLEN, G.L. 1992. Primitive polynomials over finite fields. Math. Comput. 59, 639-643, S47-S50.
• 5: Toshiya Itoh , Shigeo Tsujii, A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases, Information and Computation, v.78 n.3, p.171-177, Sept. 1988 [doi>10.1016/0890-5401(88)90024-7]
• 6: JUNCMCKEL, D. 1993. Finite Fields: Structure and Arithmetics. Bibliographisches Institut, Mannheim, Germany.
• 7: I4JEFER, J. 1961. On large deviations of the empiric d.f. of vector chance variables and a law of the iterated logarithm. Pac. J. Math. 11,649-660.
• 8: Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
• 9: MENEZES, A.J., BLAKE, I.F., GAO, X.H., MULLIN, R.C., VANSTONE, S.A., AND YAGHOOBIAN, T. 1993. Applications of Finite Fields. Kluwer, Boston, Mass.
• 10: Harald Niederreiter, Pseudorandom vector generation by the inversive method, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.2, p.191-212, April 1994 [doi>10.1145/175007.175015]
• 11: NIEDERREITER, H. 1992a. Nonlinear methods for pseudorandom number and vector generation. In Simulation and Optimization, G. Pfiug and U. Dieter, Eds. Lecture Notes in Economics and Mathematical Systems, vol. 374. Springer, Berlin, 145-153.
• 12: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 13: Miodrag Živkovic, A table of primitive binary polynomials, Mathematics of Computation, v.62 n.205, p.385-386, Jan. 1994 [doi>10.2307/2153416]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
digital pseudorandom numbers, discrepancy, inversive method, statistical independence