burrage2.pdf (214.12 kB)
Download fileLinear complexity for sequences with characteristic polynomial fv
conference contribution
posted on 2012-03-16, 16:26 authored 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