The exact autocorrelation distribution and 2-adic complexity of a class of binary sequences with almost optimal autocorrelation

摘要

AbstractPseudo-random sequences with good statistical properties, such as low autocorrelation, high linear complexity and large 2-adic complexity, have been used in designing reliable stream ciphers. In this paper, we obtain the exact autocorrelation distribution of a class of binary sequences with three-level autocorrelation and analyze the 2-adic complexity of this class of sequences. Our results show that the 2-adic complexity of such a binary sequence with periodNis at least (N+ 1) − log2(N+ 1). We further show that it is maximal for infinitely many cases. This indicates that the 2-adic complexity of this class of sequences is large enough to resist the attack of the rational approximation algorithm (RAA) for feedback with carry shift registers (FCSRs).