Re: factorization in Z_3

In article <1118514235.718070.255040@xxxxxxxxxxxxxxxxxxxxxxxxxxxx> cadaver2@xxxxx writes:
> Li Yi schrieb:
> > 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.
>
> For me too, but Mathematica factors in Z_3 as follows
>
> x^9-x=x*(1 + x)*(2 + x)(1 + x^2)*(2 + x + x^2)*(2+2*x + x^2)

x^9 - x can be found by hand easily enough. Obvious factors are x, x + 1
and x + 2 (= x - 1). Moreover when we factor off x, we find
x^8 - 1 = (x^4 - 1)(x^4 + 1) = (x^2 - 1)(x^2 + 1)(x^4 + 1). So we have
already the following factors:
x, x + 1, x + 2, x^2 + 1.
The remaining factor is x^4 + 1. Trial division leads to the two factors
you give [ (x^2 + x + 2) and (x^2 + 2x + 2) ], there are not many factors
you need to try.

> x^27-x=x*(1 + x)*(2 +
> x)*(1+2*x+x^3)*(2+2*x+x^3)*(2+x^2+x^3)*(2+x+x^2+x^3)*(1+2*x +
> x^2+x^3)*(1 + 2*x^2+x^3)*(1+x +2*x^2+x^3)*(2+2*x+2*x^2+x^3)

x^27 - x is a bit more difficult. You start with a factor x, and get
x^26 - 1. This factors as (x^13 - 1)(x^13 + 1). The first is divisible
by (x + 2) and the second by (x + 1). Dividing off those factors leaves
two 12-th degree polynomials. The first is:
x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
and the second is similar with alternating signs (remember, -1 = 2). So
we will expect pretty similar factorisations (just replace x by -x).

Now I have no idea what information Li Yi is allowed to use. But even with
trial division, you may come up with the answer. I do however suspect that
Li Yi is allowed to use information that is not disclosed to us, otherwise
the question is just horribly time consuming.
--
*** t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~***/
.

Quantcast