Results 1 to 2 of 2

Math Help - Polynomial factorization algortihms

  1. #1
    Junior Member
    Joined
    Aug 2009
    From
    Brisbane, Australia
    Posts
    31

    Polynomial factorization algortihms

    Hi,

    I want to write a computer program that takes a univariate polynomial of any degree with rational coefficients, and factorizes it into smaller polynomials. I am only interested in factorizing it into a product of polynomials with rational coefficients. Can someone tell me what is the best algorithm (or algorithms) to use, and be able to explain them simply?

    My approach would probably start by making sure the polynomial is in standard form, removing 'obvious' factors (eg. 10x^4 + 5x^2 + 20x = 5x(2x^3 + x + 4)), and converting the rational coefficients to integer coefficients (eg. 5/3x^2 + 7/2x = 1/6(10x^2 + 21x)). This would leave me with a polynomial with coprime integer coefficients.

    From here, I could use the rational roots test and long division to find the linear factors of the polynomial.

    It is from here on that I'm not quite sure what to do. There maybe cases where the polynomial can be factorized into non-linear polynomials. I know that there exists algorithms, but the details are either too sketchy to implement, or use math terminology that is way over my head, and I can't follow the explanation. I think Berlekamp and Cantor-Zassenhaus are examples. It would be good if someone could point me to a good explanation of how these algorithms work in plain English (or even pseudocode or an example piece of code that has already been written).

    Cheers.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Polynomial factorization algortihms

    Yes, you have to consider cases where the polynomial has non-real roots and therefore, cannot factor into linear polynomials with real coefficients.

    Factoring a polynomial is equivalent to finding the zeros of the polynomial, e.g. x-r is a factor if and only if r is a root. So if you've got a good method to find the roots of a polynomial (I'm not a computer geek, but Newton's method?) then you're all set.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Factorization of the polynomial
    Posted in the Algebra Forum
    Replies: 5
    Last Post: August 1st 2011, 10:27 PM
  2. Factorization of the polynomial
    Posted in the Algebra Forum
    Replies: 5
    Last Post: December 1st 2010, 08:13 PM
  3. Polynomial Unique Factorization
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 9th 2010, 06:20 AM
  4. Polynomial factorization
    Posted in the Algebra Forum
    Replies: 2
    Last Post: February 22nd 2010, 11:03 AM
  5. Replies: 3
    Last Post: June 27th 2008, 12:26 AM

Search Tags


/mathhelpforum @mathhelpforum