Research On The Linear Complexity Of Several New Classes Of Generalized Cyclotomic Sequence

Pseudo random sequences are widely used in cryptography and communication systems. The linear complexity of a sequences is defined as the length of the shortest linear shift register which can generate the sequence. In the related applications such as cryptography, pseudo random sequence should possess high linear complexity. By the Berlekamp-Massey algorithm, the linear complexity of a sequence must not be less than the half of its period. This paper mainly studies three classes of generalized cyclotomic sequences. We will describe their constructions and analysis their linear complexities, respectively. The main results are as follows:1. Based on the construction presented in the SETA2010by Liu et al., we define a new class of d-ary generalized cyclotomic sequences and calculate the linear complexity of the sequence. The results show that the new sequences possess the properties of the original construction. Due to the flexibility in the assignment to each cyclotomic classes, much more sequences can be derived from the new construction.2. By generalizing the constructions of the generalized cyclotomic sequence of pe-riod2pq given by Chang et al., we construct a new class of period2pq, where p and q are distinct primes. Furthermore, we determine the linear complexity of the new sequence. The support set of the new generalized cyclotomic sequences can also be defined flexibly.3. By dividing Zpm+1qn+1*in detail, we construct a new class of binary generalized cyclotomic sequences of period pm+1qn+1, where p and q are distinct primes. We also calculate the linear complexity of new sequence. The new sequence is a generalization of the construction in IEEE Trans. on Info. Theory,58(8):5534-5542,2012given by Hu et al.. Compared with the original construction, the new sequence is always balanced.