# Algorithms for factoring multivariate polynomials

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.

-

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.
First line on wikipedia page: In computational algebra, the Cantor–Zassenhaus algorithm is a well known method...'' I guess I have a little reading-up to do! Thank you! – Ruben Mar 9 '14 at 4:27
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.