Equidistribution properties of nonlinear congruential pseudorandom numbers (Q1312212)

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 \textit{H. Niederreiter} [Monatsh. Math. 106, No. 2, 149-159 (1988; Zbl 0652.65007)].