Title: The 2-adic complexity of a class of binary sequences with almost optimal autocorrelation,
Abstract: Pseudo-random sequences with good statistical property, such as low
autocorrelation, high linear complexity and large 2-adic complexity, have been
applied in stream cipher. In general, it is difficult to give both the linear
complexity and 2-adic complexity of a periodic binary sequence. Cai and Ding
\cite{Cai Ying} gave a class of sequences with almost optimal autocorrelation
by constructing almost difference sets. Wang \cite{Wang Qi} proved that one
type of those sequences by Cai and Ding has large linear complexity. Sun et al.
\cite{Sun Yuhua} showed that another type of sequences by Cai and Ding has also
large linear complexity. Additionally, Sun et al. also generalized the
construction by Cai and Ding using $d$-form function with difference-balanced
property. In this paper, we first give the detailed autocorrelation
distribution of the sequences was generalized from Cai and Ding \cite{Cai Ying}
by Sun et al. \cite{Sun Yuhua}. Then, inspired by the method of Hu \cite{Hu
Honggang}, we analyse their 2-adic complexity and give a lower bound on the
2-adic complexity of these sequences. Our result show that the 2-adic
complexity of these sequences is at least $N-\mathrm{log}_2\sqrt{N+1}$ and that
it reach $N-1$ in many cases, which are large enough to resist the rational
approximation algorithm (RAA) for feedback with carry shift registers (FCSRs).