The Expansion Complexity of Ultimately Periodic Sequences Over Finite Fields
Zhimin Sun, Xiangyong Zeng, Chunlei Li, Yi Zhang, Lin Yi · IEEE Transactions on Information Theory · 2021
The expansion complexity is a new figure of merit for cryptographic sequences. In this paper, we present an explicit formula of the (irreducible) expansion complexity of ultimately periodic sequences over finite fields. We also provide improved upper and lower bounds on the$N$th irreducible expansion complexity when they are not explicitly determined. In addition, for some infinite sequences with given nonlinear complexity, a tighter upper bound of their$N$th expansion complexity is given.