abstract algebra - 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?

Answer

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. = 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.