Probably Primitive Polynomials Redux

Question

Modulus $2$, is $1+x^{10}+x^{11}+x^{18}+x^{1277}$ a primitive polynomial?
Modulus $3$, is $1 + 2 x^{87} + x^{661}$ a primitive polynomial?
Modulus $5$, is $3 + 2 x^{28} + x^{431}$ a primitive polynomial?
Modulus $7$, is $4 + 2 x^{4} + 6 x^{5} + x^{359}$ a primitive polynomial?

Amusingly, soon after my run finished for finding $3 + 2 x^{28} + x^{431}$, NFS@Home snfs finished the factorization of $5^{431}-1$. I can verify that polynomial is primitive.

I found these by searching for low weight irreducible polynomial that "passed" for low factors. As shown at Probably Primitive Polynomials, irreducible but not primitive polynomials always exist if the corresponding (prime power - 1) is factorable. But these irreducible polynomials tend to have high weight.

$x^{((3^{661} - 1)/d)} \mod{(1 + 2 x^{87} + x^{661}, 3)} \equiv 2$ for $d=2$, the only known divisor for $3^{661} - 1$. Since the modulus doesn't equal 1, we can say that irreducible polynomial passes for that divisor. If a modulus $\equiv 1$ for a given divisor, it fails. What are low weight irreducible but not primitive polynomials requiring larger divisors to fail?

Mod $2$, $1 + x^{21} + x^{54}$ fails for divisors $87211$ and $262657$.
Mod $2$, $1 + x^{14} + x^{147}$ fails for divisors $4432676798593$ and $2741672362528725535068727$.
Mod $3$, $1 + x^4 + 2 x^5 + x^{75}$ fails for divisor $8951$.
Mod $5$, $3 + x^2 + x^3 + x^{85}$ fails for divisor $1531$.
Mod $7$, $3 + 2 x^2 + x^{32}$ fails for divisor $1201\times2$.

What are other low-weight polynomials that only fail for large divisors? Are the polynomial $1 + x^{21} + x^{54}$ and $1 + x^{14} + x^{147}$ special in some way? Are there other small weight polynomials that only fail for a 10+ digit divisors?

Answer 1

I believe that in general such questions are difficult. I did spot the following obvious obstructions to primitivity.

• The polynomial $p(x)=1+x^{21}+x^{54}$ can be rewritten as $q(x^3)$ with $q(x)=1+x^7+x^{18}$. Clearly $q(x)$ is irreducible also, for if it were not, then $p(x)$ would not be irreducible either. This means that any zero of $q(x)$ has order that is a factor of $2^{18}-1$. Consequently the order of a zero of $p(x)$ is a factor of $3\cdot(2^{18}-1)=786429$.
• Similarly the polynomial $r(x)=1+x^{14}+x^{147}=s(x^7)$ where $s(x)=1+x^2+x^{21}$. Again, as $s(x)$ is irreducible, the zeros of $r(x)$ have order at most $7\cdot(2^{21}-1)=14680057$.

It always happens that if $f(x)\in\Bbb{F}_p[x]$ is primitive of degree $n$, and $\ell$ is a prime number such that $\ell\mid p^n-1$, then $g(x)=f(x^\ell)$ is irreducible, but obviously not primitive. After all, any root of $g(x)$ must be of order $\ell(p^n-1)$ (need $\ell\mid p^n-1$ for this to hold). If $\ell^t$ is the highest power of $\ell$ that divides $p^n-1$, then $$ p^n=1+k\cdot\ell^t $$ with $\gcd(k,\ell)=1$, and it easily follows that $p$ has order $n\ell$ modulo $\ell^{t+1}$. This means that the roots of $g(x)$ generate an extension field of degree $\ell n$. In other words, $g(x)$ is irreducible.