Linear complexity for sequences with characteristic polynomial v

Alex J. Burrage, Ana Sǎlǎgean, Raphael C.W. Phan

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

2 Citations (Scopus)


We present several generalisations of the Games-Chan algorithm. For a fixed monic irreducible polynomial we consider the sequences s that have as characteristic polynomial a power of . 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.

Original languageEnglish
Title of host publication2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Number of pages5
Publication statusPublished - 2011
Externally publishedYes
EventIEEE International Symposium on Information Theory 2011 - St. Petersburg, Russian Federation
Duration: 31 Jul 20115 Aug 2011 (Proceedings)

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8104


ConferenceIEEE International Symposium on Information Theory 2011
Abbreviated titleISIT 2011
Country/TerritoryRussian Federation
CitySt. Petersburg
Internet address

Cite this