# zbMATH — the first resource for mathematics

Equidistribution properties of nonlinear congruential pseudorandom numbers. (English) Zbl 0787.65003
Let $$p\geq 5$$ be a prime and identify $$\mathbb{Z}_ p:= \{0,1,\dots,p-1\}$$ with the finite field of order $$p$$. Let $$\gamma\in \mathbb{Z}_ p\backslash\{0\}$$, $$g: \mathbb{Z}\to\mathbb{Z}_ p$$ be a monic permutation polynomial of $$\mathbb{Z}_ p$$ with degree $$s$$ as a polynomial over $$\mathbb{Z}_ p$$, where $$3\leq s\leq p-2$$. Define a sequence of elements of $$\mathbb{Z}_ p$$: $$(y_ n)_{n\geq 0}$$ by $$y_ n\equiv \gamma g(n) (\text{mod } p)$$, $$n\geq 0$$, and let $$x_ n= y_ n/p$$ $$(n\geq 0)$$. The author proves that the discrepancy $$D_ N$$ of the sequence of nonlinear congruential pseudorandom numbers $$\{x_ 0,x_ 1,\dots,x_{N-1}\}$$ $$(1\leq N<p)$$ satisfies $D_ N<(s-1) {p^{1/2}\over N}\left({4\over \pi^ 2}\log p+ 0.38+ {0.608\over p}+ {0.116\over p^ 2}\right)^ 2+ {1\over p},$ and also shows that this upper bound for $$D_ N$$ is best possible up to the logarithmic factor. This estimate slightly improves the result of H. Niederreiter [Monatsh. Math. 106, No. 2, 149-159 (1988; Zbl 0652.65007)].

##### MSC:
 65C10 Random number generation in numerical analysis 11K45 Pseudo-random numbers; Monte Carlo methods 11K38 Irregularities of distribution, discrepancy
Full Text:
##### References:
  Chung KL (1949) An estimate concerning the Kolmogoroff limit distribution, Trans. Amer. Math. Soc. 67:36–50 · Zbl 0034.22602  Cochrane T (1987) On a trigonometric inequality of Vinogradov, J. Number Th. 27:9–16 · Zbl 0629.10030  Eichenauer J, Grothe H, Lehn J (1988) Marsaglia’s lattice test and non-linear congruential pseudo random number generators, Metrika 35:241–250 · Zbl 0653.65006  Eichenauer-Herrmann J (1992) Inversive congruential pseudorandom numbers: a tutorial, Int. Statist. Rev. 60:167–176 · Zbl 0766.65002  Eichenauer-Herrmann J, Niederreiter H (1992) On the statistical independence of nonlinear congruential pseudorandom numbers (submitted for publication) · Zbl 0762.65001  Lidl R, Niederreiter H (1983) Finite fields, Addison-Wesley, Reading, Mass. · Zbl 0554.12010  Niederreiter H (1988a) Remarks on nonlinear congruential pseudorandom numbers, Metrika 35: 321–328 · Zbl 0663.65005  Niederreiter H (1988b) Statistical independence of nonlinear congruential pseudorandom numbers, Monatsh. Math. 106:149–159 · Zbl 0652.65007  Niederreiter H (1990) Lower bounds for the discrepancy of inversive congruential pseudorandom numbers, Math. Comp. 55:277–287 · Zbl 0708.65006  Niederreiter H (1991) Recent trends in random number and random vector generation, Ann. Operations Res. 31:323–345 · Zbl 0737.65001  Niederreiter H (1992a) Nonlinear methods for pseudorandom number and vector generation. In: Pflug, G. and Dieter, U. (eds.) Simulation and Optimization, Lecture Notes in Economics and Math. Systems 374:145–153, Springer, Berlin · Zbl 0849.11055  Niederreiter H (1992b) Random number generation and quasi-Monte Carlo methods, SIAM, Philadelphia · Zbl 0761.65002  Niederreiter H (1992c) Pseudorandom numbers and quasirandom points, Z. Angew. Math. Mech. (to appear) · Zbl 0796.11028  Weil A (1948) On some exponential sums, Proc. Nat. Acad. Sci. U.S.A. 34:204–207 · Zbl 0032.26102
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.