Factoring low-degree polynomials

Question

What is the fastest algorithm known for factoring polynomials with $n$ variables and total degree $\leq d$? Here, $n$ is growing and $d$ is fixed. Most work seem to consider the case when $d$ is growing and $n$ is fixed. I am interested in results both over finite fields and over rationals.

Answer 1

Let $\mathbb K$ be a field of characteristic $0$ or at least $d(d-1)+1$, and $p\in\mathbb K[x_1,\dotsc,x_n]$ be a polynomial of total degree at most $d$. If $d$ is fixed and $n$ is growing, one has the following complexity bounds for the reduction of the factorization of $p$ to the factorization of a degree-$d$ univariate polynomial: (The notation $\tilde{\mathcal O}(\cdot)$ ignores logarithmic factors.)

1. Deterministic algorithms:

   • $\tilde{\mathcal O}\left( \binom{n+d}{n}^4 \right)$ field operations, using naive multiplication algorithms;
   • $\tilde{\mathcal O}\left( \binom{n+2d-2}{n-1} d^\omega \right)$ field operations, if fast multiplication algorithms are availaible, where $2<\omega\le 3$ is an admissible exponent for linear algebra.¹

2. Probabilistic algorithms:

   • $\tilde{\mathcal O}\left(\binom{n+d}{n}\right)$ field operations, if fast multiplication algorithms are available.

Then, one has to factorize a univariate degree-$d$ polynomial. The complexity of this step does not depend on $n$ anymore, so the above bounds remain valid for the complete factorization algorithms. The only difference is in positive characteristic: Since no deterministic polynomial-time algorithm is known to factor a univariate polynomial, even the deterministic reduction yield a probabilistic algorithm. Nonetheless, if $d$ is really fixed and small, one can replace the probabilistic polynomial-time algorithm by a deterministic exponential-time one.

Note that the probabilistic bound $\tilde{\mathcal O}\left(\binom{n+d}{n}\right)$ is optimal up to logarithmic factors since $\binom{n+d}{n}$ is the size of the input.

More details can be found in the paper Improved dense multivariate polynomial factorization algorithms of Grégoire Lecerf (link without paywall).

Another reference, especially for fields of small characteristic, is E. L. Kaltofen & G. Lecerf, Factorization of multivariate polynomials (link without paywall), chapter 11.5 of G. L. Mullen and D. Panario, editors, Handbook of finite fields.

¹ The result needs to assume that $\omega>2$.