  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 may lead to
NP-complete problems in the strong sense. In particular, given any constant
value k in 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 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.
