Re: factorization in Z_3

Li Yi wrote: 
Okay. But how to factor
1 - x + x^2 - x^3 + x^4 - x^5 + x^6 - x^7 + x^8 - x^9 + x^10 - x^11 +
x^12?

It seems terrible to me.


Well, x^27-x does require some work, but do notice that from
general theory you can immediately infer that it is the product of all irreducible monics of degrees 1 and 3
(in Z_3[x] obviously).

In your textbook and/or course notes they have hopefully
described at least one irreducible polynomial of degree 3.
A very common choice is p(x)=x^3-x+a (with a=+1 or -1).
Let z be one of its roots in GF(27) (the other two are then
z^3=z+1 and z^9=z+2=z-1). Various and sundry tricks can be
applied here:
E.g. p(x)p(-x)=-q(x^2) for a certain monic cubic polynomial
q(x), which obviously has z^2 as its root, so q(x) is
then also an irreducible factor of x^27-x. Furthermore, if
f(x) is an irreducible monic cubic, then so are, e.g.
-f(-x), f(x+1), f(x-1), -f(-x+1), -f(-x-1). Do observe
that this "linear substitution trick" is not guaranteed
to always give new irreducible polynomials, e.g.
p(x+1)=p(x).

That oughta do it. If you go further (e.g. try x^81-x)
you will need more tools. E.g. the finite field bible by
Lidl & Niederreiter has a lot of general theory on factoring
over a finite field.

Cheers,

Jyrki Lahtonen, Turku, Finland
.