Analysis Of The Linear Complexity And Its Stability For Periodic Sequences

The linear complexity and its stability are of fundamental importance as complexitymeasures for periodic sequences in stream cipher. This dissertation investigates theirproperties,their statistical characteristics and the relationship between them. The mainresults are as follows:(1) The unique expressions of the linear complexity for pⁿ and 2pⁿ-periodic binarysequences are presented and proved, and thus exactly one to one correspondencesbetween the linear complexity and the n + 1-dimensional vector are given. Theselead to the concept of the vector expression of the linear complexity.(2) For pⁿ-periodic binary sequences and pⁿ-periodic q-ary sequences, the tight upperbounds on minimum error, expressed by the weight of error sequences, are given.(3) For 2pⁿ-periodic binary sequences, a new weight function, according to the abovepresented vector expression of the linear complexity, is defined. By analyzing theweight of the product of a special kind polynomial in finite field, the upper andlower bounds on minimum error, expressed by the here defined weight of the linearcomplexity, are given in different cases.(4) For 2ⁿp^m-periodic binary sequences, the tight upper bound on minimum error, isgiven.(5) For p^mqⁿ-periodic q-ary sequences, the upper bounds on minimum error, expressedby the weight of error sequences, are given.(6) In the following two cases: (1)gcd(N,p) = 1 ; (2)N = p^v, where p denotes thecharacteristic of the finite field GF(q), by using the factorization of the polynomialin finite field, the counting function N_N,0(c) is showed, the expected value of thelinear complexity E_N,0 is determined, and a useful lower bound on the expectedvalue of the k-error linear complexity E_N,k is established.(7) The stability of the lattice structure for pseudorandom number sequences is putforward. The concepts of weight lattice structure, sphere lattice structure and k-error lattice structure are introduced to describe it, some properties of the k-errorlattice structure are given, and a relationship between the k-error lattice structureand the k-error linear complexity is presented. These create a elementary frame ofthe stability theory of the lattice structure.