"On the computation of the linear complexity and the $k$-error linear complexity of binary sequences with period a power of two".

Abstract:

The linear complexity of a sequence (i.e. the length of the shortest recurrence relation, or Linear Feedback Shift Register which generates the sequence) is a fundamental parameter for virtually all applications of linearly recurrent sequences, including cryptography. Computing the linear complexity of a linearly recurrent sequence takes in general quadratic time, using the Berlekamp-Massey algorithm. For binary sequences whose period N is a power of two, Games and Chan developed a more efficient, linear algorithm. For such sequences, the k-error linear complexity (i.e. the minimum complexity that can be obtained by changing up to k terms in a period) can also be computed in linear time and space using the Stamp-Martin algorithm. The whole k-error linear complexity spectrum can be computed in O(N log^2 N) by the Lauder-Paterson algorithm. In our talk we will first show that one can use the Games-Chan, Stamp-Martin and Lauder-Paterson algorithms to compute the analogue notions of linear complexity and k-error linear complexity for finite sequences. Secondly, using ideas from the Stamp-Martin and Lauder-Paterson algorithms we develop a new algorithm which computes the minimum number of errors needed to bring the linear complexity of a sequence below a given value. This algorithm has linear (bit) time and space complexity and can also be used for encoding and decoding certain binary repeated-root codes. We improve thus on a previous O(N log^2 N) decoding algorithm of Lauder and Paterson.