Research On 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 stream cipher is one of the important branches of modern cryptography. The development of feedback shift register theory, together with the effective mathematical tools, has brought great progress of stream cipher theory. Therefore, as the important indexes of stream ciphers, linear complexity and k-error linear complexity have drawn more and more attention. The core idea of stream ciphers is how to use the shortest series of feedback shift register, to generate the needed key sequences or generate the approximate sequences of the needed key sequences. This dissertation mainly studies important measure indexes of stream ciphers which are based on feedback shift register, such as linear complexity, k-error linear complexity and m-tight error linear complexity. The main results are the following several respects:1. Based on the earlier notions of linear complexity, k-error linear complexity, k-error linear complexity profile and minerror, the concept of m-tight error linear complexity is presented to study the stability of the linear complexity of sequences. The m-tight error linear complexity of sequence S is defined as a two tuple (km, LCm), which is the mth jump point of the k-error linear complexity profile of sequence S.2. Based on the algorithm for determining the k-error linear complexity of a binary sequence with period 2n, the algorithm for determing the tight error linear complexity of it is presented. The main idea is calculating 0 error linear complexity at the beganing, and demanding k-error linear complexity at the same time, computing the smallest bits of original sequence Tmin when cancel this addition of linear complexity before every addition of linear complexity for the algorithm of linear complexity, and reduce the linear complexity of sequences through change the value of k.3. Based on the algorithm for determining the k-error linear complexity of a binary sequence with period pn, the algorithm for determing the tight error linear complexity of it is presented. And the main idea is like 2. 4. Based on the algorithm for determining the linear complexity of a binary sequence with period 2npm, the algorithm for determing the tight error linear complexity of it is presented. Since that Wei-Xiao-Chen algorithm can not be generalized to the algorithm of k-error linear compliexity like Games-Chan algorithm, so the main idea is different from above.The main idea is:before every addition of linear complexity for the algorithm of linear complexity, computing the smallest bits of original sequence Tmin that can cancel this addition of linear complexity. To the value of smaller and nonzero among Tmin, change Tmin bits from small to big of original sequences (that is stack a nonzero element with Tmin vectors), then l-error linear complexity may obtained. For m>1, we take one or more values of the smaller and nonzero values among Tmin, change the original sequence from small to big to cancel addition of corresponding positions of linear complexity, then we get m-tight error linear complexity. IV...