27 June, 2017: Polynomial Factoring Algorithm

Polynomial Factoring

Polynomial factoring can be a pain, even for people experienced with it. Need to factor anything larger than a quadratic? I sure don't want to, it’s a pain trying to find that first factor. There are algorithms to find it though, and they are able to be implemented in your programming language of choice. So I did.

This is a polynomial factoring algorithm I created using python. It will take any polynomial of up to degree 20 (limited to stop the program from passing default timeout periods), and factor it into the form (ax+b). It will NOT accept or factor partially factorable polynomials, or polynomials that have factors that aren't in the form (ax+b). The actual algorithm makes use of Zero Remainder Theorem, Synthetic Division, and Factor Theorem.

How it works:

The script first will store each polynomial as a list of coefficients. For instance x3 + 4x2 + 5x + 2 will be represented by [1, 4, 5, 2]. The second step is to choose a list of possible factors, and by using Factor Theorem, we can see all possible factors will be any factor of the constant (2) over any factor of the leading coefficient (1). In this case that means possible factors are 1 or 2.

Checking a factor makes use of the Zero Remainder Theorem, implying that any factor (x - p), when x = p, the polynomial will equal zero. If the factor is a success, the script uses a neat little synthetic division algorithm to divide away the factor, then multiply out to get rid of all the fractions. Once that is done, rinse and repeat until the list of coefficients is two long, indicating that the polynomial is fully factored.


Enter degree: