Remarks on nonlinear congruential pseudorandom numbers (Q1114287)

Let \(x_ 1,x_ 2,...,x_ n,..\). be a sequence of pseudorandom numbers obtained by a generator producing a permutation of \(\{\) 1,2,...,p\(\}\), p a prime. Let \(u_ n=(0,x_{n+1}-x_ n,x_{n+2}-x_ n,...,x_{n+p- 1}-x_ n)\) and \(G^{(d)}\) be the \(d\times p\) matrix with rows \(u_ 0,u_ 1,...,u_{d-1}\). We say that the generator passes the d- dimensional lattice test iff rank \((G^{(d)})=d\). Consider the generator \(x_{n+1}=ax_ n+b\), where \(\bar O=O\), \(\bar c=c^{-1}\) (in the field \(F_ p)\). If this generator has period p then it passes the lattice test for all \(d\leq (p+1)/2\). Some generalizations of the result for the fields \(F_ q\) where q is some power of a prime \(p\geq 3\) are given.