# Rabin's test for polynomial irreducibility over $\mathbb{F}_2$

I know that $f(x) = x^{169}+x^2+1$ is a reducible polynomial over $\mathbb{F}_2$. I want to show this using Rabin's irreduciblity test. First, I then have to check if $f$ is a divisor of $x^{2^{169}}+x$ and this is where I get stuck. That exponent is way too large to work with. How to handle such cases?

• Although that is a pretty big exponent, bear in mind that you want to show $x^{2^{169}}$ is congruent to $x$ mod $f$ (over $\mathbb{F}_2$). Binary exponentiation over that polynomial ring will be tedious but if suitably automated, gives the result in respectable time. – hardmath Oct 16 '13 at 14:25

The description of how to apply Rabin's irreducibility test to $f(x) = x^{169} + x^2 + 1$ in the Question is a bit terse, perhaps verging on an omission. So let's begin with a brief account of how it applies; for a more general analysis see here, esp. Sec. 2.

Prop. Let $f \in \mathbb{F}_2[x]$ have degree $n$, and let $p_1,\ldots,p_k$ be the distinct prime divisors of $n$. $f$ is irreducible in $\mathbb{F}_2[x]$ if and only if $\gcd(f,x^{2^{n/p_i}}-x) = 1$ for $1 \le i \le k$ and $x^{2^n} \equiv x \mod f$.

The case at hand involves degree $n=169$, whose only prime divisor is $p=13$. Therefore our first task is finding the greatest common divisor of $f$ and $x^{2^{13}}-x$. Note that since the field of coefficients is $\mathbb{F}_2$, $-x = +x$, a fact we will take advantage of without further comment.

In computing the GCD we can go ahead and reduce $x^{2^{13}}+x$ modulo $f$, as this is the first step of the Euclidean algorithm. It provides an excellent opportunity to introduce binary exponentiation as a practical way to do this.

Define $g_m \equiv x^{2^m} \mod f$. Beginning with $g_0 := x$, we compute $g_{m+1} \equiv g_m^2 \mod f$ until we reach (for now) $g_{13}$. Note that $x^{2^{m+1}} = (x^{2^m})^2$.

Since $f$ has degree $n=169$, we can skip to $g_7 = x^{128}$ by inspection. Working modulo $f(x) = x^{169} + x^2 + 1$ means we can replace terms $x^{169}$ by $x^2 + 1$, so:

$$g_8 \equiv x^{256} \equiv x^{169}\cdot x^{87} \equiv (x^2 + 1)x^{87} \mod f$$

Thus $g_8 \equiv x^{89} + x^{87} \mod f$, but for our computation it will be more convenient to use the factored expression above:

$$g_9 \equiv (x^2 + 1)^2 x^{174} \equiv (x^2 + 1)^3 x^5 \mod f$$

$$g_{10} \equiv (x^4 + 1)^3 x^{10} \mod f$$

$$g_{11} \equiv (x^8 + 1)^3 x^{20} \mod f$$

$$g_{12} \equiv (x^{16} + 1)^3 x^{40} \mod f$$

$$g_{13} \equiv (x^{32} + 1)^3 x^{80} \mod f$$

We've made use above of the so-called Freshman Law of Exponents in characteristic $2$, namely that $(a+b)^2 \equiv a^2 + b^2 \mod 2$. After further reduction modulo $f$:

$$g_{13} + x \equiv x^{144} + x^{112} + x^{80} + x^9 + x^7 + x \mod f$$

At this point I shrug and turn the GCD calculation over to Maxima:

(%i1) modulus:2;
(%o1)                                  2
(%i2) gcd(x^169+x^2+1,x^144+x^112+x^80+x^9+x^7+x);
(%o2)                                  1


So the first hurdle is cleared in our application of Rabin's irreducibility test. What remains is the task outlined in the Question, showing $f$ divides $x^{2^{169}}+x$, or equivalently, that $g_{169} \equiv x \mod f$.

