An Approximation Algorithm for Computing the k-error Linear Complexity of Sequences Using the Discrete Fourier Transform

The k-error linear complexity of a periodic sequence s over a field K and with period N is the minimum linear complexity that s can have after changing at most k of its terms in each period. This concept can be used as a measure of cryptographic strength for sequences. We introduce a generalisation of the notion of k-error linear complexity, which we call the extension field k-error linear complexity, defined as being the k-error linear complexity of s when working in the smallest extension field of K which contains an N-th root of unity, assuming N is not divisible by the characteristic of K. The optimisation problem of finding the extension field k-error linear complexity is firstly transformed to an optimisation problem in the DFT (Discrete Fourier Transform) domain, using Blahut's theorem. We then give an approximation algorithm of polynomial complexity for the problem (O(N-2) operations in the extension field), by restricting the search space to error sequences whose DFT have period up to k. The algorithm was implemented in GAP and the results on a series of sequences are discussed.