<s>[INST] Factorize polynomial over $GF(3)$ I want to factorize $x^{11}-1$ over $GF(3)$ but I'm stuck at 
$(x-1)(x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1).$
I have tried to do it trial and error but failed. Is
$$
x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1
$$
already irreducible over $GF(3)$?
 [/INST] The polynomial
$$
\phi_{11}(x):=\frac{x^{11}-1}{x-1}=\sum_{i=0}^{10}x^i\in GF(3)[x]
$$
is not irreducible. Because $11\mid 3^5-1=242$, there is a primitive eleventh root of unity in the field $GF(3^5)$. This is a quintic extension field of $GF(3)$, so the minimal polynomials of all the primitive eleventh roots of unity are of degree $5$. Thus $\phi_{11}(x)$ must be a product of two irreducible quintic factors.

Finding the factors takes a bit of work.  We repeatedly use the fact that, if $\beta$ is a root of a polynomial $f(x)\in GF(3)[x]$, then so
is its image $F(\beta)=\beta^3$ under the Frobenius automorphism. 
Let $\alpha$ be one of the roots of $\phi_{11}(x)$.
It has conjugates $F(\alpha)=\alpha^3$, $F(\alpha^3)=\alpha^9$, $F(\alpha^9)=\alpha^{27}=\alpha^5$ (here we use the fact that $\alpha^{11}=1$, so as $27=2\cdot11+5$ we get $\alpha^{27}=\alpha^5$) and $F(\alpha^5)=\alpha^{15}=\alpha^4$ (same trick). We can stop here as $F(\alpha^4)=\alpha^{12}=\alpha$, so we won't get any more conjugates ($F$ generates the relevant Galois group). Therefore the minimal polynomial of $\alpha$ is
$$
m_{\alpha}(x)=(x-\alpha)(x-\alpha^3)(x-\alpha^9)(x-\alpha^5)(x-\alpha^4)=x^5+ax^4+cx^3+bx^2+dx+e\in GF(3)[x].
$$
The other eleventh roots of unity are the reciprocals of these, so
$$
m_{1/\alpha}(x)=(x-\alpha^{10})(x-\alpha^8)(x-\alpha^2)(x-\alpha^6)(x-\alpha^7),
$$
and
$$
\phi_{11}(x)=m_{\alpha}(x)m_{1/\alpha}(x)
$$
is the desired factorization.
Let us next compute the coefficient $e=(-1)^5\alpha\cdot\alpha^3\cdot\alpha^9\cdot\alpha^5\cdot\alpha^4=-\alpha^{22}=-1$. To make further progress, we use the fact that the roots of $m_{1/\alpha}(x)$ are the reciprocals of the roots of $m_{\alpha}(x)$. Thus the polynomial $x^5m_{\alpha}(1/x)=ex^5+dx^4+cx^3+bx^2+ax+1$ has the same roots (with the same multiplicities) as $m_{1/\alpha}(x)$, so they must be scalar multiples of each other.
Taking into account the known constant term $e=-1$ we get
$$
m_{1/\alpha}(x)=x^5-dx^4-cx^3-bx^2-ax-1.
$$
There are four unknowns $a,b,c,d\in GF(3)$. We get a bunch of equations tying these together by expanding $m_{\alpha}(x)m_{1/\alpha}(x)=\phi_{11}(x)$. There may be a systematic way of solving the resulting system, but I took the easy way out, and guessed $a=0$ (there are three possible values of $a$, so guessing won't take much time). This leads to a solution $d=-1$, $b=-1$, $c=1$ and to the factorization
$$
\phi_{11}(x)=(x^5-x^3+x^2-x-1)(x^5+x^4-x^3+x^2-1).
$$
</s>