Linear complexity of binary generalized cyclotomic sequences over GF(q)

Periodic sequences over finite fields have been used as key streams in private-key cryptosystems since the 1950s. Such periodic sequences should have a series of cryptographic properties in order to resist many attack methods. The binary generalized cyclotomic periodic sequences, constructed by the cyclotomic classes over finite fields, have good pseudo-random properties and correlation properties. In this paper, the linear complexity and minimal polynomials of some generalized cyclotomic sequences over GF(q) have been determined where q=pm and p is an odd prime. Results show that these sequences have high linear complexity over GF(q) for a large part of odd prime power q, which means they can resist the linear attack method.