Hard to Detect Factors of Univariate Integer Polynomials

We investigate the computational complexity of deciding whether a given univariate integer polynomial p ( x ) has a factor q ( x ) satisfying specific additional constraints. When the only constraint imposed on q ( x ) is to have a degree smaller than the degree of p ( x ) and greater than zero, the problem is equivalent to testing the irreducibility of p ( x ) and then it is solvable in polynomial time. We prove that deciding whether a given monic univariate integer polynomial has factors satisfying additional properties is NP-complete in the strong sense. In particular, given any constant value k ∈ Z , we prove that it is NP-complete in the strong sense to detect the existence of a factor that returns a prescribed value when evaluated at x = k (Theorem 1) or to detect the existence of a pair of factors—whose product is equal to the original polynomial—that return the same value when evaluated at x = k (Theorem 2). The list of all the properties we have investigated in this paper is reported at the end of Section Introduction.