Factorization of a polynomial in Z2.
I know x+1 is one of the factors, but how do I go about finding the rest?
Math wizards, I know you're out there somewhere.
divide the polynomials in Z2
I think
I think that there is only one factorization since Z2 is a field.
So we have x+1 as a factor and divide x^12 + 1 by it.
x^12 + 1 = (x + 1)(x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1) = (x + 1)p(x)
Since the number of summands in p(x) is even, p(1) = 0 and (x+1) is again a factor.
p(x) = (x+1)(x^10 + x^8 + x^6 + x^4 + x^2 + 1) = (x+1)q(x)
and again
q(x) = (x+1)(x^9 + x+8 + x^5 + x^4 + x + 1) = (x+1)r(x)
and again
r(x) = (x + 1)(x^8 + x^4 + 1) = (x + 1)s(x)
Now we need to check s(x) for quadratic factors. The only irreducible quadratic factor is x^2 + x + 1 since x^2 = x x, x^2 + 1 = (x+1)(x+1), x^2 + x = x(x + 1).
x^8 + x^4 + 1 = (x^2 + x + 1)(x^6 + x^5 + x^3 + x + 1)
x^7 + x^6 + x^4 + 1
x^5 + x^4 + 1
x^3 + 1
x^2 + x + 1
0
So x^2 + x + 1 is another factor, and again:
x^6 + x^5 + x^3 + x + 1 = (x^2 + x + 1)(x^4 + x^2 +1)
Since (x^2 + x + 1)^2 = x^4 + x^2 + 1 we have finished.
x^12 + 1 = (x + 1)^4 (x^2 + x + 1)^4
>>75442
The last step can be simplified:
Since (x^2 + x + 1)^2 = x^4 + x^2 + 1 = z^2 + z + 1 for z = x^2:
s(x) = x^8 + x^4 + 1 = z^4 + z^2 + 1 = (z^2 + z + 1)^2 = ((x^2 + x + 1)^2)^2 = (x^2 + x + 1)^4
>>75185
(x^12+1)
(x^6+1)(x^6+1)
(x^3+1)(x^3+1)(x^6+1)
(x^3+1)(x^3+1)(x^3+1)(x^3+1)
(x+1)(x^2+x+1)(x^3+1)(x^3+1)(x^3+1)
(x+1)(x^2+x+1)(x+1)(x^2+x+1)(x^3+1)(x^3+1)
(x+1)(x^2+x+1)(x+1)(x^2+x+1)(x+1)(x^2+x+1)(x^3+1)
(x+1)(x^2+x+1)(x+1)(x^2+x+1)(x+1)(x^2+x+1)(x+1)(x^2+x+1)
>>75442
>>75583
Thanks, anons.
Wasn't sure I was doing it right.
What about x^5-2x4+x3-2x2+x-2 mod 3, 5 or 7?
Z3 for example, f(1) = -3 = 0 and f(2) = 0. So x+1 and x+2 are factors. I divide and get the quotient, but it doesn't divide by these factors anymore.
It ends up factoring to (x+1)^3(x+2)^2 mod 3 somehow but I don't know how to get there.
>>75718
I would first multiply the two factors:
(x+1)(x+2) = x^2 + 3x + 2 = x^2 + 2 (mod 3)
and then divide:
x^5 - 2x^4 + x^3 - 2x^2 + x - 2 =
x^5 + x^4 + x^3 + x^2 + x + 1 =
(x^2 + 2)(x^3 + x^2 - x - 1)
and again:
x^3 + x^2 - x - 1 = (x^2 + 2)(x + 1)
f(x) = (x^2 + 2)^2(x + 1) = (x+2)^2(x+1)^3
>>75786
A more general solution is to factorize f(x) in the integers and then look at the factors modulo 3,5,7:
x^5 - 2x^4 + x^3 - 2x^2 + x - 2 =
(x - 2)(x^4 + x^2 + 1)
Since x^4 + x^2 + 1 > 0 there are no further zeros in Z which means that x^4 + x^2 + 1 can only be the product of two irreducible quadratic functions or be irreducible itself.
(x^2 + ax + 1)(x^2 + bx + 1) = x^4 + (a+b)x^3 + (ab+2)x^2 +(a+b)x + 1
Since a+b = 0, b = -a which implies ab+2 = -a^2 + 2 = 1, that is, a = +-1 and b = -+1
f(x) = (x-2)(x^2 + x + 1)(x^2 - x + 1)
Now you can check the quadratic functions modulo 3,5,7.