Statistical independence of nonlinear congruential pseudorandom numbers (Q1107254)

Nonlinear congruential pseudorandom numbers were introduced by \textit{J. Eichenauer}, \textit{H. Grothe} and \textit{J. Lehn} [Metrika 35, 241-250 (1988))] in the following way. Let p be large prime and generate a sequence \(y_ 0,y_ 1,..\). of integers in \(F_ p=\{0,1,...,p-1\}\) by the recursion \(y_{n+1}\equiv f(y_ n)mod p\) for \(n=0,1,...\), where f is an integer-valued function on \(F_ p\) such that the sequence of \(y_ n\) is purely periodic with period \(p\) and \(\{y_ 0,y_ 1,...,y_{p- 1}\}=F_ p\). Then the pseudorandom numbers \(x_ n\) are obtained by \(x_ n=y_ n/p\). The following equivalent description was given by the author [Metrika (to appear)]: there exists a uniquely determined polynomial \(g\) over the finite field \(F_ p\) such that \(y_ n=g(n)\) for all \(n\in F_ p\) and \(1\leq s:=\deg (g)\leq p-2\), where \(\{g(0),g(1),...,g(p-1)\}=F_ p.\) In the present paper the behavior of these pseudorandom numbers under the \(k\)-dimensional serial test is investigated by considering the discrepancy \(D_ N^{(k)}\) of the points \(\bar x_ n=(x_ n,x_{n+1},...,x_{n+k-1})\), \(n=0,1,...,N-1\). It is shown that \(D_ p^{(k)}=O(sp^{-1/2}(\log p)^ k)\) for all \(k\leq s\) and \(D_ N^{(K)}=O(N^{-1}sp^{1/2}(\log p)^{k+1})\) for \(1\leq N<p\) and all \(k\leq s-1\). It is also proved that these bounds are essentially best possible. As a consequence, nonlinear congruential pseudorandom numbers with an appropriate value of \(s\) have satisfactory statistical independence properties up to rather high dimensions.