New Results on the -1 Conjecture on Cross-Correlation of m-Sequences Based on Complete Permutation Polynomials
Journal article, Peer reviewed
Accepted version
View/ Open
Date
2023Metadata
Show full item recordCollections
- Department of Informatics [985]
- Registrations from Cristin [10615]
Original version
IEEE Transactions on Information Theory. 2023, 69 (6), 4035 - 4044. 10.1109/TIT.2023.3238994Abstract
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 ≡ 1 (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 ≡ 1 (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(prtm − 1)/(r + 1) over Fprtm , where p is a prime, r + 1 is an odd prime satisfying p r 2 ≡ −1 (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 investigating the existence of irreducible polynomials over Fp 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 Fprtm 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(prtm − 1)/(r + 1) when t is a sufficiently large integer.