The Pseudo-random Properties Of Generalized Cyclotomic Binary Sequences With Period Pq

Pseudo-random sequences are widely used in communication and cryptography systems.For the application of stream ciphers,the key stream must be unpredictable and random.The linear complexity of the sequence,which is defined as the length of the shortest linear feedback shift register that can generate a given sequence,is one of the most important indexes to measure these properties.Generally speaking,a sequence with large linear complexity(at least half of its period)is considered to be favorable for cryptography to resist the attack of the well-known Berlekamp-Massey algorithm.The autocorrelation of sequences is also an important index to measure the randomness of sequences.A good sequence must have a low autocorrelation value.In this paper,we studied the construction of generalized cyclotomic binary sequences,linear complexity and autocorrelation.The main results of this paper are as follows:(1)We studied all kinds of cyclotomy methods and the constructions of cyclotomic sequences.On the basis of Whiteman's generalized cyclotomy of order 4 and classic cyclotomy of order 2,we constructed a class of generalized cyclotomic binary sequences with period pq,where p and q are two distinct odd primes.The sequences are almost balanced.Our construction can generate a number of sequences as the parameter a is introduced in the characteristic set.(2)The exact value of linear complexity of the constructed sequences is calculated by studying the solutions of their generating polynomial.For all the cases of odd primes p and q,the linear complexity of the sequences is pq-1?Pq-p+1/2?pq-q+1/2 or pq+p+q-3/2 respectively.The result shows that this class of generalized cyclotomic binary sequences is quite good in terms of the linear complexity for most of its values are close to its period.(3)By using the method of isomorphism,the problems on the residual class ring modulo the product of two primes are transformed into the problems on the residual class ring modulo a prime.Then the autocorrelation distribution of the constructed sequences is completely determined when the parameter a in the characteristic set is 2 by using cyclotomic numbers.Theory results and experiment data show that this class of sequences generally has lower autocorrelation value.Especially,when the value of p approaches to q,the out-of-phase autocorrelation of the sequence is very small with respect to its period.