Research Of Linear Complexity And K-error Linear Complexity Of Periodic Sequences

How to evaluate the stability of stream cipher is an important issue in the research of stream cipher, which is an important part of cryptography. The linear complexity becomes an important standard to evaluate the stability of stream cipher since Massey provided the B-M algorithm in1969. However, a sequence of large linear complexity may not be secure enough, so another standard is proposed by Stamp and Martin, which is called k-error linear complexity. Since then, the linear complexity and k-error linear complexity become two important indicators to measure the stability of stream cipher. For a2n-period binary sequence, Chan and Games gives a fast algorithm of the linear complexity, as well as Stamp and Martin gives an algorithm of the k-error linear complexity, which set off a upsurge of the research on algorithms. In recent years, the theoretical study of multi-sequences is more and more concerned by scholars.In this thesis, we mainly study the k-error linear complexity of2"-period binary sequences, Matlab programming of algorithms, the minimal polynomial and joint linear complexity of multi-sequences. The details are given as follows:1. For2n-period binary sequences of linear complexity2n-2m-1, we get all possible values of4-error (or5-error) linear complexity:LC4(s)=0,2n-2m-2r+1+c or2n-2r+1+c, and the number of sequences with LC4(s)=0and LC4(s)=2n2m-2r+1+c.2. For a2n-period binary sequence, we discuss classic algorithms of linear complexity and k-error linear complexity as well as their Matlab program.3. We study the algorithm for the numbers of2n-period binary sequences of a given linear complexity, and give its Matlab program which is then used to get the sequences satisfying the condition.4. Based on the conclusion of a new sequence combined by a sequence s and its dual sequences, we discuss the minimal polynomial and joint linear complexity of multi-sequences which consist of a number of the new sequences.