<s>[INST] 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?
 [/INST] 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$.
</s>