Study On Construction And Randomness Of Pseudo-random Sequences

Pseudo-random sequences are widely used in spread-spectrum communications,electronic countermeasures,remote sensing measurements,secure communications,etc.Especially in stream ciphers,the unpredictability of sequence keys and the imitations of one-time ciphers determine their important position in the cipher system.With reasonable parameter setting,stream ciphers can resist quantum computing attack to some extent.Therefore,stream cipher will still play an important role in the future development of cryptography.Constructing pseudo-random sequences with good cryptographic characteristics is the focus of research in stream ciphers.Linear complexity is considered as one of primary security criterion to measure the unpredictability of pseudorandom sequences.In order to resist linear attacks effectively,the linear complexity of pseudo-random sequences usually needs to be more than half of their period.Trace function representation of pseudorandom sequence is an important tool to study sequence structure and cryptographic properties.The linear complexity or the limit of linear complexity of a sequence can be obtained by using the trace function representation of the sequence.Trace functions can also be used in sequence design and hardware design of key generators.In this paper,several classes of pseudorandom sequences are constructed by various methods and the linear complexity and trace function representation of these classes of pseudorandom sequences are studied respectively.Firstly,based on the Ding generalized cyclotomy class proposed by Ding,the binary balanced generalized cyclotomy sequence with period of order 2 is constructed,then the linear complexity and minimal polynomial of this kind of sequence are given.The results show that the linear complexity of the sequence is multi-valued,and in most cases it is more than half of the periodic value,so it has high linear complexity.Using the relation between Legendre sequence and generalized cyclotomy sequence,the trace representation of sequence is obtained.The linear complexity and trace representation of another kind of Ding generalized cyclotomy sequence are given by defining pairs of the sequence.Secondly,based on the inverse Gray mapping,two new kinds of generalized cyclotomy sequences with period pq are constructed on the finite field,and the linear complexity of the two kinds of sequences on the residual class ring Z₄ is calculated by the Fourier spectrum transform.The results show that the linear complexity of these two kinds of sequences is multi-valued,and it is greater than half of the period in most cases,So,they have good linear complexity.Thirdly,a new family of binary sequences derived from polynomial quotients modulo an odd prime p in general case are constructed.Under the condition that 2 is the primitive element of p²,the minimal polynomial and linear complexity of the sequence are presented according to the solution of polynomial decomposition and generated polynomial.The results show that this kind of sequence has high linear complexity.The results are extended to the general case of polynomial quotients with period p^r（10）1,and the sequence of polynomial quotients with period p^r（10）1 is constructed.The linear complexity of the generalized sequence is verified.Finally,a new class of binary sequence derived from Euler quotient of modules pq is constructed.The linear complexity and minimal polynomial of the sequences are investigated under certain conditions.Through the corresponding definition pair,the trace representation of the sequence is determined.Furthermore,the results are generalized to the Euler quotients modulo p^m qⁿ.The linear complexity and trace representation of the generalized binary sequences are obtained.Concrete examples are given to verify the correctness of the general expression of linear complexity and trace representation.The results show that the linear complexity of these two kinds of sequences is much more than half of the period value,and can resist the linear attack of Berlekamp-Massey algorithm,which has certain research value in the field of information security and stream cryptography.