Equidistribution properties of nonlinear congruential pseudorandom numbers
type: Item
instance of: scholarly article
title: Equidistribution properties of nonlinear congruential pseudorandom numbers
zbMATH Open document ID: 0787.65003
DOI: 10.1007/BF02613697
published in: Metrika
publication date: 1994-01-26T00:00:00Z
full work available at URL: https://eudml.org/doc/176480
review text: 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)].
reviewed by: Yaochen Zhu
Mathematics Subject Classification ID: 65C10
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 11K38
zbMATH DE Number: 488312
zbMATH Keywords: finite field
zbMATH Keywords: discrepancy
zbMATH Keywords: sequence of nonlinear congruential pseudorandom numbers
author: Jürgen Eichenauer-Herrmann
MaRDI profile type: Publication
cites work: An Estimate Concerning the Kolmogroff Limit Distribution
cites work: On a trigonometric inequality of Vinogradov
cites work: Marsaglia's lattice test and non-linear congruential pseudo-random number generators
cites work: Inversive Congruential Pseudorandom Numbers: A Tutorial
cites work: Lower Bounds for the Discrepancy of Inversive Congruential Pseudorandom Numbers with Power of Two Modulus
cites work: Q3216750
cites work: Remarks on nonlinear congruential pseudorandom numbers
cites work: Statistical independence of nonlinear congruential pseudorandom numbers
cites work: Lower Bounds for the Discrepancy of Inversive Congruential Pseudorandom Numbers
cites work: Recent trends in random number and random vector generation
cites work: Q4026983
cites work: Q4003879
cites work: Q4295076
cites work: On Some Exponential Sums
OpenAlex ID: W2074838884
description: scientific article; zbMATH DE number 488312