Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$?

share|improve this question
    
The basic concept is exactly the same as that of factorizing over any other field. –  Mariano Suárez-Alvarez Oct 16 '10 at 15:42
add comment

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
1  
Note that one gets each irreducible polynomial of degree dividing n with coefficients in the underlying field. –  Qiaochu Yuan Oct 16 '10 at 16:57
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.