On the expected value of the linear complexity and the k-error linear complexity of periodic sequences

摘要

Rueppel (1986) conjectured that periodic binary sequences have expected linear complexity close to the period length N. In this paper, we determine the expected value of the linear complexity of N-periodic sequences explicitly and confirm Rueppel's conjecture for arbitrary finite fields. Cryptographically strong sequences should not only have a large linear complexity, but also the change of a few terms should not cause a significant decrease of the linear complexity. This requirement leads to the concept of the k-error linear complexity of N-periodic sequences. We present a method to establish a lower bound on the expected k-error linear complexity of N-periodic sequences based on the knowledge of the counting function /spl Nscr//sub N/,/sub 0/(c), i.e., the number of N-periodic sequences with given linear complexity c. For some cases, we give explicit formulas for that lower bound and we also determine /spl Nscr//sub N,0/(c).