Abstract: A fast algorithm is presented for determining the linear complexity and the minimal polynomial of sequences over GF(p^m) with the period kn, where p is a prime, gcd(n, p^m-1)=1, p^m-1=kt, and n, k and t are integers. The algorithm presented here covers the algorithm proposed by Chen Hao for determining the linear complexity of sequences over GF(p^m) with the period 3n, where p is a prime, gcd(n, p^m-1)=1, p-1=3t, and n and t are integers. Combining the proposed algorithm with some known algorithms, the linear complexity of sequences over GF(p^m) with the period kn can be determined more efficiently. Finally, an example for applying this algorithm is presented.

Key words: cryptography, periodic sequence, linear complexity, minimal polynomial, fast algorithm