Analysis Of Stability For Periodic Sequences

Pseudorandom sequences are widely used in cryptography, communication and computation, etc. It is an important issue that how to evaluate the pseudorandom sequences. With the study of stream cipher, especially by the end of 1960, the B-M complicated algorithm, which is reported by Berlekamp-Massey, made the linear complexity become the important standard of stream cipher. The linear complexity of a sequence is the length of the shortest linear feedback shift register that can generate the sequence, denoted by LC ( a ).If 2 LC ( a )continuous bits of this sequence were known, we can find the whole sequence, using B-M algorithm. So the linear complexity of sequence must be large enough. But a sequence with large linear complexity is not necessarily a safe stream cipher. For example, the period and the linear complexity of the sequence a = (000010000100001 )both reach the maximal value 5, 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 0. Therefore, another important standard to scale the pseudorandom properties of the sequences is proposed: k - error linear complexity. Besides having large linear complexity and k - error linear complexity, cryptographically strong sequences should also have as fewer error sequences for small k .Firstly, because of the characteristic that k - error linear complexity can well reflect sequence's stability, for a 2n - periodic binary sequence with linear complexity 2 n - 2m, the specific forms of the k - error linear complexity are obtained using Chan-Games algorithm and an example is given to illustrate the specific forms. The result presented of stream cipher is so important that it can be used to analyze the safety of periodic key sequences more deeply. Secondly, based on the number of error sequences has strong relations with security of the key sequences, the possible number of k - error sequences of 2n - periodic binary sequences with linear complexity 2 n - 2m is also provided for k = 4,5.