TY - JOUR

T1 - Computing the linear complexity for sequences with characteristic polynomial fv

AU - Sǎlǎgean, Ana

AU - Burrage, Alex J.

AU - Phan, Raphael C.W.

N1 - Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2013/6

Y1 - 2013/6

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

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

KW - Games-Chan algorithm

KW - Linear complexity

KW - Linear recurrent sequences

UR - http://www.scopus.com/inward/record.url?scp=84874807559&partnerID=8YFLogxK

U2 - 10.1007/s12095-013-0080-3

DO - 10.1007/s12095-013-0080-3

M3 - Article

AN - SCOPUS:84874807559

SN - 1936-2447

VL - 5

SP - 163

EP - 177

JO - Cryptography and Communications: Discrete Structures, Boolean Functions and Sequences

JF - Cryptography and Communications: Discrete Structures, Boolean Functions and Sequences

IS - 2

ER -