Statistical independence of nonlinear congruential pseudorandom numbers
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.
statistical independence of nonlinear congruential pseudorandom numbers
Nonlinear congruential pseudorandom numbers
scientific article; zbMATH DE number 4064342