In this paper, a new method is presented to compute the 2-adic complexity of pseudo-random sequences. With this method, the 2-adic complexities of all the known sequences with ideal 2-level autocorrelation are determined in a unified way. Results show that their 2-adic complexities equal their periods. In other words, their 2-adic complexities attain the maximum. In addition, 2-adic complexities of two classes of optimal autocorrelation sequences with period N ≡ 1mod4, namely Legendre sequences and Ding-Helleseth-Lam sequences, are investigated. This method also can be used to compute the linear complexity of binary sequences regarded as sequences over other finite fields.

In this study, the minimal polynomials and the linear complexity of interleaved binary sequences are investigated. Both the linear complexity and the minimal polynomials of low correlation zone sequences constructed by Zhou et al. are completely determined. Besides, an open problem proposed by Li and Tang is discussed. At last, a sufficient condition and a necessary condition are presented about when the linear complexity of the interleaved sequences constructed by Tang et al. attains the maximum.

In this study, the authors propose a new concept named similar-bent function and the authors present two general methods to construct balanced sequences with low correlation by using similar-bent functions and orthogonal similar-bent functions. The authors find that the bent sequence sets are special cases of our construction. The authors also investigate the linear complexity of the new constructed sequences. If a suitable similar-bent function is given, the sequences constructed by it can have high-linear complexity. As examples, the authors construct two new low-correlation sequence sets. One constructed based on Dobbertin's iterative function is asymptotically optimal with respect to the Welch bound and the other one is constructed based on Kasami function whose sequences have a high-linear complexity.