On the k-error linear complexity of l-sequences

AbstractThis paper studies the stability of the linear complexity of l-sequences. Let s̲ be an l-sequence with linear complexity attaining the maximum per(s̲)/2+1. A tight lower bound and an upper bound on minerror(s̲), i.e., the minimal value k for which the k-error linear complexity of s̲ is strictly less than its linear complexity, are given. In particular, for an l-sequence s̲ 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 minerror(s̲) is very close to r, which implies that this kind of l-sequences have very stable linear complexity