A brief view on the linear and 2-adic complexities of pseudorandom binary sequences

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 $N$th linear complexity (resp. $N$th $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 $N$th linear complexity (resp. $N$th $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.