Linear Complexity and Related Complexity Measures for Sequences

摘要

We present a survey of recent work on the linear complexity, the linear complexity profile, and the k-error linear complexity of sequences and on the joint linear complexity of multisequences. We also establish a new enumeration theorem on multisequences and state several open problems. The material is of relevance for the assessment of keystreams in stream ciphers.