Probably Primitive Polynomials

Question

Over GF(2), degree 11 ($2^{11}-1=23\times89$) there are 186 irreducible polynomials (A001037) and 176 primitive polynomials (A011260). There are only 10 irreducible but not primitive polynomials of this degree, the below and the 11-power reversals. With a polynomial modulus of the first, $x^{23} =1$, for the rest $x^{89} =1$.
$1 + x + x^5 + x^6 + x^7 + x^9 + x^{11}$
$1 + x + x^6 + x^7 + x^{11}$
$1 + x + x^2 + x^4 + x^5 + x^8 + x^{11}$
$1 + x + x^2 + x^3 + x^5 + x^6 + x^7 + x^8 + x^{11}$
$1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^{10} + x^{11}$

For the Frank Nelson Cole number, ($2^{67}-1=193707721\times761838257287$), there are 2202596307308603178 - 2202596295934991760 = 11373611418 irreducible but not primitive polynomials. Is there an easy way to find one of them? A randomly chosen irreducible polynomial has a 0.99999999483627 chance to be primitive.

Based on exponents 11, 67, 101, 137, 149, 523, 727, and 1061, when the factorization of $2^{p}-1$ yields a large valued semiprime, the odds of irreducible being primitive are roughly $1-2^{-\frac{4}{9}p}$. Do any of the irreducible but not primitive polynomials for these degrees have conveniently short forms? With the factorizations, finding primitive polynomials isn't hard. These are primitive:
$1 + x^2 + x^{11}$
$1 + x + x^2 + x^5 + x^{67}$
$1 + x + x^6 + x^7 + x^{101}$
$1 + x^{21} + x^{137}$
$1 + x^7 + x^9 + x^{10} + x^{149}$
$1 + x^2 + x^6 + x^{13} + x^{523}$
$1 + x^{180} + x^{727}$
$1 + x + x^3 + x^{10} + x^{1061}$

The number $2^{1277}-1$ has no known factors. A degree 1277 irreducible polynomial would have a high likelihood of being primitive. Are there any reasonable ways of proving primitivity for one of these irreducible polynomials without knowing the factorization? Given a user-selected small set of these polynomials, is it possible to prove at least one of them must be primitive? One irreducible polynomial of this degree is $1 + x^{10} + x^{11} + x^{18} + x^{1277}$. It's probably primitive.

EDIT: Jyrki's solution below works amazingly well. Solutions for degrees 67, 101, 137, 149.

PolynomialMod[x^761838257287,1+x^2+x^4+x^5+x^6+x^8+x^10+x^11+x^12+x^15+x^16+x^18+x^19+x^22+x^24+x^25+x^29+x^31+x^32+x^35+x^38+x^39+x^40+x^41+x^43+x^44+x^45+x^46+x^52+x^53+x^55+x^56+x^59+x^60+x^61+x^62+x^63+x^66+x^67,Modulus->2]

PolynomialMod[x^341117531003194129,1+x^4+x^6+x^9+x^12+x^14+x^17+x^24+x^25+x^26+x^27+x^28+x^33+x^34+x^35+x^37+x^41+x^42+x^44+x^45+x^47+x^48+x^49+x^56+x^58+x^60+x^63+x^64+x^65+x^68+x^70+x^75+x^76+x^77+x^79+x^80+x^81+x^82+x^83+x^84+x^86+x^87+x^88+x^89+x^91+x^92+x^93+x^94+x^95+x^100+x^101,Modulus->2] 

PolynomialMod[x^5439042183600204290159,1+x+x^7+x^9+x^10+x^11+x^12+x^14+x^15+x^16+x^17+x^18+x^21+x^22+x^24+x^26+x^27+x^28+x^29+x^31+x^32+x^33+x^34+x^36+x^37+x^39+x^40+x^42+x^43+x^44+x^46+x^49+x^50+x^54+x^62+x^63+x^64+x^68+x^69+x^70+x^71+x^72+x^73+x^74+x^77+x^78+x^83+x^85+x^89+x^91+x^93+x^95+x^98+x^99+x^103+x^111+x^113+x^114+x^118+x^120+x^130+x^131+x^133+x^136+x^137,Modulus->2] 

