author = {Z. Chen and Z. Chen and J. Obrovsky and A. Winterhof},
title = {{Maximum-order Complexity and 2-Adic Complexity}},
language = {english},
abstract = {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, the Nth 2-adic complexity has not been studied for any promising candidate of a pseudorandom sequence of finite length N. Also nothing seems be known for a part of the period of length N of any cryptographically interesting periodic sequence. Here we introduce the first method for this aperiodic case. More precisely, we study the relation between Nth maximum-order complexity and Nth 2-adic complexity of binary sequences and prove a lower bound on the Nth 2-adic complexity in terms of the Nth maximum-order complexity. Then any known lower bound on the Nth maximum-order complexity implies a lower bound on the Nth 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 ell -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.},
journal = {IEEE Transactions on Information Theory},
volume = {70},
number = {8},
pages = { 6060--6067},
isbn_issn = {ISSN: 0018-9448},
year = {2024},
refereed = {yes},
keywords = {Complexity theory;Polynomials;Random sequences;Cryptography;Surveys;Shift registers;Mathematics;Pseudorandom sequences;maximum-order complexity;2-adic complexity;ℓ-sequences},
length = {8},
url = {https://doi.org/10.1109/TIT.2024.3405946}