Results 1 to 2 of 2

Thread: Polynomial factorization algortihms

  1. #1
    Junior Member
    Aug 2009
    Brisbane, Australia

    Polynomial factorization algortihms


    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).

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Jun 2012

    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: Aug 1st 2011, 09:27 PM
  2. Factorization of the polynomial
    Posted in the Algebra Forum
    Replies: 5
    Last Post: Dec 1st 2010, 07:13 PM
  3. Polynomial Unique Factorization
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Aug 9th 2010, 05:20 AM
  4. Polynomial factorization
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Feb 22nd 2010, 10:03 AM
  5. Replies: 3
    Last Post: Jun 26th 2008, 11:26 PM

Search Tags

/mathhelpforum @mathhelpforum