Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Lower bounds for the discrepancy of inversive congruential pseudorandom numbers

Author: Harald Niederreiter
Journal: Math. Comp. 55 (1990), 277-287
MSC: Primary 65C10; Secondary 11K45
MathSciNet review: 1023766
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The inversive congruential method is a uniform pseudorandom number generator which was introduced recently. For a prime modulus p the discrepancy $ D_p^{(k)}$ of k-tuples of successive pseudorandom numbers generated by this method determines the statistical independence properties of these pseudorandom numbers. It was shown earlier by the author that

$\displaystyle D_p^{(k)} = O({p^{ - 1/2}}{(\log p)^k})\quad {\text{for}}\;2 \leq k < p.$

Here it is proved that this bound is essentially best possible. In fact, for a positive proportion of the admissible parameters in the inversive congruential method the discrepancy $ D_p^{(k)}$ is at least of the order of magnitude $ {p^{ - 1/2}}$ for all $ k \geq 2$.

References [Enhancements On Off] (What's this?)

  • [1] J. Eichenauer, H. Grothe, and J. Lehn, Marsaglia's lattice test and nonlinear congruential pseudo random number generators, Metrika 35 (1988), 241-250.
  • [2] J. Eichenauer and J. Lehn, A non-linear congruential pseudo random number generator, Statist. Hefte 27 (1986), 315-326. MR 877295 (88i:65014)
  • [3] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 4th ed., Clarendon Press, Oxford, 1960.
  • [4] R. Lidl and H. Niederreiter, Finite fields, Addison-Wesley, Reading, Mass., 1983. MR 746963 (86c:11106)
  • [5] H. Niederreiter, Pseudo-random numbers and optimal coefficients, Adv. in Math. 26 (1977), 99-181. MR 0476679 (57:16238)
  • [6] -, The serial test for pseudo-random numbers generated by the linear congruential method, Numer. Math. 46 (1985), 51-68. MR 777824 (86i:65010)
  • [7] H. Niederreiter, Remarks on nonlinear congruential pseudorandom numbers, Metrika 35 (1988), 321-328. MR 980847 (90e:11119)
  • [8] -, The serial test for congruential pseudorandom numbers generated by inversions, Math. Comp. 52 (1989), 135-144. MR 971407 (90e:65008)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65C10, 11K45

Retrieve articles in all journals with MSC: 65C10, 11K45

Additional Information

Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society