A Binary Sequence For A Given Cycle 2-adic Complexity,

An architecture of stream ciphers called feedback shift register with carry(FCSR) was presented by Klapper and Goresky in 1994, which is a feedback shift register together with an amount of auxiliary memory. It not only provides an efficient keystream generator but also introduces the concept of the 2-adic complexity of sequences. Similar to the linear complexity, the 2-adic complexity of a sequence is the size of the smallest FCSR that generates the sequence. Up to now, the 2-adic complexity has been taken as another important standard to judge whether a sequence is safe or not.In this paper, we focus on the analysis of the 2-adic complexity of binary sequences with given period. First we provide an analog of the extended Games-Chan algorithm which can yield a tight upper bound for the 2-adic complexity of periodic binary sequences with period 2~mp~n. Compared with the rational approximation algorithm, our algorithm is more simple and efficient. Then we provide a lower bound for the 2-adic complexity of binary sequences with period 2~mp~n.In the end, we discuss the 2-adic complexity of binary sequences with period p1p2, and present an upper bound and a lower bound for the 2-adic complexity of the sequences in five cases.