On the distribution of inversive congruential pseudorandom numbers in parts of the period

Niederreiter, Harald; Shparlinski, Igor

doi:10.1090/S0025-5718-00-01273-4

On the distribution of inversive congruential pseudorandom numbers in parts of the period
HTML articles powered by AMS MathViewer

by Harald Niederreiter and Igor E. Shparlinski PDF

Math. Comp. 70 (2001), 1569-1574 Request permission

Abstract:

The inversive congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. In this paper we present the first nontrivial bounds on the discrepancy of individual sequences of inversive congruential pseudorandom numbers in parts of the period. The proof is based on a new bound for certain incomplete exponential sums.

References

Todd Cochrane, On a trigonometric inequality of Vinogradov, J. Number Theory 27 (1987), no. 1, 9–16. MR 904002, DOI 10.1016/0022-314X(87)90045-X
Jürgen Eichenauer-Herrmann and Frank Emmerich, Compound inversive congruential pseudorandom numbers: an average-case analysis, Math. Comp. 65 (1996), no. 213, 215–225. MR 1322889, DOI 10.1090/S0025-5718-96-00675-8
Jürgen Eichenauer-Herrmann, Frank Emmerich, and Gerhard Larcher, Average discrepancy, hyperplanes, and compound pseudorandom numbers, Finite Fields Appl. 3 (1997), no. 3, 203–218. MR 1459824, DOI 10.1006/ffta.1997.0180
J. Eichenauer-Herrmann, E. Herrmann, and S. Wegenkittl, ‘A survey of quadratic and inversive congruential pseudorandom numbers’, Lect. Notes in Statistics, Springer-Verlag, Berlin, 127 (1998), 66–97.
Mary Flahive and Harald Niederreiter, On inversive congruential generators for pseudorandom numbers, Finite fields, coding theory, and advances in communications and computing (Las Vegas, NV, 1991) Lecture Notes in Pure and Appl. Math., vol. 141, Dekker, New York, 1993, pp. 75–80. MR 1199823
J.B. Friedlander, D. Lieman, and I.E. Shparlinski, ‘On the distribution of the RSA generator’, Sequences and Their Applications (C. Ding, T. Helleseth, and H. Niederreiter, eds.), Springer-Verlag, London, 1999, 205–212.
Rudolf Lidl and Harald Niederreiter, Finite fields and their applications, Handbook of algebra, Vol. 1, Handb. Algebr., vol. 1, Elsevier/North-Holland, Amsterdam, 1996, pp. 321–363. MR 1421805, DOI 10.1016/S1570-7954(96)80013-1
Rudolf Lidl and Harald Niederreiter, Finite fields, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 20, Cambridge University Press, Cambridge, 1997. With a foreword by P. M. Cohn. MR 1429394
H. Niederreiter, ‘The serial test for congruential pseudorandom numbers generated by inversions’, Math. Comp., 52 (1989), 135–144.
Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
Harald Niederreiter, Finite fields, pseudorandom numbers, and quasirandom points, Finite fields, coding theory, and advances in communications and computing (Las Vegas, NV, 1991) Lecture Notes in Pure and Appl. Math., vol. 141, Dekker, New York, 1993, pp. 375–394. MR 1199844
Harald Niederreiter, New developments in uniform pseudorandom number and vector generation, Monte Carlo and quasi-Monte Carlo methods in scientific computing (Las Vegas, NV, 1994) Lect. Notes Stat., vol. 106, Springer, New York, 1995, pp. 87–120. MR 1445782, DOI 10.1007/978-1-4612-2552-2_{5}
H. Niederreiter and I.E. Shparlinski, ‘On the distribution and lattice structure of nonlinear congruential pseudorandom numbers’, Finite Fields Appl., 5 (1999), 246–253.
S. B. Stečkin, An estimate of a complete rational trigonometric sum, Trudy Mat. Inst. Steklov. 143 (1977), 188–207, 211 (Russian). Analytic number theory, mathematical analysis and their applications (dedicated to I. M. Vinogradov on his 85th birthday). MR 0480376