Research On The Complexities Of Several Classes Of Sequence Families

As a sequence generator whose outputs are natural nonlinear sequences, a feedback with carry shift register(FCSR) is designed by introducing an auxiliary memory, which is the device resulting in the nonlinearity of outputs, into a trad itional linear feedback shift register(LFSR). Since A. K lapper and M. Goresky proposed FCSRs more than twenty years ago, researches on FCSR sequences, especially on maximal length FCSR sequences(l-sequences), 2-adic complexity of sequences and designs of stream ciphers based on FCSRs have received remarkable effects. However, several significant problems, such as the relationship between 2-adic complexity and linear complexity, still remain unsolved.This thesis studies the complexities, mainly 2-adic complexity and nonlinear complexity, of several classes of sequence sets, and the main results are listed below:1. For the LFSR sequence family generated by an irreducible polynomial, the minimal connection integer and the 2-adic complexity are properly de fined, and both of them are proved to attain the maximum. Furthermore, the symmetric 2-adic complexity of the LFSR sequence family is parallel defined, and the conclusion that it attains the maximum also holds. Thus a further understanding of the relationship between 2-adic complexity and linear complexity is presented.2. By treating an FCSR as a nonlinear feedback shift register(NFSR) in Galois configuration, the nonlinear complexity of a unique set of output sequences of the FCSR is given. From this new perspective, the nonlinear complexity of the FCSR periodic sequence families as well as l-sequences can be easily derived, and the relationship between 2-adic complexity and nonlinear complexity, together with the relationship between 2-adic span and nonlinear complexity, is further discussed.