Research On K-Error Linear Complexity Of Periodic Sequences

With the rapid development and wide application of information and network, more and more information has been transmitted through the network. Meanwhile, because of the openness and sharing of computer networks, information security has gained more and more concerns. The theory and technology of cryptography has become one of the most important research fields of information science and technology. It should be said that, the more information and its advanced commercialization, the more important information security and the more extensive application of cryptography. The keystream strength is one of the important branches of modern cryptography, hence designing a sequence which possesses high linear complexity and k-error linear complexity is a hot topic in cryptography and communication. Niederreiter first noticed many periodic sequences with high k-error linear complexity over the finite field Fq. In this paper, the concept of stable κ-error linear complexity is presented to study sequences with high κ-error linear complexity. By studying linear complexity of binary sequences with period2n, the method using cube theory to construct sequences with maximum stable κ-error linear complexity is presented, and many examples are given to illustrate the approach. It is proved that a binary sequence with period N=2n can be decomposed into some disjoint cubes. The cube theory is a new direction for studying k-error linear complexity.Then by studying linear complexity of binary sequences with period2n, it is proposed that the computation of k-error linear complexity should be converted to finding error sequences with minimal Hamming weight. Based on Games-Chan algorithm,4-error linear complexity distribution of2n-periodic binary sequences with linear complexity2n-lis discussed. In most cases, the complete counting functions on the4-error linear complexity of2n-periodic binary sequences are presented. Meanwhile, the counting functions are verified by computer programming for n=3, n=4, n=5. Then the complete counting functions on the16-error linear complexity of2n-periodic binary sequences with linear complexity2n-15are presented.