Research On Distribution Of The κ-error Linear Complexity

Pseudorandom sequences are widely used in cryptography, communication and computation, etc. It is an important issue that how to evaluate the pseudorandom sequences.S.W.Golomb considered the good pseudorandom sequences should satisfy:the balanceable distribution of elements,fine runs properties and the ideal auto correlation besides long period and easy generation. With the study of stream cipher, more and more new results appeared and the new requirements about good pseudorandom sequences in cryptography were put forward. The linear complexity became an important standard to estimate the pseudorandom properties after Massey provided the Berlekamp-Massey synthesis algorithm in 1969. However, the sequence having a large linear complexity may not be secure enough. For example, the period and the linear complexity of the sequence (110010111001011100100)∞both reach the maximal value 21, however, it is a quite insecure sequence because altering the last bit of each period will reduce the linear complexity of the sequence to be 3. Therefore, another important standard to scale the pseudorandom properties of the sequences is proposed:k-error linear complexity.In this dissertation, the distribution property of the terror linear complexity is discussed which include the value of k-error linear complexity, the number of the sequences with the given k-error linear complexity, the expected of the k-error linear complexity and the decreasing point of the linear complexity etc. The main results are as follows:1. For the 2n-periodic binary sequence with linear complexity 2n-1, the possible values for the 2-error(or 3-error) linear complexity and the number of sequences with certain 2-error(or 3-error) linear complexity, moreover, the expected of the 2-error(or 3-error) linear complexity is calculated, that is, the distribution of the 2-error(or 3-error) linear complexity are provided.2. For a random 2n-periodic binary sequence, the distribution of the 2-error linear complexity is discussed. That is to say, the possible values for the 2-error linear complexity and the number of sequences with certain 2-error linear complexity are established. Moreover, the expected of the 2-error linear complexity for a random 2n-periodic binary sequence is also given.3. For a random 2n-periodic balanced binary sequence, the distribution of the 2-error linear complexity is discussed simply.4. For a pn-periodic sequence over Fp, the possible values of the 1-error linear complexity and the number of sequences with certain 1-error linear complexity are established. Then the expected of the 1-error linear complexity for a random pn-periodic sequence over Fp is also given. Moreover, the bounds for the expect value of k-error linear complexity are provided.5. The upper bound for the first decreasing point of the linear complexity is given for a binary sequence with period 2p". Furthermore, it is showed that the upper bound can be reached for a binary sequence with period 2p in most condition. 6. The upper bound for the first decreasing point of the linear complexity is given for a sequence with period 2p" over Fq.7. The cyclotomic polynomialΦpq(x) and its factorization are analyzed and the upper bound for the first decreasing point of the linear complexity is given for a binary sequence with period pqn.