Linear complexity profile of \(m\)-ary pseudorandom sequences with small correlation measure (Q633044): Difference between revisions

In [\textit{N. Brandstätter} and \textit{A. Winterhof}, Period. Math. Hungar. 52, 1--8 (2006; Zbl 1127.11050)] the linear complexity profile of a binary sequence is estimated in terms of the correlation measure of order \(l\) introduced by \textit{C. Mauduit} and \textit{A. Sarközy} in [Acta Arith. 82, 365--377 (1997; Zbl 0886.11048)]. The authors introduce a new correlation measure for sequences over \(\mathbb Z_m = \{0,1,\ldots,m-1\}\), which is applicable also for composite integers \(m\), and present a lower bound for the linear complexity profile over \(\mathbb Z_m\) of an \(m\)-ary sequence in terms of the new correlation measure. If \(m\) is not prime, then this generalization of the binary case is not straightforward. The result is then applied to obtain bounds on the linear complexity profile for sequences of discrete logarithms modulo \(m\), and for quaternary sequences derived from two Legendre sequences.