On the k-error linear complexity of l-sequences

This paper studies the stability of the linear complexity of l-sequences. Let be an l-sequence with linear complexity attaining the maximum . A tight lower bound and an upper bound on , i.e., the minimal value k for which the k-error linear complexity of is strictly less than its linear complexity, are given. In particular, for an l-sequence based on a prime number of the form 2r+1, where r is an odd prime number with primitive root 2, it is shown that is very close to r, which implies that this kind of l-sequences have very stable linear complexity.