Having shown how to reach $g_{13}$, I will leave it to the Reader to continue the calculation by repeated squarings, in which task we are aided by the aforementioned Freshman Law of Exponents. Only 156 more steps to go!

If desired there's an alternative approach which uses many fewer but more difficult steps, involving a composition of polynomial functions. In particular:

$$g_m(g_r) \equiv g_{m+r} \mod f$$

so that composition of functions allows us to increase the index $m$ by doubling, thereby progressing rapidly to the goal $m=169$. While the composition of polynomials is much less convenient than repeated squarings, it's possible to invoke Maxima to do the work for us.

Notes on computation:

I've incorporated a command from Richard Fateman's recent Note at MO in the Maxima session above, setting modulus and correcting an omission in the GCD computation.

The day after posting my initial Answer, I sat down and wrote some Prolog code to square polynomials in $\mathbb{F}_2[x]/f(x)$, and the next day I elaborated the code to compute $g_{169}$ by steps:

$$g_{m+1} \equiv (g_m)^2 \mod f$$

The squaring part of the computation is actually trivial in my chosen representation, a descending list of the exponents for monomials with coefficient 1 in the polynomial, since by the Freshman Law all that is required is a doubling of each exponent. The only real work in each step is reducing the result modulo $f$. In the end I got that:

$$g_{169}(x) = x^{168}+x^{166}+x^{165}+x^{164}+x^{163}+x^{159}+\ldots +x^7+x^6+x^5+x^4$$

Since $g_{169} + x$ is not zero modulo $f$, $f(x)$ is reducible in $\mathbb{F}_2[x]$.

As a check I wanted to recompute $g_{169}$ using composition of polynomials mod $f$ as outlined earlier. Maxima can do this by combining compose and remainder (or divide), but Sage's modular_composition method (for polynomials over $\mathbb{F}_2$) is specific to our purpose:

sage: P.<x> = GF(2)[]
sage: f = x^169 + x^2 +1
sage: g1 = x^2
sage: g2 = g1.modular_composition(g1, f)
sage: g4 = g2.modular_composition(g2, f)
sage: g8 = g4.modular_composition(g4, f)
sage: g16 = g8.modular_composition(g8, f)
sage: g32 = g16.modular_composition(g16, f)
sage: g64 = g32.modular_composition(g32, f)
sage: g128 = g64.modular_composition(g64, f)
sage: g160 = g128.modular_composition(g32, f)
sage: g168 = g160.modular_composition(g8, f)
sage: g169 = g168.modular_composition(g1, f)


These computations confirm the expression for $g_{169}$ found by my scratch program.

The ten calls to modular_composition correspond to a binary addition chain for m=169, where as discussed:

$$g_m(g_r) = g_{m+r} \mod f$$

Shorter chains are often possible (Knuth, AOCP vol. 2: Semi-numerical Algorithms has a discussion), but here the binary chain turns out to have minimum length.

• +1 Has been there for some time. Only now I got around to looking for factors (after your calculations proved that it is not irreducible). – Jyrki Lahtonen Nov 1 '13 at 22:09

This is probably not what you wanted to see, but it is easy to see that your polynomial is divisible by $x^2+x+1=(x^3-1)/(x-1)$. Here $$x^{169}+x^2+1=(x^{169}+x)+(x^2+x+1)=x(x^{3\cdot56}+1)+(x^2+x+1),$$ and clearly $x^{3\cdot56}-1$ is divisible by $x^3-1$ and hence by $x^2+x+1$.

It is usually easy to check the divisibility of a `sparse' polynomial by the low degree polynomials: $x^2+x+1$, $x^3+x+1$, $x^3+x^2+1$, $x^4+x+1$, $x^4+x^3+1$, $x^4+x^3+x^2+x+1$, because they are respectively factors of $x^3-1$, $x^7-1$, $x^7-1$, $x^{15}-1$, $x^{15}-1$ and $x^5-1$.