The expectation and variance of the joint linear complexity of random periodic multisequences (Q2577529)

The linear complexity of a periodic sequence, i.e. the length of the shortest linear recurrence relation which can generate the sequence, and the joint linear complexity of \(t\) parallel periodic sequences (\(t\)-fold multisequence), i.e. the length of the shortest linear recurrence relation which can generate the \(t\) sequences simultaneously, are important security measures for (vectorized) stream ciphers. In \textit{W. Meidl} and \textit{H. Niederreiter} [J. Complexity 19, No. 1, 61--72 (2003; Zbl 1026.68067)] a generalized discrete Fourier transform has been used to express the exact expected value of the joint linear complexity of random \(N\)-periodic multisequences explicitely in terms of cardinalites of certain cyclotomic cosets. With this result significant lower bounds on this expected value have been obtained. In this article the authors derive several new bounds on the expectation of the joint linear complexity of random \(N\)-periodic multisequences, which improve the known lower bounds. Using generalized discrete Fourier transform the authors obtain a general expression for the variance of the joint linear complexity of random \(N\)-periodic multisequences, again in terms of cardinalities of certain cyclotomic cosets, and a general upper bound on the variance. The results generalize the results of \textit{Z. D. Dai} and \textit{J. H. Yang} [Lect. Notes Comput. Sci. 547, 168--175 (1991; Zbl 0766.94003)] for the variance of the linear complexity for single random periodic sequences. Finally, closed formulas for the variance of the joint linear complexity of random \(N\)-periodic multisequences are presented for several classes of periods.