8
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Many thanks! Do you know about any work over very small fields, say GF(2)? $\endgroup$ – arnab Dec 17 '13 at 14:33
  • 3
    $\begingroup$ The bound I mention in my answer are given by algorithms that reduce multivariate factorization to univariate factorization. AFAIK, the best known bounds when the above results do not apply (that is when the characteristic is too small) are given by algorithms that do a reduction multivariate → bivariate → univariate. For more on this, you can have a look to Factorization of multivariate polynomials by Kaltofen and Lecerf, chapter 11.5 of Handbook of finite fields. A preliminary version of this chapter is here. $\endgroup$ – Bruno Dec 17 '13 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.