Research On The Cross-correlation Properties Between M-sequence And Its Decimated Sequences

Because of good correlation properties, m-sequences are widely employed in the military cryptography and spread spectrum communication. In stream cipher, as important parameter of characterization the pseudo-random of key sequence, correlation function becomes a hot issue of research and design. m-sequence has two autocorrelation values, i.e., optimal autocorrelation. At present, the study of autocorrelation properties is comparatively perfect. But the calculation of cross-correlation function is difficult and it still lacks of a complete description of characteristics.The study of cross-correlation function between two m-sequences of same series can be attributed to that of an m-sequence and its decimated sequence. And decimation pays a decisive role in the values of cross-correlation function. Therefore for given decimations, getting the several-valued cross-correlation function and determining the distributions becomes an important aim.The calculation of cross-correlation function can be translated to that of exponential sum over finite field. At present, the lack of effective methods to solve the general exponential sum restricts the research of cross-correlation function. Quadratic form theory is one of rapid and effective tools to calculate exponential sum. Based on quadratic form theory, the third chapter studies the cross-correlation function and distribution between p-ary m-sequence and its like-quadratic decimated sequence. The main achievements and innovations are:A. We find a kind of decimations of similar structure and firstly propose the concepts of like-quadratic cross-correlation function. Based on the quadratic form theory over finite field, we get the common method of calculating cross-correlation function between m-sequence and its like-quadratic decimated sequences, and give their values’upper bound. We mainly calculate two like-quadratic cross-correlation functions and distributions:1. For decimation d= （p2k+1）/（pk+1）, we get the five-valued distributions of cross-correlation function Cd（τ） between m-sequence and its decimated sequence. Based on the quadratic form theory over finite field, through calculating the ranks of quadratic form, the paper gets the five values of Cd（τ）. With addition of the distributions of symmetric matrix, we firstly introduce association schemes of symmetric matrix to determine the specific distributions of Cd（τ）.2. We get a new decimation d=（p2m+2p2m-1+2pm-1-1）/2（pk+1）. Based on the quadratic form theory over finite field, by finding ranks of quadratic forms, the upper bound of cross-correlation function between m-sequence s（t） and decimated sequences s（dt+1） is gotten, where 0≤l<（pm+1）/2. Furthermore, whenk=1, we obtain the six-valued cross-correlation distributions between s（t） and its decimated sequence s（dt）.B. The fourth chapter calculates values of two kinds of Niho cross-correlation function.3. We get a new Niho decimation d=（3p2m+2pm-1）/4. In the calculation of cross-correlation function, we split the variables into in the form of multiplication of two primitives with low order and reduce the order of equation. Based on the known exponential sum, we get two quadratic equations and deduce that there are at most three solutions. Finally, we known that the cross-correlation function between m-sequences（t） and decimated sequencess（dt+l）takes values-1,-1-1-[pn^1/2,-1+pn^1/2, or -1+2pn^1/2, where 0≤l< （pm+1）/2.4. We get a new Niho decimation d=p2m-（p2m+1-2pm）/2（ps+1） with at most nine-valued cross-correlation. Over binary finite field, Dobbertin get a kind of decimations which contain all four-valued cross-correlation Niho decimations. We expand these results to those over odd prime field. And we need to calculate two equations with high degree. It is known that there are four cases of solution number of each equation, and the total is nine. We proof that the cross-correlation function between m-sequence.s（t） and s（dt） has at most nine values.