# Factorization of a polynomial in Z3[X] with Berlekam's algorithm.

• Jun 25th 2008, 05:52 AM
clarissa
Factorization of a polynomial in Z3[X] with Berlekam's algorithm.
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.
• Jun 25th 2008, 08:01 AM
Isomorphism
Quote:

Originally Posted by clarissa
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.

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 $x^{ip} \mod p(x)$, 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 $b_1(x),b_2(x),...,b_k(x)$, then for each s starting from s = 0 to p-1, find $(p(x), b_2(x)-s)$ , 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.
• Jun 25th 2008, 09:24 AM
clarissa
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

???
• Jun 27th 2008, 12:26 AM
clarissa
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..