A Lower Bound on the 2-Adic Complexity of Hall’s Sextic Residue Sequences

Hall’s sextic residue sequences of prime period p with [Formula: see text] have some desirable features of pseudorandomness, such as high linear complexity, two-level periodic autocorrelation, nice aperiodic auto-correlation measure (correlation measure of order k) and in particular the 2-adic complexity for some special p (related to Hall’s difference set). In this study, we prove a lower bound on the 2-adic complexity for all p, which implies that the 2-adic complexity of Hall’s sequences is at least the expected value of the 2-adic complexity of all p-periodic binary sequences. However, numerical analysis leads to the conjecture that Hall’s sequences have maximal 2-adic complexity.