Loading web-font TeX/Math/Italic
An approximation algorithm for computing the k-error linear complexity of sequences using the discrete fourier transform | IEEE Conference Publication | IEEE Xplore

An approximation algorithm for computing the k-error linear complexity of sequences using the discrete fourier transform


Abstract:

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 t...Show More

Abstract:

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(N2) 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.
Date of Conference: 06-11 July 2008
Date Added to IEEE Xplore: 08 August 2008
ISBN Information:

ISSN Information:

Conference Location: Toronto, ON, Canada

I. Introduction

The linear complexity of a sequence of terms over a field is defined as the length of the smallest linear recurrence relation which generates that sequence. The -error linear complexity of a periodic sequence is a natural generalisation of the notion of linear complexity and it represents the length of the smallest linear recurrence relation which generates a sequence which differs from the original in at most positions in each period.

References

References is not available for this document.