burrage2.pdf (214.12 kB)

Download file# Linear complexity for sequences with characteristic polynomial fv

conference contribution

posted on 16.03.2012, 16:26 by Alex J. Burrage, Ana SalageanAna Salagean, Raphael C.-W. PhanWe present several generalisations of the Games-
Chan algorithm. For a fixed monic irreducible polynomial f we
consider the sequences s that have as characteristic polynomial
a power of f. We propose an algorithm for computing the linear
complexity of s given a full (not necessarily minimal) period of
s. We give versions of the algorithm for fields of characteristic 2
and for arbitrary finite characteristic p, the latter generalising an
algorithm of Kaida et al. We also propose an algorithm which
computes the linear complexity given only a finite portion of
s (of length greater than or equal to the linear complexity),
generalising an algorithm of Meidl. All our algorithms have
linear computational complexity. The algorithms for computing
the linear complexity when a full period is known can be further
generalised to sequences for which it is known a priori that the
irreducible factors of the minimal polynomial belong to a given
small set of polynomials.

## History

## School

- Science

## Department

- Computer Science