Lattice structure and linear complexity of nonlinear pseudorandom numbers (Q1861173)

Let \(q\) be a prime power and \(\mathbb F_q\) be the finite field of order \(q\). Let \(s\geq 1\). the authors first give an extended version of Marsaglia's lattice test as follows: A sequence \(\eta_0, \eta_1,\dots\) over \(\mathbb F_q\) passes the \(s\)-dimensional lattice test if the vectors \(\vec\eta_n- \vec\eta_0\) for \(n\geq 0\) span \(\mathbb F_q^s\), where \(\vec\eta_n= (\eta_n, \eta_{n+1},\dots, \eta_{n+s-1})\) for \(n\geq 0\). Moreover, the linear complexity \(L(\eta_n)\) of a sequence \(\eta_0, \eta_1,\dots, \) over \(\mathbb F_q\) means the least nonnegative integer \(L\) such that there are constants \(\gamma_0,\dots, \gamma_{L-1}\in \mathbb F_q\) satisfying \(\eta_{n+L}+ \gamma_{L-1} \eta_{n+L-1} +\cdots+ \gamma_0\eta_n= 0\) for all \(n\geq L\). The basic result of this paper is that the \(q\)-periodic sequence \(\eta_0, \eta_1,\dots\), over \(\mathbb F_q\) passes the \(s\)-dimensional lattice test if and only if \(s< L(\eta_n)\). The authors also give applications of this result to nonlinear and inverse pseudorandom number generators.