Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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:
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)$?
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.
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.
