burrage2.pdf (214.12 kB)

# Linear 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

## Citation

BURRAGE, A.J., SALAGEAN, A.M. and PHAN, R.C.-W., 2011. Linear complexity for sequences with characteristic polynomial fv. IN: IEEE International Symposium on Information Theory Proceedings, (ISIT), St. Petersburg, Russia, July 31 - Aug 5th., pp. 688 - 692## Publisher

© IEEE## Version

- NA (Not Applicable or Unknown)

## Publication date

2011## Notes

Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.## ISBN

9781457705946;9781457705960## ISSN

2157-8095## Publisher version

## Language

- en