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

Stream cipher is an important part of cryptography.More and more works focus on the problem how to evaluate the pseudorandom sequences.With the study of stream cipher,especially by the end of 1960,the B-M complicated algorithm,which is reported by Berlekamp-Massey,made the linear complexity become the important standard of stream cipher .If the linear complexity of one sequence is L,and 2L continuous bits of this sequence were known ,we can find the whole sequence,by use of B-M algorithm.So the linear complexity of sequence must be large enough.But a sequence with large linear complexity must not be a safe stream cipher.Under these,the safty standard of linear complexity was reported by Stamp and Martin,this is k-error linear complexity.Now linear complexity and k-error linear complexity become two important standard to estimate the pseudorandom properties.Because the sepacial relation between periodic sequences and its bit-wise negative sequences,under the old correlative results over F₂ ,the relation of minimum generate polynomials and linear complexity between sequences and its bit-wise negative sequences over F_P has been discussed in this dissertation firstly;secondly,the k-error(k=4,5)linear complexity of 2n ? periodic binary sequences with linear complexity of 2ⁿ- 1 has been discussed by use of Games-Chan algorithm,and the expected value of those 2ⁿ - periodic binary sequences given k-error linear complexity were provided.In the end,on base of the new definition of generalized bit-wise negative periodic multi-sequences,the relation between periodic multi-sequences and its generalized bit-wise negative periodic multi-sequences has been discussed over F₂ and F_P respectively.