Lattice structure and linear complexity profile of nonlinear pseudorandom number generators (Q1396702)

The authors extend a generalized version of Marsaglia's lattice test for sequences over finite fields to segments of sequences over an arbitrary field \(\mathbb{K}\) and give the relation between lattice test and linear complexity profile for such sequences. For given \(s\geq 1\) and \(N\geq 1\) we say that a sequence \((\eta_n)\) over \(\mathbb{K}\) (it is not necessarily periodic) passes the \(s\)-dimensional \(N\)-lattice test if the vectors \(\vec\eta_n- \vec\eta_0\) \((1< n< N-s) \operatorname {span} \mathbb{K}^s\), where \(\vec\eta_n= (\eta_n, \eta_{n+1},\dots, \eta_{n+s-1})\). Let \(L(N)= L((\eta_n),N)\) be the greatest one among such \(s\). Further, the linear complexity profile \(L(N)= L((\eta_n),N)\) is defined by the least order of a linear recurrence relation over \(\mathbb{K}\) satisfied by the first \(N\) terms of \((\eta_n)\). The authors prove that either \(S(N)= \min(L(N), N+1-L(N))\), or \(S(N)= \min(L(N), N+1- L(N))-1\), and so this lattice test and linear complexity profile provide essentially equivalent quality measures for randomness.