Why x^p-1 Factors over GF(2) the Way It Does

Let p be a prime number. We know that F_2=GF(2)=\{0,1\}. Let F_2[x] be the ring  the polynomials with indeterminate x and coefficients in F_2. The polynomial (x^p-1) \in F_2[x] factors over F_2 as  follows for various p:

x^3-1=(1+x) (1+x+x^2).
x^5-1=(1+x) (1+x+x^2+x^3+x^4).
x^7-1=(1+x) (1+x+x^3) (1+x^2+x^3).
x^{11}-1=(1+x) (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}).
x^{13}-1=(1+x) (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}+x^{11}+x^{12}).
x^{17}-1=(1+x) (1+x^3+x^4+x^5+x^8) (1+x+x^2+x^4+x^6+x^7+x^8).

None of the factors above can be factored anymore, hence they are irreducible over F_2. Let us call x+1 the trivial factor since the root x= 1 already belongs to F_2. But why do we have two nontrivial irreducible factors of x^7-1, each of degree 3, whereas x^{13}-1 has only one non-trivial irreducible factor of degree 12? It appears that either there is only one nontrivial factor, or the degree of all nontrivial factors is the same. Why?

More formally, let n_p(d) be the number of the nontrivial irreducible polynomials of degree d appearing in the factorization of x^p-1 over GF(2). We would like to understand n_p(d).

In another post, I discussed the structure of the quotient ring R=F_\ell[x]/(x^p-1). There, we have shown that

\displaystyle R=F_\ell[x]/(x^p-1) \cong F_\ell \oplus (F_{\ell^r})^s,\ \ \ \ \ \ \ \ (*)

where r is the smallest natural that makes \ell^r \equiv 1 \pmod{p}, and s=(p-1)/r. Here, r is called the multiplicative order of \ell modulo p. Since Fermat’s little theorem tells us that \ell^{p-1}\equiv 1 \pmod{p}, it follows that r must divide p-1 and s will always be an integer.

So what? (A little head scratching.) Okay. A root of the polynomial x^p-1 is called a pth root of unity. Our base field, F_2, contains 1, the trivial root of unity. It turns out, the smallest extension E over F_2 that contains a non-trivial pth root of unity is E=F_{2^r}. (Why?) This extension E, once again, is isomorphic to the quotient field F_2[x]/(q(x)) where q(x) is an irreducible polynomial of degree r over F_2. Each copy of F_{2^r} in the decomposition of the quotient ring R corresponds to an irreducible polynomial of degree r. These polynomials are the factors of x^p-1 over F_2. Therefore,

\displaystyle \boxed{n_p(d)=\left\{\begin{array}{ll} (p-1)/ord_p(2) & \text{ if } d=ord_p(2) \\ 0 & \text{ otherwise} \end{array}\right..}

This means, in the factorization of x^p-1 over GF(2),

  • The degree of all nontrivial irreducible factors is the same, and it equals the order of 2 modulo p
  • The number of these factors times their degree equals (p-1)

Now that is awesome. Moreover, this argument is valid over any base field of prime order l, which was 2 in the above discussion.

For primes p = 3, 5, 11, 13, 19 and 29, r=ord_p(2)=p-1; hence there is only s=(p-1)/(p-1)=1 nontrivial irreducible factor of degree p-1 in the expansion of x^p-1 over GF(2). This is true in general for primes for which 2 is a primitive root.

When p=7, the order of 2 modulo 7 is r=3. This is why there are (7-1)/3=2 irreducible factors of degree 2 in the expansion of x^p-1 over GF(2). When p=17, the order of 2 modulo 17 is r=8. This is why there are only (17-1)/8=2 irreducible factors of degree 8 in the expansion of x^p-1 over GF(2). A similar analysis is true for p=23.

Let N(d) be the number of monic degree-d irreducible polynomials over $latex F_2$. (See this sequence and this Wikipedia article.) The splitting fields of two irreducible polynomials of the same degree are isomorphic. (Why? See this post again.) Hence the polynomials of a given degree d appearing in the factorization of x^p-1 are not unique; unless, of course, all N(d) of them appear together and makes the factorization unique. This is indeed the case for x^7-1, where all N(3)=2 monic irreducible polynomials of degree 3 appear as its factors.



One thought on “Why x^p-1 Factors over GF(2) the Way It Does

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s