How do I factorize a polynomial $X^n - 1$ over $\mathbb{F}_p$? In particular I need to find factors of the polynomial $X^{3^3 - 1} - 1 = X^{26} - 1$ over $\mathbb{F}_3$.
$\begingroup$
$\endgroup$
7
-
4$\begingroup$ en.wikipedia.org/wiki/Berlekamp%27s_algorithm en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm $\endgroup$– Steve HuntsmanCommented Feb 3, 2010 at 22:16
-
1$\begingroup$ For your example: Check that $p(X)=X^3+2X+1$ is an irreducible polynomial of a primitive element of $(\mathbb{F}_{27})^*$. To do that, see that the images of $1,X,\ldots,X^{25}$ in $\mathbb{F}_3[X]/(P(X))$ are all different. In the process, you'll get the coefficients of all field elements according to the basis $1,\alpha,\alpha^2$ of $\mathbb{F}_{27}/\mathbb{F}_3$, where $\alpha$ is the image of $X$. Now use the partition of $\mathbb{F}_{27}$ to orbits under the Galois group, generated by $x\mapsto x^3$, and multiply linear factors to get the irreducible polynomials. $\endgroup$– user2734Commented Feb 3, 2010 at 23:17
-
1$\begingroup$ Abstract Algebra by Dummit and Foote has a section on finite fields (14.3) which should have all the info you need. $\endgroup$– Sonia BalagopalanCommented Feb 3, 2010 at 23:34
-
3$\begingroup$ What the heck does this have to do with Kummer theory? $\endgroup$– darij grinbergCommented Feb 4, 2010 at 10:21
-
3$\begingroup$ I guess I was wrong. $\endgroup$– Harry GindiCommented Feb 4, 2010 at 15:50
|
Show 2 more comments
3 Answers
$\begingroup$
$\endgroup$
1
If you just need a quick answer (to decide if something else is going to work how you need), then you can do this with Wolfram|Alpha. Go there: http://www.wolframalpha.com/ and input "factor x^26-1" and press the "equal" button. It'll show some info about the polynomial, including the factors mod 2. In many boxes, there's a link for "Show More". Press the one attached to the factors over GF(2), and it'll show you the factors over GF(3). In this case, you get $$(x+1) (x+2) (x^3+2 x+1) (x^3+2 x+2) (x^3+x^2+2) (x^3+x^2+x+2) (x^3+x^2+2 x+1) (x^3+2 x^2+1) (x^3+2 x^2+x+1) (x^3+2 x^2+2 x+2).$$
Annoying to have "2" instead of "-1" in GF(3), but that's the price of having a machine do your work for you.
answered Feb 4, 2010 at 15:08
-
$\begingroup$ I tried countless variations on wolframalpha, but not "factor x^26-1". thank you $\endgroup$ Commented Feb 10, 2010 at 23:49
$\begingroup$
$\endgroup$
I describe how to do this generally in my answer to question #16457 about cyclotomic integers. However, in this particular problem you are probably supposed to use the fact that the divisors of $x^{p^n} - x$ over $\mathbb{F}_p$ are precisely the irreducible polynomials of degree dividing $n$.
answered Feb 3, 2010 at 22:22
$\begingroup$
$\endgroup$
2
This seems very much like homework to me, so I'll be brief. I assume that your $Z_p$ denotes the field with $p$ elements; I will call it $\mathbb{F}_p$ henceforth (lest it be confused with the ring $\mathbb{Z}_p$ of $p$-adic integers).
You want to factor the polynomial $X^{p^a-1}-1$ over $\mathbb{F}\_{p}$. Let us go into the field $\mathbb{F}_{p^a}$; what are the roots of the polynomial $X^{p^a-1}-1$ factor over there? Hence, which divisors does $X^{p^a-1}-1$ have over $\mathbb{F}_p$ ? Can any of them occur more than once?
answered Feb 3, 2010 at 22:23
-
$\begingroup$ Yes, it's part of a homework, but the factorization is already given at few.vu.nl/~jeu/Teaching/CC/Notes0.pdf (page 22). Unfortunately the provided factorization is wrong and I need the correct one to continue. $\endgroup$ Commented Feb 3, 2010 at 22:34
-
1$\begingroup$ @Alexandru: You are right, there is a typo, and the last factor should be $X^3+X^2-X+1$. $\endgroup$ Commented Feb 3, 2010 at 23:07