On the \(k\)-error linear complexity of \(\ell\)-sequences (Q609360)

Feedback with carry shift register (FCRS) sequences are an important class of nonlinear sequence generators. An FCRS sequence is called an \(l\)-sequence if it has maximal length. The linear complexity of a sequence is an important measure for the quality of the sequence. For applications in cryptography, it is significant that a sequence has a large linear complexity even if a few of its terms are changed. The appropriate notion for such a scenario is \(k\)-error linear complexity. When the sequence is periodic, \(k\)-error linear complexity has been studied in the literature. For a periodic sequence \(\underline{s}\), let \(\text{minerror}(\underline{s})\) denote the minimum number of terms that have to be changed within one period to decrease the linear complexity of \(\underline{s}\). For an \(\ell{s}\)-sequence \(\underline{s}\), its maximal linear complexity is \(\text{per}(\underline{s})/2+1\), where \(\text{per}(\underline{s})\) is the period of \(\underline{s}\). Let \(\underline{s}\) be an \(\ell\)-sequence of maximal length. In this interesting paper the authors obtain tight lower and upper bounds for \(\text{minerror}(\underline{s})\). They also obtain some further results for \(\ell\)-sequences based on strong 2-prime numbers.