Pseudorandomness Of The Generalized Self-Shrinking Sequences

This dissertation focuses on the pseudo-random properties of the Generalized Self-Shrinking (GSS) sequences-the stability of the linear complexity, the selection of the linear combining vectors, the security of the GSS sequence generators, designs the algorithms for computing the k-error 2-adic complexity of the 2~n and p~n periodic binary sequences and the algorithm for determining the k-error N-adic complexity of the p~n periodic binary sequences. The author obtains main results as follows:1. A lower bound of the linear complexity of the GSS sequences is presented, and the stability of the GSS sequences is discussed.2. A simple algorithm is proposed for selecting the linear combing vectors G of the GSS sequence generators. The number of the vectors G obtained is large and all of the vectors G can maximize the least period of the GSS sequences.3. The security of the GSS sequence generators is investigated under three cases in which the initial state of the LFSR is unknown, both the initial state of the LFSR and linear combing vector are unknown, and both the initial state and feedback polynomial of the LFSR are unknown.4. The security of the fifth class and the sixth class of the GSS sequence generators is discussed concretely.5. Note the period of the GSS sequences is 2~n, where n is a positive integer. The 2-adic complexity and the k-error 2-adic complexity are mainly investigated for the 2"-periodic sequences. Firstly, the existence of N-periodic sequences, which simultaneously achieve the maximum value of the 2-adic complexity and the k-error 2-adic complexity is established, and the number of the N-periodic sequences of such properties is given. Then two algorithms for computing the k-error 2-adic complexity and an algorithm for computing the k-error N-adic complexity are proposed, by which we can determine the upper bound of the k-error 2-adic complexity of the p~n and 2~n periodic sequence and the upper bound of the k-error N-adic complexity of the p~n periodic sequence respectively.