On the distribution and lattice structure of nonlinear congruential pseudorandom numbers (Q1964063): Difference between revisions

Let \(p\) be prime. Define a sequence \((u_n)\) by \[ u_{n+1}\equiv f(u_n)\pmod p, \quad 0\leq u_n\leq p-1, \;n\geq 0, \] with some initial value \(u_0\), where \(f(X)\in \mathbb{F}_p(X)\) is a rational function over the field \(\mathbb{F}_p\) of \(p\) elements. The sequence \((u_n)\) is periodic with some period \(t\leq p\). Let \(D_s(N)\) denote the discrepancy of the points \((u_n/p,\dots, u_{n+s-1}/p)\) \((n=0,\dots, N-1)\) in \([0,1)^s\). In this paper the authors consider the case of \(f(X)\in \mathbb{F}_p[X]\) with degree \(d\geq 2\). They prove that if the sequence \((u_n)\) is purely periodic with period \(t\) and \(t\geq N\geq 1\), then \[ D_s(N)= O_{d,s} (N^{-1/2} p^{1/2} \log^{-1/2} p (\log\log p)^s); \] and in the case of \(t=p\), this sequence passes the \(s\)-dimensional lattice test for all positive \(s\leq \lceil p/d\rceil\). The extension of this result to the case \(f(X)\in \mathbb{F}_p(X)\) will be valuable. The method of this paper is also able to deal with the case of composite modulus, and to study the distribution of sequences satisfying nonlinear recurrence relations of order \(m\geq 2\) over \(\mathbb{F}_p\).