|
On the distribution of inversive congruential pseudorandom numbers in parts of the period
Author(s):
Harald
Niederreiter;
Igor
E.
Shparlinski.
Journal:
Math. Comp.
70
(2001),
1569-1574.
MSC (2000):
Primary 11K45, 65C10;
Secondary 11K38, 11L07, 11T23
Posted:
June 12, 2000
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
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:
-
- 1.
- T. Cochrane, `On a trigonometric inequality of Vinogradov', J. Number Theory, 27 (1987), 9-16. MR 88k:11053
- 2.
- J. Eichenauer-Herrmann and F. Emmerich, `Compound inversive congruential pseudorandom numbers: an average-case analysis', Math. Comp., 65 (1996), 215-225. MR 96i:65005
- 3.
- J. Eichenauer-Herrmann, F. Emmerich, and G. Larcher, `Average discrepancy, hyperplanes, and compound pseudorandom numbers', Finite Fields Appl., 3 (1997), 203-218. MR 98j:11059
- 4.
- 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.
- 5.
- M. Flahive and H. Niederreiter, `On inversive congruential generators for pseudorandom numbers', Finite Fields, Coding Theory, and Advances in Communications and Computing (G.L. Mullen and P.J.-S. Shiue, eds.), Marcel Dekker, New York, 1993, 75-80. MR 94a:11117
- 6.
- 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.
- 7.
- R. Lidl and H. Niederreiter, `Finite fields and their applications', Handbook of Algebra (M. Hazewinkel, ed.), Vol. 1, Elsevier, Amsterdam, 1996, 321-363. MR 97i:11114
- 8.
- R. Lidl and H. Niederreiter, Finite fields, Cambridge University Press, Cambridge, 1997. MR 97i:11115
- 9.
- H. Niederreiter, `The serial test for congruential pseudorandom numbers generated by inversions', Math. Comp., 52 (1989), 135-144.
- 10.
- H. Niederreiter, Random number generation and quasi-Monte Carlo methods, SIAM, Philadelphia, 1992. MR 93h:65008
- 11.
- H. Niederreiter, `Finite fields, pseudorandom numbers, and quasirandom points', Finite Fields, Coding Theory, and Advances in Communications and Computing (G.L. Mullen and P.J.-S. Shiue, eds.), Marcel Dekker, New York, 1993, 375-394. MR 94a:11121
- 12.
- H. Niederreiter, `New developments in uniform pseudorandom number and vector generation', Lect. Notes in Statistics, Springer-Verlag, Berlin, 106 (1995), 87-120. MR 97k:65019
- 13.
- H. Niederreiter and I.E. Shparlinski, `On the distribution and lattice structure of nonlinear congruential pseudorandom numbers', Finite Fields Appl., 5 (1999), 246-253. CMP 99:17
- 14.
- S.B. Steckin, `An estimate of a complete rational trigonometric sum', Trudy Mat. Inst. Steklov., 143 (1977), 188-207 (in Russian). MR 58:543
Similar Articles:
Retrieve articles in Mathematics of Computation
with MSC
(2000):
11K45, 65C10,
11K38, 11L07, 11T23
Retrieve articles in all Journals with MSC
(2000):
11K45, 65C10,
11K38, 11L07, 11T23
Additional Information:
Harald
Niederreiter
Affiliation:
Institute of Discrete Mathematics, Austrian Academy of Sciences, Sonnenfelsgasse 19, A--1010 Vienna, Austria
Email:
niederreiter@oeaw.ac.at
Igor
E.
Shparlinski
Affiliation:
Department of Computing, Macquarie University, New South Wales 2109, Australia
Email:
igor@comp.mq.edu.au
DOI:
10.1090/S0025-5718-00-01273-4
PII:
S 0025-5718(00)01273-4
Keywords:
Pseudorandom numbers,
inversive congruential method,
discrepancy,
exponential sums
Received by editor(s):
November 17, 1998
Received by editor(s) in revised form:
November 19, 1999
Posted:
June 12, 2000
Copyright of article:
Copyright
2000,
American Mathematical Society
|
Comments: webmaster@ams.org