Cross-correlation of M-sequences, exponential sums and dickson polynomials

摘要

Let s(t) and s(dt) be two binary m-sequences of the same period 2^m - 1 where gcd(d, 2^m - 1) = 1 . The cross-correlation between these two m-sequences is defined to be c_d(tau) = Sigma_t(-1)^{s(t+tau)-s(t)}, where the summation is over a full period t = 0,1,hellip, 2^m - 2 . The main problem is to find the distribution of the cross-correlation i.e., the values that occur and their multiplicity when tau ranges through 0,1,hellip, 2^m - 2. The cross-correlation between m-sequences is a well studied problem during the last 40 years. A survey over known results as well as an overview of some interesting remaining open problems is presented. In particular new recent results are presented for the cross-correlation of sequences with decimations on the form d = (2^k + 1)/(2^r + 1) using connections to Dickson polynomials and calculations of some special exponential sums.