New Results on the −1 Conjecture on Cross-Correlation of m-Sequences Based on Complete Permutation Polynomials
Gaofei Wu, Keqin Feng, Nian Li, Tor Helleseth · IEEE Transactions on Information Theory · 2023
The cross-correlation between two maximum length sequences ($m$-sequences) of the same period has been studied since the end of 1960s. One open conjecture by Helleseth states that the cross-correlation between any two$p$-ary$m$-sequences takes on the value −1 for at least one shift provided that the decimation$d$obeys$d\equiv 1\,({\mathrm{ mod}}\, p-1)$. This was known as the −1 conjecture. Up to now, the −1 conjecture was confirmed for the following decimations: (1) Niho-type decimations, i.e.,$d=s(p^{n/{2}}-1)+1$, where$s$is an integer; (2) all the complete permutation polynomial (CPP) exponents$d$satisfying$d\equiv 1\, ({\mathrm{ mod}}\, p-1) $; and (3) the additional families of decimations tabulated in this paper. In this paper, we first discuss the connection between the −1 conjecture on cross-correlation of$m$-sequences and CPP exponents, then we confirm the −1 conjecture for a new type of decimations by giving a new class of CPP exponents. The decimations are of the type$d=1+l{(p^{rtm}-1)}/{(r+1)}$over${\mathbb F}_{p^{rtm}}$, where$p$is a prime,$r+1$is an odd prime satisfying$p^{r/{2}} \equiv -1\,({\mathrm{ mod}}\, r+1)$,$t$is an odd integer ($t>2$if$p=2$) with$\gcd (t,r)=1$, and$m$is a positive integer. We transform the problem of determining whether$d$is a CPP exponent into that of investigating the existence of irreducible polynomials over$\mathbb {F}_{p}$with degree$t$satisfying a congruence equation. By a theorem given by Rosen that considered the number of irreducible polynomials with a special congruence relation, we prove that$d$is a CPP exponent over${\mathbb F}_{p^{rtm}}$for sufficiently large$t$. When$m$is odd, our new CPP exponents are of Niho type; thus, we give a new class of CPP exponents of Niho type. When$m$is even, we obtain a new class of CPP exponents which are not of Niho type. As a consequence, we show that the −1 conjecture is true for$d=1+l{(p^{rtm}-1)}/{(r+1)}$when$t$is a sufficiently large integer.