The expectation and variance of the joint linear complexity of random periodic multisequences (Q2577529): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.jco.2005.07.001 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2034704828 / rank | |||
Normal rank |
Revision as of 01:55, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The expectation and variance of the joint linear complexity of random periodic multisequences |
scientific article |
Statements
The expectation and variance of the joint linear complexity of random periodic multisequences (English)
0 references
22 December 2005
0 references
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.
0 references
multisequences
0 references
joint linear complexity
0 references
stream ciphers
0 references
expectation
0 references
variance
0 references
generalized discrete Fourier transform
0 references