Research On The Linear Complexity And K-Error Linear Complexity Of Period Sequences

Periodic pseudo-random sequences are widely used in stream ciphers,spread spectrum communication,radar ranging and other fields.Linear complexity and k-error linear complexity are important criterions for measuring the security of pseudo-random sequences of stream ciphers.This thesis focuses on the linear complexity and k-error linear complexity of several periodic sequences,including the k-error linear complexity spectrum of long periodic with 2~n sequences,the number of sequences with k-error linear complexity drop point of a certain relationship,as well as construction of binary generalized circular sequences with high linear complexity and high k-error linear complexity.The main results are as follows:(1)An improved Stamp-Martin algorithm is proposed for k-error linear complexity of periodic sequences.Firstly,the new algorithm replaces one-dimension?[i]structure in Stamp-Martin algorithm with two-dimension?[i,h]to achieve the minimum k-error linear complexity.Secondly,the position of the subsequent drop point is determined by adding variables dop.Finally,the k-error linear complexity spectrum of a specific periodic sequence is obtained according to the new algorithm.(2)Based on the Games-Chan algorithm,the drop point of the k-error linear complexity of the binary sequence with period of 2~n is studied utilizing the standard cube decomposition method and the screening method.Firstly,for sequences with first drop point 4 and the second drop point 12,the relationship between the two drop points is obtained,and then all possible value of 12-error linear complexity are gived.Secondly,when the first drop point is 2,the second drop point is 6,and the third drop point is 8,the relationship and the count between these three drop points of a periodic sequence is obtained.(3)A class of binary generalized cyclotmic sequences with high linear complexity are constructed.Based on Ding's generalized cyclotmic theory,a orderly binary generalied cyclotomic sequence of order with q period 2p~m are constructed,the value of linear complexity and the upper bound of the k-error linear complexity of the new sequence are calculated by cyclotmic method.