<p>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.)</p>

<ol>
<li><p>Deterministic algorithms:</p>

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

<ul>
<li>$\tilde{\mathcal O}\left(\binom{n+d}{n}\right)$ field operations, if fast multiplication algorithms are available.</li>
</ul></li>
</ol>

<p>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. </p>

<p>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.</p>

<p>More details can be found in the paper <strong><a href="http://dx.doi.org/10.1016/j.jsc.2007.01.003">Improved dense multivariate polynomial factorization algorithms</a></strong> of Grégoire Lecerf (<a href="http://lecerf.perso.math.cnrs.fr/publications/Lecerf:2005%3aidmpfa.pdf">link without paywall</a>). </p>

<p>Another reference, especially for fields of small characteristic, is E. L. Kaltofen &amp; G. Lecerf, <strong>Factorization of multivariate polynomials</strong> (<a href="http://www4.ncsu.edu/~kaltofen/bibliography/11/KL11.pdf">link without paywall</a>), chapter 11.5 of G. L. Mullen and D. Panario, editors, <em><a href="http://www.crcpress.com/product/isbn/9781439873786">Handbook of finite fields</a></em>.</p>

<p>¹ The result needs to assume that $\omega&gt;2$.</p>

CC BY-SA 3.0
2013-12-17T14:33:13.087Z
Many thanks! Do you know about any work over very small fields, say GF(2)?
arnab
CC BY-SA 3.0
2013-12-17T15:44:46.087Z
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](http://www4.ncsu.edu/~kaltofen/bibliography/11/KL11.pdf).
Bruno
CC BY-SA 3.0
2013-12-17T10:43:09.913Z
2013-12-17T15:49:40.063Z
2013-12-17T15:49:40.063Z
Bruno
<p>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.</p>

<cc.complexity-theory><algebra><factoring>
Factoring low-degree polynomials
arnab
# Factoring low-degree polynomials

(Asked by: username_0 on 2013-12-17)

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.

**Tags:** cc.complexity-theory, algebra, factoring

---

## 1 answers

### Answer by username_1 on 2013-12-17. Score: 8 | Accepted answer

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](http://dx.doi.org/10.1016/j.jsc.2007.01.003)** of Grégoire Lecerf ([link without paywall](http://lecerf.perso.math.cnrs.fr/publications/Lecerf:2005%3aidmpfa.pdf)).

Another reference, especially for fields of small characteristic, is E. L. Kaltofen & G. Lecerf, **Factorization of multivariate polynomials** ([link without paywall](http://www4.ncsu.edu/~kaltofen/bibliography/11/KL11.pdf)), chapter 11.5 of G. L. Mullen and D. Panario, editors, *[Handbook of finite fields](http://www.crcpress.com/product/isbn/9781439873786)*.

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

> **Comments:**
> **username_0**: Many thanks! Do you know about any work over very small fields, say GF(2)?  
> **username_1**: 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](http://www4.ncsu.edu/~kaltofen/bibliography/11/KL11.pdf).  

---

