Algorithms for factoring multivariate polynomials

Question

I am wondering if there are any algorithms to factor polynomials in multiple variables, when you know that the factors are other polynomials with rational or integer coefficients.

I know you have the rational root theorem, which helps out a lot, but it isn't always obvious how to apply this. Suppose we have the expression $$ 2y^6 - 5x^6 + x^5y^5 - 10xy $$

(I deliberately choose factors with x and y in high powers, to avoid the solutions being solving by completing the square, Cardano's formula, or Ferrari's formula)

This case might be doable: the powers in the terms suggest terms of $x^5$ and $y^5$ and $x$ and $y$, so with a little inspection one might expect the factorization to be of the form $(ax^5+by)(cy^5+dx)$. The term $x^5y^5$ suggests $a=c=1$ and from there it's almost trivial (you can use the rational root theorem, but I don't think that is even necessary).

It seems to be doable in this case, which makes it plausible that there is an algorithm who does something like this. Also, I was wondering about another specific case, in just one variable: $$ (x - a)(x - b)(x - c) $$

With $a, b, c$ integers with a very large absolute value. You can't use Cardano for this (casus irreducibilis), and in order to use the rational root theorem, you need to factorize abc, a very large number (which is very slow).

Besides, using the rational root theorem would not make use of the information that the values $a + b + c$ and $bc + ac + ab$ are also known (because they are coefficients in the polynomial).

One trivial algorithm I can come up with is to enumerate all polynomials (we do this by enumerating their coefficients, and integers and rationals are countable, so we can do this) with powers equal to or lower than the powers in the original polynomial, and try if long division yields a rest term (if not, we found a factor). Of course, this is too slow to be practical, but this and the fact that Wolfram Alpha can usually find the factorization of complicated polynomials (though I haven't tried this thoroughly), suggests there is at least one algorithm to do this in a more or less practical way.

Answer 1

There are algorithms for factoring univariate polynomials with integer coefficients like the Zassenhaus algorithm that reduces the problem modulo small primes and then uses Hensel-lifting to probe for the integer factors, and for which modular factors have to be combined. Or the LLL based factorization algorithm that looks for the minimal polynomial of a numerically with high precision computed root.

So chose a random small to medium integer $m$ to replace $y$, perform univariate factorization and apply Hensel lifting modulo powers of $(y-m)$ to the factors. Again, if after the lifting there remain factors with too high a degree, look for combinations of them that are proper factors.

Answer 2

You can view $2y^6−5x^6+x^5y^5−10xy$ as a polynomial in $y$. So write it as $$2y^6+x^5y^5-10xy−5x^6$$ This polynomial in $y$ has coefficients in $\mathbb{Z}[x]$. The constant term (with respect to the variable $y$) is $-5x^6$ If the polynomial is not irreducible it hast at least one factor of degree 1,2 or 3 with respect ot the variable y. if it has a factor of degree 1 this factot has the form $y-f(x)$ with $f(x) in \mathbb{Q}[x]$. But we know even more about $f(x)$ it must have the structure $f(x)=\frac{p(x)}{q(x)}$ with $p(x) \in \mathbb{Z}[x]$ and $q(x) \in \mathbb{Z}[x]$ and and $p(x)$ is a divisor of the constant term $-5x^6$ of the polynomial and $q(x)$ is a divisor of the coefficient $2$ of the leading term of the polynomial. So $p(x)$ must be form the set $\{ a x^k, a \in \{\pm 1, \pm 5\}, k \in \{0,1,2,3,4,5\}\}$. Actually $-\frac{x^5}{2}$ is a zero of the polynomial so $2y+x^5$ is a factor and we have $$(2y+x^5)(y^5-5x)$$ Checking with the same method the factor $y^5-5x$ one will see that it has no zero and therefore no linear factors. But maybe it has higher degree factors.

Some details can be found in Factorize the polynomial x3+y3+z3−3xyz. Another example calculated with this method is Factoring multivariate polynomial