The asymptotic behavior of the joint linear complexity profile of multisequences (Q877184)

The \(n\)th joint linear complexity \(L_n^{(m)}(\mathbb{S})\) of an \(m\)-fold multisequence \(\mathbb{S}\) (\(m\) parallel sequences) over a finite field \(\mathbb F_q\) is the length of the shortest linear recurrence relation the first \(n\) terms of each of the \(m\) sequences satisfy. The present paper refines results of the authors' earlier paper [INDOCRYPT 2005, Lect. Notes Comput. Sci. 3797, 13--22 (2005; Zbl 1153.94338)], where it was shown that \(\lim_{n\rightarrow\infty}L_n^{(m)}(\mathbb{S})/n = m/(m+1)\), \(\mu_{q,m}^\infty\)-almost everywhere, where \(\mu_{q,m}^\infty\) denotes the Haar measure on the sequence space \((\mathbb F_q^m)^\infty\) over \(\mathbb F_q^m\). Before, this was only known to be true for \(m = 1,2\). As major results of the present work the authors show that \(L_n^{(m)}(\mathbb{S}) = mn/(m+1) + O(\log n)\) as \(n \rightarrow \infty\), and that \(E_n^{(m)} = mn/(m+1) + o(n)\) as \(n \rightarrow \infty\), where \(E_n^{(m)}\) denotes the expected value for the \(n\)th joint linear complexity of a random \(m\)-fold multisequence. Finally the authors show that \(E_n^{(3)} = 3n/4 + O(1)\) as \(n \rightarrow \infty\), which extends the well known corresponding result for \(m = 1\) and the recently proved result for \(m=2\), \(q=2\) in \textit{X. T. Feng} and \textit{Z. D. Dai} [SETA 2004, Lect. Notes Comput. Sci. 3486, 113--128 (2004; Zbl 1145.94416)], and \(m=2\) and arbitrary \(q\) in the authors' paper [Finite Fields Appl. 12, No. 4, 613--637 (2006; Zbl 1156.94328)]. Based on this observations the authors conjecture that \(E_n^{(m)} = 3n/4 + O(1)\) as \(n \rightarrow \infty\) holds for any integer \(m \geq 1\). The present paper is a valuable contribution to the theory of joint linear complexity, in which dramatic progress has been achieved in the last few years, motivated by the increased activity in the design of word-based stream ciphers. A comprehensive overview of this progress is given in \textit{H. Niederreiter} [SETA 2006, Lect. Notes Comput. Sci. 4086, 5--16 (2006; Zbl 1152.94392)].