Minimal Polynomials And Linear Complexity Of Periodic Sequences

The stream cipher, which belongs to symmetric key, is one of the important branches of modern cryptography. Because of its simple realizing, quick encryption and decryption, the stream cipher always keeps strong superiority in real application. Period and linear complexity are of great importance as measure indexes on the security of stream ciphers. This dissertation mainly studies minimal polynomials and linear complexity of periodic sequences. The main results are as follows:After reading some fast algorithms for determining the linear complexity of periodic sequences, the author presented a fast algorithm to determine the minimal polynomial and the linear complexity of a binary sequence with period u2~tp~n, where p is an odd prime and 2 is a primitive root modulo p~2. Let m be the order of 2 modulo u . The conditions gcd ( m, p ( p- 1) )= 1 and gcd ( p ,2~m- 1) = 1 are also required. In the fast algorithm, the computation of the minimal polynomial of a sequence with period u2~tp~n over GF (2) is reduced to the product of minimal polynomials of u sequences with period 2t p~n over GF (2~m). Accordingly, the computation of the linear complexity is reduced to the sum of linear complexity of u sequences with period 2t p~n over GF (2~m).Then the author presented the relation between the linear complexity of s and the linear complexity of its bit-wise negative sequence with the help of the Xiao-Wei-Lam-Imamura algorithm and the analysis of linear complexity of periodic sequences and its bit-wise negative sequences by others, where s is a binary sequence with period p n, p is an odd prime and 2 is a primitive root modulo p~2. Finally, with the help of the generalized Games-Chan algorithm, the author presented the relation between the minimal polynomial and the linear complexity of s and the minimal polynomial and the linear complexity of its bit-wise negative sequence, where s is a sequence with period p~n over GF ( p). And the author proved a result that the linear complexity of s is the same as that of its bit-wise negative sequence if s≠( p- 1, p -1,…, p-1,…), where s is a non-zero sequence with period p~n over GF ( p ).The main results in this dissertation can be used to the analysis and design of stream ciphers.