Remarks on the \(k\)-error linear complexity of \(p^n\)-periodic sequences (Q2383994)

The applicability of sequences over finite fields for cryptographic purposes is closely related to notions of linear complexity and \(k\)-error linear complexity of (periodic) sequences. Previously, the first author found exact formulas for the counting function and the expected value for the \(1\)-error linear complexity of \(2^n\)-periodic binary sequences as well as upper and lower bounds for the expected \(k\)-error linear complexity for such sequences. These results made use of the so called Chan-Games algorithm to determine the (\(k\)-error) linear complexity of a given \(2^n\)-periodic binary sequence. Later generalization of the Chan-Games algorithm to a more sophisticated algorithm made it posible to obtain some results also in a more general case of \(p^n\)-periodic sequences over a finite field \(F_p\), \(p\) prime. In the article exact formulas for the counting function and the expected value for the \(1\)-error linear complexity of \(p^n\)-periodic sequences over a \(F_p\), \(p\) prime are given. The authors also show how the approach can be used to calculate upper and lower bounds for the \(k\)-error linear complexity for such sequences (previously only lower bounds have been known).