Research On Counting And Characterization Of Periodic Sequences With K-Error Linear Complexity

The theory and technology of cryptography is becoming one of the most important researchfields of information science and technology. It should be said that, the higher the degree ofinformation society, the more developed business, information security becomes more important,and there are more extensive cryptography applications. The intensity of cipher system has beenstudied by cipher designer and analyzers and has become the key problem since cipher theory andtechnology emerged. Stream cipher is one of the important branches of modern cryptography, moreand more works focus on how to evaluate pseudorandom sequences. The linear complexity is animportant measurement of pseudorandom sequences. However, a sequence with large linearcomplexity is not a necessarily safe stream cipher, thus the safe measurement of k-error linearcomplexity was proposed by Stamp and Martin. Designing a sequence with high linear complexityand k-error linear complexity is a hot topic in cryptography and communications. Niederreiter firstnoticed many periodic sequences with high k-error linear complexity over the finite field Fq, andproposed the concept of stable k-error linear complexity to study sequences with high k-error linearcomplexity.Based on Games-Chan algorithm, this paper mainly studies linear complexity、k-error linearcomplexity、the number of sequences with given k-error linear complexity and so on. The mainwork and innovations are as follows:1. By studying linear complexity of binary sequences with period 2n, the method using cubetheory to construct sequences with maximum stable k-error linear complexity is presented, andmany examples are given to illustrate the approach. It is proved that a binary sequence with periodN=2ncan be decomposed into some disjoint cubes. The cube theory is a new direction for studyingk-error linear complexity.2. By studying linear complexity of binary sequences with period 2n, it is proposed that thecomputation of k-error linear complexity should be converted to finding error sequences withminimal Hamming weight. Based on Games-Chan algorithm, 6-error linear complexity distributionof 2n-periodic binary sequences with linear complexity 2n-1is discussed. In most cases, the completecounting functions on the 6-error linear complexity of 2n-periodic binary sequences are presented.Meanwhile, the counting functions are verified by computer programming for n=4 and n=5. As aconsequence of these results, an important error of the thesis of Wang Jun is corrected.3. By Games-Chan algorithm, k-error linear complexity distribution of 2n-periodic binarysequences with linear complexity 2n-m are discussed. When (m,k)=(2,2),(3,4),(4,2),(5,4), (6,4),(7,8),(8,2), the complete counting functions on the k-error linear complexity are presentedrespectively. For general m, the complete counting functions on the k-error linear complexity of2n-periodic binary sequences with linear complexity 2n-m can also be obtained using a similarapproach.