On the lattice structure of pseudorandom numbers generated over arbitrary finite fields (Q5941760)

Let \(\mathbb{F}_q\) be the finite field of order \(q=p^r\), where \(r\in\mathbb N\) and \(p\) is prime, and let \(\{\eta_n\}_{n=0}^\infty\) be a periodic sequence of elements of \(\mathbb F_q\) with period \(q\). Then the map \(\xi_n\mapsto \eta_n\) for \(n=0,1,\ldots\), where \(\{\xi_0,\xi_1,\ldots, \xi_{q-1}\}\) is any ordering of the elements of \(\mathbb F_q\) with \(\xi_0=0\) and \(\xi_{n+q}= \xi_n\) for \(n=0,1,\ldots\), can be represented by a uniquely determined polynomial \(g\in\mathbb F_q[x]\) with \(\deg(g)< q\), and so \[ \eta_n= g(\xi_n) \quad\text{for}\;n=0,1,\ldots\;.\tag \(*\) \] \textit{J. Eichenauer, H. Grothe}, and \textit{J. Lehn} [Metrika 35, 241--250 (1988; Zbl 0653.65006)] showed that a congruential generator modulo \(p\) passes the \(s\)-dimensional lattice test proposed by \textit{G. Marsaglia} [Applications of number theory to numerical analysis, Proc. Symp. Univ. Montreal 1971, New York: Academic Press, 249--285 (1972; Zbl 0266.65007)] if and only if \(s\leq \deg(g)\). In the present paper the authors prove that the generator \((*)\) over \(\mathbb F_q\) passes the \(s\)-dimensional lattice test if and only if the polynomials \(\varphi_0(g), \varphi_1(g),\ldots, \varphi_{s-1}(g)\) are linearly independent over \(\mathbb F_q\), where \(\varphi_j(g)(x)= g(x+\xi_j)- g(\xi_j)\) for \(j=0,\ldots, q-1\). Furthermore, they also derive from this criterion necessary conditions and a sufficient condition for passing the \(s\)-dimensional lattice test.