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

Stream cipher is an important part of cryptography. The intensity of cipher system has been studied by cipher designers and analyzers and has become the key problem since cipher theory and technology emerged. More and more works focus on the problem how to evaluate the pseudorandom sequences.With the study of pseudorandom sequences, especially by the end of 1960s,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 arbitrary continuous bits of this sequence were known, we can find the whole sequence by using B-M algorithm. So the linear complexity of sequence must be large enough. But a sequence with large linear complexity is not a necessarily safe stream cipher.Under these, the safty standard of linear complexity was reported by Stamp and Martin, that is k-error linear complexity. Now linear complexity and k-error linear complexity become two important standards to estimate the pseudorandom properties.This paper mainly studies linear complexity, k-error linear complexity, the number of sequences with given k-error linear complexity, the expected k-error linear complexity which based on periodic sequence and so on. Specific studies are as follows:1. This paper presented the relation between f_s(x) and f_s(x)over field F₂ ,in which f_s(x) and f_s(x) are the minimum polynomials of periodic sequences S∞and sequences S-∞respectively, The relation presented can be used to analyze the complexity of periodic sequences of stream ciphers over F₂ .2. This paper presented the relation between f_s(x) and f_s(x) over field FP ,in which f_s(x) and f_s(x) are the minimum polynomials of periodic sequences S∞and sequences S-∞respectively, The relation presented can be used to analyze the complexity of periodic sequences of stream ciphers over FP .3. In F₂ , it discusses the 2n - periodic binary sequence with linear complexity 2 n - 1,The number of sequences with given k-error linear complexity and the expected k-error linear complexity are provided. (k = 6,7).4. In F₂ , it discusses the 2n - periodic binary sequence with linear complexity 2ⁿ - 2^m- 1,The number of sequences with given k-error linear complexity and the expected k-error linear complexity are provided. (k = 1,2).5. In F_P , it explores the Pⁿ- periodic P-ary sequence with linear complexity Pⁿ - P^m- 1,The number of sequences with given k-error linear complexity and the expected k-error linear complexity are provided. (k = 1,2).