Equidistribution properties of nonlinear congruential pseudorandom numbers (Q1312212)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Equidistribution properties of nonlinear congruential pseudorandom numbers
scientific article

    Statements

    Equidistribution properties of nonlinear congruential pseudorandom numbers (English)
    0 references
    0 references
    26 January 1994
    0 references
    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)].
    0 references
    0 references
    finite field
    0 references
    discrepancy
    0 references
    sequence of nonlinear congruential pseudorandom numbers
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references