zbMATH — the first resource for mathematics

Lower bounds for the discrepancy of inversive congruential pseudorandom numbers. (English) Zbl 0708.65006
For a short general discussion of the generators see p. 93, and 94 of [P. L’Écuyer: Random numbers for simulation, CACM 33, 86 ff. (1990)] who also explains discrepancy (informally) and its importance.
After a short definition of inverse linear congruential generators (special case of linear rational congruential generators) in the introduction, it is proved that an earlier derived lower bound for the discrepancy in the case of prime modulus p is in fact essentielly best possible. The proof requires (the full of the paper and) recourse to number theory concerning primitive polynomials over the finite field of p elements and some theorems on characters in this field. Thereby several interesting results on character sums and the number of quadratic primitive polynomials are obtained.
Reviewer: K.G.Brokate

65C10 Random number generation in numerical analysis
11K45 Pseudo-random numbers; Monte Carlo methods
Full Text: DOI
[1] J. Eichenauer, H. Grothe, and J. Lehn, Marsaglia’s lattice test and nonlinear congruential pseudo random number generators, Metrika 35 (1988), 241-250. · Zbl 0653.65006
[2] Jürgen Eichenauer and Jürgen Lehn, A nonlinear congruential pseudorandom number generator, Statist. Hefte 27 (1986), no. 4, 315 – 326. · Zbl 0607.65001
[3] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 4th ed., Clarendon Press, Oxford, 1960. · Zbl 0086.25803
[4] 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. · Zbl 0629.12016
[5] Harald Niederreiter, Pseudo-random numbers and optimal coefficients, Advances in Math. 26 (1977), no. 2, 99 – 181. · Zbl 0366.65004
[6] Harald Niederreiter, The serial test for pseudorandom numbers generated by the linear congruential method, Numer. Math. 46 (1985), no. 1, 51 – 68. · Zbl 0541.65004
[7] H. Niederreiter, Remarks on nonlinear congruential pseudorandom numbers, Metrika 35 (1988), no. 6, 321 – 328. · Zbl 0663.65005
[8] Harald Niederreiter, The serial test for congruential pseudorandom numbers generated by inversions, Math. Comp. 52 (1989), no. 185, 135 – 144. · Zbl 0657.65007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.