How do I factorize polynomial over Galois field? How does the factoring of polynomials over Galois fields work? I cannot seem to understand the basic concept.
For example: How do I factorize $x^6 - 1$ over $\operatorname{GF}(3)$? I know that the result is $(x+1)^3 (x+2)^3$, but I'm unable to compute it myself.
I've studied the articles on Wikipedia:


*

*http://en.wikipedia.org/wiki/Galois_field

*http://en.wikipedia.org/wiki/Factorization_of_polynomials
but I found it very difficult to understand. Is there some algorithm that would help me factorize polynomials like $x^n - 1$ over $\operatorname{GF}(k)$?
 A: If $n=pm$ is a multiple of $p$ then over $GF(p)$ one has
$$x^n-1=(x^m-1)^p$$
so the problem reduces swiftly to the case where $n$ is coprime to $p$.
If $p$ is not a factor of $n$ then over an algebraic closure of
$GF(p)$
$$x^n-1=\prod_{k=0}^{n-1}(x-\zeta^j)$$
where $\zeta$ is a primitive $n$-th root of unity.
One makes this into a factorization over $GF(p)$ by combining conjugate
factors together. For each $k$, the polynomial
$$(x-\zeta^k)(x-\zeta^{pk})(x-\zeta^{p^2k})\cdots(x-\zeta^{p^{r-1}k})$$
has coefficients in, and is irreducible over, $GF(p)$ where $r$
is the least positive integer with $p^r k\equiv k$ (mod $n$).
Using this, it's easy to work out the degrees of the irreducible
factors of $x^n-1$, but to find the factors themselves needs a bit more
work, using for instance Berlekamp's algorithm.
A: Factoring the polynomials $x^n - 1$ is very different from factoring general polynomials, since you already know what the roots are; they are, in a suitably large finite extension, precisely the elements of order dividing $n$.  Since you know that the multiplicative group of a finite field is cyclic, the conclusion follows from here.
