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²) 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.