Researches On The K-Error Linear Complexity Of Some Periodic Sequences

Linear complexity and k-error linear complexity are important measures for assessing the pseudorandom properties of sequences. A cryptographically strong sequence should not only have a large linear complexity, but also alerting a few terms in a period should not cause a significant decrease of the linear complexity. Based on this, in the early 1990's, C. Ding and M. Stamp etc. independently proposed the stability theory of sequences and the conception of k-error linear complexity. For the past two decades, plentiful results have been obtained about this problem. In this paper, we further study the k-error linear complexity of some periodic sequences over finite fields. The main results are as follows:1. For qmpn-periodic sequences over Fq, where p is an odd prime and q is a primitive root modulo p~2, we present the upper and lower bounds on the minimal value of k such that the k-error linear complexity is strictly less than the linear complexity, which is the so-called the first decreasing point denoted by m(s). When qm < p - 1, the upper and lower bounds of m(s) are estimated, which are related to the p-adic expression of the linear complexity. It shows some internal relationship between the linear complexity and its stability. When q~m≥p - 1, the bounds of m(s) are estimated based on the decomposition of the generation function of sequences.2. The distribution of the 1-error linear complexity of 2pm-periodic binary sequences is studied, where p is an odd prime and p > 3, 2 is a primitive root modulo p2. We give all the possible values of the 1-error linear complexity and the number of sequences with given 1-error linear complexity.3. For 2n-periodic binary sequences with m(s) = 4, the distribution of the 4-error linear complexity is discussed. The all possible values of the 4-error linear complexity and the number of sequences with given 4-error linear complexity are established. Moreover, the expected value of the 4-error linear complexity of 2n-periodic binary sequences with m(s) = 4 is also given.