Ana Salagean (Loughborough):<br>
"On the computation of the linear complexity and the $k$-error linear
complexity of
binary sequences with period a power of two".<br>
<br>
Abstract:<br>
<br>
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.