Error Decomposition Algorithm for Approximating the k-Error Linear Complexity of Periodic Sequences

In cryptography applications, pseudorandom sequences should have large linear complexity and k-error linear complexity, so that they cannot be recovered by only knowing a small amount of consecutive terms. However, general efficient algorithms do not exist for computing the exact value of k-error linear complexity. Therefore, it is useful to compute a good upper bound of the k-error linear complexity. First we develop an efficient exhaustive search algorithm for k-weight complexity when k is small by using Blahut's theorem and the cyclotomic structure of the discrete Fourier transform (DFT) of periodic sequences. Then we give an approximation algorithm by decomposing the total k errors into errors of smaller weight at different stages. Theoretical analysis show that the complexity of our algorithm is scalable with the dominant factor, decomposition depth. Experiments show that our algorithm has a better approximation of the k-error linear complexity than other approximation algorithms in most cases, and the simulated time complexity matches well with our theoretical result.