The Design And Analysis Of Pseudo-Random Sequences

With the developing of communication and information technology, binary pseudo-random sequences are widely used in communications, cryptography and radar. Hence, interest in studying pseudo-random sequences also has increased. This thesis will focus on the following three topics of pseudo-random sequences, namely construction of pseudo-random sequence sets,2-adic complexity and linear complexity of pseudo-random se-quences, and compression map of sequences over integer residue rings. The results of this thesis are presented as follows:(I) In sequences design, a class of low correlation zone (LCZ) sequence sets and aclass of low correlation sequence sets are constructed.(1) The method of constructing LCZ sequence sets is to modify some bits of ideal two-level autocorrelation sequences. These new LCZ sequence sets are optimal with respect to Tang-Fan-Matsufuji bound. Besides, comparing with the previous con-structions, the LCZ sequence sets presented by us are the first class of LCZ sequence sets which have two flexibly parameters.(2) The idea of constructing low correlation sequence sets is inspired by the design of bent sequence sets. Firstly, a new notation called similar-bent function is pro-posed by generalizing the definition of bent function. Then, based on orthogonal similar-bent functions, a class of low correlation sequence sets are designed. And the sequences therein have a high linear complexity.(II) In security criteria of sequences,2-adic complexity and linear complexity of op-timal autocorrelation sequences and some interleaved sequences are investigated.(1) Firstly, a new method is presented to compute 2-adic complexity of binary sequences. By this method, the 2-adic complexity of all the known ideal two level autocorre-lation sequences is determined. Still by this method, the 2-adic complexity of Leg-endre sequences and Ding-Helleseth-Lam sequences with period N(≡3 mod 4) is determined. This method also can be used to compute the linear complexity of binary sequences over finite fields with odd characteristics.(2) Secondly, the minimal polynomial and the linear complexity of two classes of inter-leaved sequences are investigated. One is the LCZ sequences constructed by Zhou et al. and the other one is the optimal autocorrelation sequences constructed by Tang et al. By using their interleaved structure, the linear complexity of the LCZ sequences can be determined completely. However, the linear complexity of the second class sequences only can be determined under some conditions. But these results also partially answered the open problem proposed by Li and Tang.(3) Results about 2-adic complexity of the aforementioned interleaved sequences are presented. Their 2-adic complexity is completely determined by using their inter-leaved structure.(Ⅲ) In the sequences over integer residue rings, a class of compression maps are studied. Let φ(x0, x1,…xe-1)=g(xe-1)+μ(x0, x1,…,xe-2) be a function from Fpe to Fp. Then φ can induce a compression map from G’(f(x),pe) to Fp∞. In the previous literatures, some people showed that this compression map is injective if f(x) is a strongly primitive polynomial. In this thesis, we show that if deg(g) is an odd integer or g(x)= xk+∑i=0k-2 cixi,then this map is injective even if f(x) is only a primitive polynomial.