Primitive Trinomial for $82589933$?

246 Views Asked by At

At Twelve new primitive binary trinomials, $x^{74207281}+x^{9999621}+1$ is shown to be a primitive trinomial in $GF(2)[x]$.

Note that $2^{74207281}-1$ was the largest known (Mersenne) prime before 2018, that is the prime in the exponent of the Mersenne prime gave rise to a trinomial.

In the interim, new Mersenne primes have been found.

Just announced (Dec 2018), $2^{82589933}-1$ is prime, and in Jan 2018, $2^{77232917}-1$ was found to be prime.

Do these also give rise to trinomials?

To be explicit, are there $j$ or $k$ such that $x^{82589933}+x^{j}+1$ or $x^{77232917}+x^{k}+1$ are primitive trinomials in $GF(2)[x]$?

1

There are 1 best solutions below

1
On BEST ANSWER

As per Swan's Theorem, reproduced in The Great Trinomial Hunt, $T_{r,s}(x) \equiv x^r + x^s + 1$ has an even number of factors over $GF(2)$ if $r$ is $\pm 3 \pmod{8}$ and $s$ is even and not a factor of $2r$. Given that both of the Mersenne exponents above (82589933 and 77232917) are 5 mod 8, if $s>2$ even then we know $T_{r,s}$ is reducible.

Likewise as stated in the paper, $x^r + x^s + 1$ has the same number of factors as $x^r + x^{r-s} + 1$, which eliminates all odd $s$ aside from $s = r-2$.

So it suffices to look at $x^r + x^2 + 1$ for the two values of $r$ in question. This is not exactly an easy computation, even though polynomial squaring is easy in $GF(2)$.

Fortunately, the paper then suggests a useful trick -- sieving against small factors by using the fact that $T \mod x^d+1 = x^{(r \pmod{d})} + x^{(s\pmod{d})} + 1$.

With this, it is easy to see that $x^{82589933} + x^2 + 1$ and $x^{77232917} + x^2 + 1$ are both divisible by $x^3+x+1$.

So there are no primitive trinomials for these primes.