Results 1 to 4 of 4

Math Help - Factorization of a polynomial in Z3[X] with Berlekam's algorithm.

  1. #1
    Newbie
    Joined
    Jun 2008
    Posts
    4

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by clarissa View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2008
    Posts
    4
    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

    ???
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jun 2008
    Posts
    4
    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..
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Index calculus algorithm, -1 in factorization
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 8th 2011, 01:36 PM
  2. Factorization of the polynomial
    Posted in the Algebra Forum
    Replies: 5
    Last Post: August 1st 2011, 10:27 PM
  3. Factorization of the polynomial
    Posted in the Algebra Forum
    Replies: 5
    Last Post: December 1st 2010, 08:13 PM
  4. Polynomial factorization
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 22nd 2010, 11:03 AM
  5. LU-Factorization Algorithm??
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 11th 2007, 09:40 PM

Search Tags


/mathhelpforum @mathhelpforum