@article{Lin2026, 
author = {Hezheng Lin and Lingmei Xiao and Zhixiong Chen},
title = {A brief view on the linear and 2-adic complexities of pseudorandom binary sequences},
year = {2026},
journal = {AIMS Mathematics},
volume = {11},
number = {7},
pages = {20267-20290},
keywords = {stream cipher, binary sequence, linear complexity, 2-adic complexity},
url = {https://www.sciopen.com/article/10.3934/math.2026823},
doi = {10.3934/math.2026823},
abstract = {In this survey, we review pseudorandom binary sequences generated by linear feedback shift registers (LFSRs) and feedback with carry shift registers (FCSRs), respectively. A natural question is how to determine the size of a register (LFSR or FCSR) that generates a given sequence. It can be transferred mathematically in terms of the theory of formal power series for LFSRs and of    2-adic integers for FCSRs, respectively. Hence, the linear complexity (resp.    2-adic complexity) of an eventually periodic sequence is determined by its rational formal power series (resp. rational    2-adic integer). The    Nth linear complexity (resp.    Nth    2-adic complexity) of a sequence of length    N is the minimal linear complexity (resp.    2-adic complexity) of all eventually periodic sequences which start with the    N-length sequence. We present results on the average and asymptotic behavior of finite length and periodic sequences. We also present bounds on the    Nth linear complexity (resp.    Nth    2-adic complexity) for algebraic sequences which are non-eventually periodic. Our primary goal is to assist cryptographic novices in gaining a better understanding and mastery of the design and analysis of shift register sequences.}
}