The Research On Error Linear Complexity Of Binary 2n-periodic Sequences

The sequences play an important role in Cryptography, Algebraic Coding Theory, Code Di-vision Multiple Access (CDMA) communication system, Computer Simulation and other fields. In cryptographic application, the linear complexity is very useful in the research on the security of stream ciphers.In stream ciphers, the periodic sequences used as keystreams should have high linear com-plexity, which can resist against the attack of the Berlekamp-Massey algorithm. While, a sequence with cryptographical strength not just possess a high linear complexity, but also have large k-error linear complexity. That is altering a few bits of sequence can not cause a drastic decrease of the linear complexity. So k-error linear complexity of a periodic sequence is usually used to measure the stability of the periodic sequence.The k-error linear complexity spectrum of a sequence indicates how the linear complexity change when k bits (or fewer bits) allowed to be altered perperiod. In the sense of the statistics, if a sequence have the more critical point number, then the sequence will have the better cryptographic properties.Besides, the critical error sequence is also important. If a sequence have the more critical error sequences, then the adversary has more choices to analyze the sequence, which shows that the se-quence is cryptographically weak and vulnerable to the threat. So the number of the critical points and the critical error sequences are also the important cryptographic measure of the sequence.This paper is based on the known results, further study on the error linear complexity of binary sequence with period 2n. The content conclude the algorithmic research on error linear complexity, the critical point problems in the error linear complexity spectrum of a sequence and the counting problems of the critical error sequences. The main research results as follows:1, Summarizing the algorithms about the linear complexity and k-error linear complexity of binary 2n-periodic sequences, by means of the Games-Chan (G-C) algorithm and Stamp-Martin (S-M) algorithm, a new and simple algorithm、the generalization of S-M algorithm for k-error linear complexity of binary 2n-periodic sequences are presented respectively. What’s more, the related conclusion are stated.2, Based on the counting method of sequences with two critical points, the way and formula to computer the number of sequences with three critical points are proposed.3, According to the research on the linear complexity and k-error linear complexity of the sequence, one formula to count the number of the critical error sequences is stated.