PolynomialMod[x^8235109336690846723986161,1+x^2+x^4+x^5+x^7+x^9+x^12+x^14+x^16+x^18+x^20+x^22+x^23+x^24+x^25+x^29+x^31+x^32+x^34+x^35+x^36+x^40+x^41+x^42+x^44+x^45+x^46+x^47+x^48+x^51+x^52+x^53+x^57+x^65+x^67+x^68+x^72+x^73+x^74+x^75+x^77+x^79+x^81+x^82+x^83+x^86+x^88+x^90+x^93+x^95+x^96+x^98+x^99+x^100+x^102+x^103+x^104+x^105+x^106+x^108+x^109+x^111+x^112+x^113+x^114+x^116+x^119+x^122+x^126+x^128+x^129+x^130+x^132+x^134+x^136+x^141+x^142+x^146+x^147+x^148+x^149,Modulus->2]

I've also studied Joerg Arndt's nonprimitive irreducible trinomials table. I'll make a conjecture based on that study.

For enormous prime divisors $d_1$ and $d_2$, if modulus a low weight irreducible polynomial $x^{(2^p-1)/d_1}=1$, then also $x^{(2^p-1)/d_2}=1$. A tiny polynomial cannot split an enormous semiprime. As a corollary, if all factors of $(2^p-1)$ are enormous, low weight irreducible polynomials are also primitive.

Answer 1

Answering the first question on finding a non-primitive irreducible polynomial of degree $p$, when factors of $2^p-1$ and a primitive polynomial $p(x)$ are known. The rest of the questions are more difficult, and I have nothing useful to say about them.

Let $\alpha$ be the corresponding primitive element, i.e. a zero of $p(x)$. Let's use the basis $\mathcal{B}=\{1,\alpha,\alpha^2,\ldots,\alpha^{p-1}\}$ for $GF(2^p)$ over $GF(2)$. Let $\beta=\alpha^d$.

The minimal polynomial $m(x)=\sum_{i=0}^pm_ix^i$ of $\beta$ can be found as follows.

1. Calculate the powers $\beta^j,j=0,1,\ldots,p$ in terms of the basis $\mathcal{B}$. This can be done efficiently with square-and-multiply.
2. Because $m(x)$ is irreducible of degree $p$, we know that $m_0=m_p=1$. Using this and the result of the earlier calculation we can write the sum $$S=\sum_{i=0}^pm_i\beta^i$$ in terms of $\mathcal{B}$. We treat the coefficients $m_1,m_2,\ldots,m_{p-1}$ as unknown variables. Observe that $S$ is linear in all these variables.
3. Solve the unknowns $m_1,\ldots,m_{p-1}$ from the system $S=0$.

A way to accomplish this with Mathematica is the following (ask Mathematica gurus for tips to possibly make this more efficient). I did the example of $$ \begin{aligned} p&=67,\\ p(x)&=1+x+x^2+x^5+x^{67},\\ d&=193707721. \end{aligned} $$

In[1]:=powers = Table[PolynomialRemainder[x^(j*193707721), 1 + x + x^2 + x^5 + x^67, x, Modulus -> 2], {j, 0, 67}];
In[2]:=coeffs = Table[m[j], {j, 0, 67}];
In[3]:=prod = coeffs.powers;
In[4]:=terms = CoefficientList[prod, x];
In[5]:=m[0] = 1;
In[6]:=m[67] = 1;
In[7]:=Solve[Table[terms[[i]] == 0, {i, 1, 67}], Table[m[i], {i, 1, 66}], 
 Modulus -> 2];
In[8]:=minimal = coeffs/.%[[1]];
In[9]:=minpol = Sum[minimal[[i]] x^(i - 1), {i, 1, 68}]

And in the last step Mathematica kindly gave the output $$m(x)=x^{67}+x^{66}+x^{63}+x^{62}+x^{61}+x^{60}+x^{59}+x^{56}+x^{55}+x^{53}+x^{5 2}+x^{46}+x^{45}+x^{44}+x^{43}+x^{41}+x^{40}+x^{39}+x^{38}+x^{35}+x^{32 }+x^{31}+x^{29}+x^{25}+x^{24}+x^{22}+x^{19}+x^{18}+x^{16}+x^{15}+x^{12} +x^{11}+x^{10}+x^8+x^6+x^5+x^4+x^2+1$$ as the minimal polynomial of $\beta$.

As a final check I calculated that the remainder of $x^{761838257287}$ modulo $m(x)$ is equal to $1$ as it should, because the multiplicative order of $\beta$ is $(2^p-1)/d$.

You can similarly find the minimal polynomial of any power of $\beta$. Unfortunately I don't know how to find an exponent $s$ such that the minimal polynomial of $\beta^s$ would have a low number of terms. The question of finding low weight primitive polynomials has received quite a bit of attention, but I'm afraid I haven't followed that work at all.