## Abstract

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 language | English |
---|---|

Title of host publication | 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 |

Pages | 688-692 |

Number of pages | 5 |

DOIs | |

Publication status | Published - 2011 |

Externally published | Yes |

Event | IEEE International Symposium on Information Theory 2011 - St. Petersburg, Russian Federation Duration: 31 Jul 2011 → 5 Aug 2011 https://ieeexplore.ieee.org/xpl/conhome/6026198/proceeding (Proceedings) |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

ISSN (Print) | 2157-8104 |

### Conference

Conference | IEEE International Symposium on Information Theory 2011 |
---|---|

Abbreviated title | ISIT 2011 |

Country/Territory | Russian Federation |

City | St. Petersburg |

Period | 31/07/11 → 5/08/11 |

Internet address |