Maximum-Order Complexity and 2-Adic Complexity
Zhiru Chen, Zhixiong Chen, Jakob Obrovsky, Arne Winterhof · IEEE Transactions on Information Theory · 2024
The 2-adic complexity has been well-analyzed in the periodic case. However, we are not aware of any theoretical results in the aperiodic case. In particular, theNth 2-adic complexity has not been studied for any promising candidate of a pseudorandom sequence of finite lengthN. Also nothing seems be known for a part of the period of lengthNof any cryptographically interesting periodic sequence. Here we introduce the first method for this aperiodic case. More precisely, we study the relation betweenNth maximum-order complexity andNth 2-adic complexity of binary sequences and prove a lower bound on theNth 2-adic complexity in terms of theNth maximum-order complexity. Then any known lower bound on theNth maximum-order complexity implies a lower bound on theNth 2-adic complexity of the same order of magnitude. In the periodic case, one can prove a slightly better result. The latter bound is sharp, which is illustrated by the maximum-order complexity of ℓ-sequences. The idea of the proof helps us to characterize the maximum-order complexity of periodic sequences in terms of the unique rational number defined by the sequence. We also show that a periodic sequence of maximal maximum-order complexity must be also of maximal 2-adic complexity.