# Complexity of variant polynomial factorization

Few years back a question on whether a variant of integer factorization was $\mathsf{NP}$ complete was asked, which according to state of mathematics today does not have a conclusive answer.

Is following variant of polynomial factorization, 'given $p(x)\in\Bbb Z[x], l,u\in\Bbb N$, is there a $q(x)\in\Bbb Z[x]$ with $l\leq\mathsf{deg}(q(x))\leq u$ such that $q(x)|p(x)$', $\mathsf{NP}$ complete?

• No, it's in P. Factoring of polynomials over $\mathbb Z$ into irreducible factors (except constant factors) can be done in polynomial-time by LLL, and then the question reduces to checking if a subset of the degrees of the irreducible factors sums to a number between $l$ and $u$, which is easy as they have a unary bound. – Emil Jeřábek Jun 18 '15 at 9:21
• what is an unary bound? – Turbo Jun 18 '15 at 9:33
• A bound that can be written in unary. Here, wlog $u$ is at most the degree of $p$. – Emil Jeřábek Jun 18 '15 at 10:01
• Oh the issue here is we have atmost $O(p)$ distinct degree of factors and checking certain subset of degrees sum in between $l$ and $u$ can be done in $O(p^c)$ time for some fixed constant $c>1$? This is in poly time? – Turbo Jun 18 '15 at 13:03
• en.wikipedia.org/wiki/… – Emil Jeřábek Jun 18 '15 at 13:12