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?

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