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
DOI:
https://doi.org/10.1090/S0025-5718-1990-1023766-0
MathSciNet review:
1023766
Full-text PDF Free Access
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 \[ 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$.
-
J. Eichenauer, H. Grothe, and J. Lehn, Marsaglia’s lattice test and nonlinear congruential pseudo random number generators, Metrika 35 (1988), 241-250.
- Jürgen Eichenauer and Jürgen Lehn, A nonlinear congruential pseudorandom number generator, Statist. Hefte 27 (1986), no. 4, 315–326. MR 877295 G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 4th ed., Clarendon Press, Oxford, 1960.
- Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
- Harald Niederreiter, Pseudo-random numbers and optimal coefficients, Advances in Math. 26 (1977), no. 2, 99–181. MR 476679, DOI https://doi.org/10.1016/0001-8708%2877%2990028-7
- Harald Niederreiter, The serial test for pseudorandom numbers generated by the linear congruential method, Numer. Math. 46 (1985), no. 1, 51–68. MR 777824, DOI https://doi.org/10.1007/BF01400255
- H. Niederreiter, Remarks on nonlinear congruential pseudorandom numbers, Metrika 35 (1988), no. 6, 321–328. MR 980847, DOI https://doi.org/10.1007/BF02613320
- Harald Niederreiter, The serial test for congruential pseudorandom numbers generated by inversions, Math. Comp. 52 (1989), no. 185, 135–144. MR 971407, DOI https://doi.org/10.1090/S0025-5718-1989-0971407-2
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