What are the most efficient algorithms to factorize a polynomial over integers, knowing that it has only integer roots? I googled around a lot, but most of the work seems to be around Finite fields. Is general factorization NP-hard?
Related question: Suppose I had a Polynomial $H = P + X$, where I knew $H$. I also know $X$ is a natural number, and that $P$ only had integral roots. I get infinite tries at $X$, and every time I guess, I know whether I'm right or wrong. Let's assume for the sake of argument I know that $X$ is from $\{0,1,2,\dotsc,N\}$. Could I improve my guessing of $X$ from knowing $H$ and that $P$ has only integral roots, over randomly guessing new elements from the set $\{0,1,2,\dotsc,N\}$?