Research On The2-Adic Complexity And Linear Complexity Of Periodic Sequences

A stream cipher is an important private key cipher where each plaintext digit is encrypted one at a time with the corresponding digit of a key stream. Thus, the security of a stream cipher depends on the key stream, that is, the key stream bits should be that they appear like a random sequence. With the development of research, according to different key stream generators and attacks on stream ciphers, many indexes to measure the security of a sequence are proposed. The2-adic complexity and linear complexity are the two of important indexes. They are proposed based on Feedback Shift Register with Carry (FCSR) and Linear Feedback Shift Register (LFSR), to measure how large the generators are required to output a sequence, respectively. Large2-adic complexity and linear complexity can make a sequence resist Rational Approximation Algorithm and B-M Algorithm attacks effectively. So the computation, statistical characteristics and stability of the two indexes are hot topics in stream ciphers research. This dissertation discuss an upper bound for the2-adic complexity of periodic sequences, analysis the stability of2-adic complexity and determine the linear complexity of specific sequences. The main contributions of this work are as follows:1. By means of the usual Fourier transform, an upper bound for2-adic complexity of L-periodic binary sequences is improved, which is simpler than related result before. Moreover, for p"-periodic binary sequences, a lower bound for the number of sequences with given2-adic complexity is also obtained.2. The usual Fourier transform of periodic binary multisequences is proposed. By using it, an upper bound for the joint2-adic complexity of multisequences is discussed, and a lower bound for the number of pn-periodic binary multisequences with given joint2-adic complexity is derived.3. The exact value for the expected value of k-error2-adic complexity (k<L/2) of L-periodic sequences is determined when2L-1is a prime number, and lower bounds for expected values of binary periodic sequences, which satisfied2L-1=p1p2,P1n2,p1np2(P1,P2are prime numbers, n is an arbitrary integer) are derived.4. The definition of joint k-error2-adic complexity is proposed, as well as joint k-error2-adic complexity is used to measure the stability of joint2-adic complexity. Furthermore, the expected values of joint k-error2-adic complexity and joint k-error2-adic complexity of L-periodic multisequences are presented in two special cases, respectively.5. Lower bounds for the2-adic complexity of a binary sequence obtained from a periodic binary sequence by either inserting or deleting k symbols within one period are dicussed. Moreover, using the half-period complementary property of l-sequences, upper and lower bounds for the2-adic complexity of l-sequences by inserting, deleting and substituting2symbols within every period are derived, respectively. Meanwhile, the bounds of2-error2-adic complexity of l-sequences are tight.6. Based on single cycle T-function’s special properties, the linear complexity and its stablity of the sequences which are bitwise output of all single word single cycle T-functions are determined. For some2P words single cycle T-function, the period, linear complexity and k-error linear complexity of the sequences which are constituted by the first2’ bits in the consecutive states are given respectively. The study proves that the output sequences of the single cycle T-function have good properties. Moreover, the minimal polynomial and linear complexity over Z/(4) of a class of quaternary sequences with low autocorrelation constructed by generalized cyclotomic sequences are discussed. The results show that the sequences possess large linear complexity to resist Reeds-Sloane attack effectively.