I have a homework at algebra, and i don't know where to start. I have to factorize a polynomial in Z3[X] using Berlekamp's algorithm.
The polynomial is: x^5 + 2x^4 + x^2 + x + 1
Can you give me a start and some details about what I should do next. Thanks a lot.
There are a lot of pure algebraists here, but very few applied algebraists. So post the part of the question you do not understand.Quote:
Originally Posted by clarissa
Let p(x) = x^5 + 2x^4 + x^2 + x + 1.
*Is it the first step, where you have to find whether the given polynomial is square free?
You only need to find gcd of p(x) and p'(x). You should know Euclid's Algorithm for that.
*In the second step where you should find the Q matrix?
Find each row separately by reading off the polynomial coefficients of, with i varying from 0 to 4.
Thus you will get a 5 x 5 Q matrix.
*Finding a basis for null space of Q-I?
This is done by reducing Q-I to row echelon form. Then we can simply read the basis off the matrix.
*Once we get the basis, are you finding it difficult to convert it to polynomial form and get the factorization?
First convert each of the basis vector to polynomial form. Say the basis polynomials are, then for each s starting from s = 0 to p-1, find
, which is the non-trivial factorization of p(x)
I did not compute the whole problem, because I find it painful to work out Q. If you tell me Q, we can work out the remaining details.
Until now I computed:
1) f' = 5x^4 + 8x^3 + 2x + 1 = 2x^4 + 2x^3 + 2x + 1
2) (f, f') = 1 => f is square free
3)
k=0, x^0 = 1
k=1, x^3 = x^3
k=2, x^6 = x^4 + 2x^3 + x^2 + 2
k=3, x^9 = x^4 + x^3 + x^2 + 2x + 2
k=4, x^12 = x^4 + 2x^3 + x
So Q should be
1 0 2 2 0
0 0 1 2 1
0 0 1 1 0
0 1 2 1 2
0 0 1 1 1
???
I've recalculated the ecuations:
k=0, x^0 = 1
k=1, x^3 = x^3
k=2, x^6 = x^4 + 2x^3 + x^2 + 2 = x^4 - x^3 + x^2 - 1
k=3, x^9 = x^4 + x^3 + x^2 + 2x + 2 = x^4 + x^3 + x^2 - x -1
k=4, x^12 = x^4 + 2x^3 + x = x^4 - x^3 + x
to get a simpler form
I get the matrix
Q=
1, 0, -1, -1, 0
0, 0, 0, -1, 1
0, 0, 1, 1, 0
0, 1, -1, 1, -1
0, 0, 1, 1, 1
and i've reduced it to the echelon form:
and i get that Q=I5
Can you help me continue please..