The number of cross-join pairs in maximum length linear sequences
Tor Helleseth, Torleiv Kløve · IEEE Transactions on Information Theory · 1991
It has been conjectured by T. Chang et al. (1990) that the number of cross-join pairs in a maximum length linear sequence equals (2/sup n-1/-1)(2/sup n-1/-2)/6. A maximum length linear sequence (an m-sequence) of length 2/sup n/-1 is a binary sequence which satisfies a linear recurrence whose characteristic polynomial is primitive of degree n. The number of primitive polynomials is given by phi (2/sup n/-1)/n, where phi is Euler's phi -function. A proof of the conjecture is given.>