On the Computation of the Linear Complexity of a Sequence over GF(q) with Period qnpm

A fast algorithm is derived for determining the linear complexity and the minimal polynomial of sequences over GF(q) with period qnpm, where p is a prime number, q is a prime number and a primitive root modulo p² . The new algorithm generalizes both the algorithm to compute the linear complexity of sequences over GF(q) with period pm, where p is a prime, q is a prime and a primitive root modulo p², and the algorithm to compute the linear complexity of sequences over GF(2) with period 2ⁿp^m, where p is a prime, and 2 is a primitive root modulo p².