Research On Linear Complexity Of Two Generalized Circular Sequences

Pseudo random sequences are widely used in cryptography and communication systems. The linear complexity of the sequences is defined as the length of the short-est linear shift register which can generate the sequences. In the related applications such as cryptography, pseudorandom sequences should possess high linear complex-ity. By the Berlekamp-Massey algorithm, the linear complexity of a sequence must be greater than the half of its period. In this paper, we mainly study the design of two classes of generalized cyclotomic sequences, and linear complexities. The main results are as follows:Based on the theory of generalized cyclotomic, a new class of binary generalized cyclotomic sequence of order four with periodis 2p₂ established. Using the theory of polynomial factor over finite field, we determined the linear complexity and minimal polynomial of the new sequence.Combined the theory of Gray mapping and cyclotomic, a new class of sequence over Z₄ with pq periodis established. We will determine the corresponding Fourier spectral sequence of the new sequence on the finite field of F₄ ?r? 5 prime?. Then, we will obtain the linear complexity of the new sequence from the weights of it is Fourier spectral sequence.Results show that the sequences have larger linear complexity and can resist the attack by B-M algorithm. They are good sequences from the viewpoint of cryptography.