5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ When is a polynomial in $\mathbb Z_2[X]$ primitive ? $\endgroup$ – Peter Aug 3 '17 at 18:43
  • $\begingroup$ @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. $\endgroup$ – Jyrki Lahtonen Aug 3 '17 at 21:37
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Aug 3 '17 at 21:47
  • 1
    $\begingroup$ (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. $\endgroup$ – Jyrki Lahtonen Aug 3 '17 at 21:48
  • $\begingroup$ 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. $\endgroup$ – Ed Pegg Aug 3 '17 at 21:59
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ed Pegg Aug 4 '17 at 6:30
  • $\begingroup$ I've added more solutions, and a conjecture. $\endgroup$ – Ed Pegg Aug 4 '17 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.