The expected value of the joint linear complexity of periodic multisequences

✍ Scribed by Wilfried Meidl; Harald Niederreiter

• Book ID: 104347280
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 153 KB
• Volume: 19
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1016/s0885-064x(02)00009-2

✦ Synopsis

Complexity measures for sequences of elements of a finite field, such as the linear complexity, play an important role in cryptology. Recent developments in stream ciphers point towards an interest in word-based (or vectorized) stream ciphers, which require the study of the complexity of multisequences. We extend a well-known relationship between the linear complexity of an N-periodic sequence and the (generalized) discrete Fourier transform of Ntuples to the case of multisequences. Using the concept of the generalized discrete Fourier transform for multisequences, we compute the expected value of the joint linear complexity of random periodic multisequences, and for some types of period lengths N we determine the number N t N ðcÞ of t N-periodic sequences with given joint linear complexity c: