# Probably Primitive Polynomials

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.

• When is a polynomial in $\mathbb Z_2[X]$ primitive ? Aug 3, 2017 at 18:43
• @Peter When its zeros are so called primitive elements. In the context of finite fields an element is primitive, if it is a generator of the multiplicative group of the field (see the Tag Wiki). This is analogous to so called primitive roots modulo a prime. Aug 3, 2017 at 21:37
• Ed, if you know a non-trivial factor $d\mid 2^p-1$ and a primitive polynomial of degree $p$, then finding an irreducible non-primitive polynomial $m(x)$ should be straightforward. If $\alpha$ is a zero of $m(x)$, then the minimal polynomial of $\beta=\alpha^d$ is one such. To find it "all" you need to do is to write the powers $\beta^j$, $j=0,1,\ldots,p$ w.r.t. the monomial basis consisting of powers of $\alpha$. This is straightforward (but I wouldn't do it with paper & pencil). You can compute $\alpha^d$ by using square-and-multiply. Aug 3, 2017 at 21:47
• (cont'd) Then you need to solve for the coefficients of the minimal polynomial of $\beta$ from the linear $p\times p$ system over $GF(2)$. You probably knew that already. I'm afraid I don't know the answers to any of your more difficult questions. Aug 3, 2017 at 21:48
• How about p=67, d=193707721, primpoly=1+x+x^2+x^5+x^67? I don't see how you use the primitive polynomial in your method. Aug 3, 2017 at 21:59

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:=powers = Table[PolynomialRemainder[x^(j*193707721), 1 + x + x^2 + x^5 + x^67, x, Modulus -> 2], {j, 0, 67}];
In:=coeffs = Table[m[j], {j, 0, 67}];
In:=prod = coeffs.powers;
In:=terms = CoefficientList[prod, x];
In:=m = 1;
In:=m = 1;
In:=Solve[Table[terms[[i]] == 0, {i, 1, 67}], Table[m[i], {i, 1, 66}],
Modulus -> 2];
In:=minimal = coeffs/.%[];
In:=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.

• Very nice. I've done searches for low weight primitive polynomials myself for all binary degrees to 1206. It's basically checking a up to a few thousand polynomials, and doesn't take long. Brute force. Polynomials as you've found here are much, much, much rarer. Brute force won't work. Aug 4, 2017 at 6:30
• I've added more solutions, and a conjecture. Aug 4, 2017 at 15:31