Factoring Polynomials

[Glass]

Hey everyone,

I was looking at another thread about factoring polynomials, and now I'm wondering if anyone knows any unusual or cool ways to factor them (i.e. not using numerical techniques such as Newton's Method). Unfortunately the only one I do know is the rational root theorem...

 

[mathPimpDaddy]

look up pascal's triangle.

 

[Glass]

look up pascal's triangle.

I do know what Pascal's Triangle is, but I'm not seeing how it would help me factor a polynomial. Unless I happen to notice it's coefficients are the binomial coefficients. Am I missing something here?

 

[Gib Z]

You not missing anything there, that's exactly what he meant. Sure its not the most general method, but it works on rare occasions.

Check out https://www.physicsforums.com/showthread.php?t=166834, post 7, to see how I factored that polynomial. It works everytime, its just that when the first and last terms aren't perfect squares like in that case, its harder to solve.

 

[Gib Z]

O And here's One I thought of that's not going to apply that often, but it could.

I know that If we have a polynomial and we know one of the roots is repeated twice, like in (x-1)^2, then the derivative of the polynomial will have the same root.

So reversing that, if you find a polynomial whose integral is a polynomial you know how to factorize, bingo.

 

[Werg22]

There's no general way to factor polynomials since this would go against Galois's theory.

 

[Hurkyl]

There's no general way to factor polynomials since this would go against Galois's theory.

That's certainly not true. If that were so, then how could computers factor?

Two general methods I know off the top of my head for factoring polynomials over the integers in one variable are:
(1) Numerically obtain a complex root with enough accuracy, then use lattice techniques to find the minimal polynomial of that root, which is then a factor of your polynomial.
(2) Factor your polynomial modulo p for enough small primes p, then use the Chinese Remainder Theorem (and a small search) to construct factors of your integer polynomial.

 

[Gib Z]

No Algebraic Method Werg22 should have said then :)

 

[mathwonk]

there is an algebraic method for factoring polyn omials over say the integers, or rationals.

notice that if f = gh, then for every a, f(a) = g(a)h(a), i.e. every value of f is factored by the correponding values of g and h.

moreover a polynomial of degree n is determined by the values at n+1 integers.

so if f has degree n take any n+1 integers, and evaluate f at all of them,. that gives you n+1 values of f.

for each of these values take all of its possible integer factorizations. this gives you all possible values of both g and h at all these n+1 integers. then use lagrange interpolation to construct all possible pairs g,h having these values.

then try them all to see if any of these factorizations work.

if none of these work, then f is irreducible.

yes it is a lengthy and tedious method, but it IS algebaric and does always work,

this crude method is due to kronecker. and appears in van der waerden, and the harvard notes of richard brauer.

obviously improvements are possible, but this shows it is possible to factor polynomials over any ring of coefficients in which one can already factor.

 

[mathwonk]

let me give an example. suppose you have a quartic polynomial f over Z you wish to factor. if it has non constant factors over Q then it has non constant factors over Z.

the root factor theorem suffices to find all linear factors, as they correspond to rational roots which correspond to quotients of integer factors of the constant term and lead term.

so we seek quadratic factors g,h such that f = gh. such a factor is determined by its values at any three distinct points, so choose three distinct integers and evaluate the original polynomial f at those points.

assume for extreme simplicity that you always get the value 1. then both factors g,h must have value 1 or -1 at each point, and thus in fact g =h.

so there are 8 possibilities for g=h, namely it haS EITHER VALUES 1,1,1 or -1,-1,-1, or 1,-1,-1, or -1,1,1, or 1,1,-1, or -1,-1,1, or 1,-1,1, or -1,1,-1,

at those three points. this gives by lagrange interpolation, only 8 possible pairs of factors. either they work or they do not. that's it.

what do you think of this?

 

[mathwonk]

since the method above is very old, does anyone have any newer versions to report? ones which perhaps are actually in use by computer factoring programs?

 

[Crosson]

ones which perhaps are actually in use by computer factoring programs?

For univariate polynomials, Mathematica uses a variant of the Cantor‐Zassenhaus algorithm to factor modulo a prime, then uses Hensel lifting and recombination to build up factors over the integers.

Factoring over algebraic number fields is done by finding a primitive element over the rationals and then using Trager's algorithm.

For multivariate polynomials Mathematica works by substituting appropriate choices of integers for all but one variable, then factoring the resulting univariate polynomials, and reconstructing multivariate factors using Wang's algorithm.

 

[matt grime]

There's no general way to factor polynomials since this would go against Galois's theory.

Galois theory states that there is no way to write down the *roots* of an arbitrary poly as certain functions of its coefficients.

 

[mathwonk]

crosson, your explanations leave a bit to be desired, in the details. can you be a bit more self contained?