There seems to be a consensus that factorization of integers is hard (in some precise computational sense.) Is it known whether polynomial factorization is computationally easy or hard?
One thing I originally thought was that if we could factor polynomials easily, then we could factor $n$ by finding a polynomial $p(x)$ with $p(m)=n$ for some $m$, then "easily factorizing" $p$ to get $p(x)=q(x)\cdot r(x)$. Then $q(m)\cdot r(m)$ would be a factorization of $n$. But we wouldn't get any information if one of these happened to be 1.
Does anyone have a solution or a reference for this problem? (I searched online, but all I could find was how to do factorization like in high school problems.)
There is a polynomial time algorithm for factoring polynomials with rational coefficients (the LLL algorithm of Lenstra, Lenstra, and Lovasz), so factoring polynomials over the rationals is known to be "easy" (polynomial time is considered to make the problem "computationally easy", even if in practice it does not perform well). Of the known methods for factoring general integers, on the other hand, the best is the General number field sieve, which is believed to be super-polynomial and sub-exponential (the complexity of the algorithm is estimated heuristically), which is worse.
In general, this kind of problem tends to be easier for polynomials than for integers, thanks to the existence of the derivative. Thus, there is a fairly easy proof of "FLT for polynomials" (about one page long); it is trivial to detect if a polynomial is squarefree (and no such easy algorithm is known for integers), and so on.
Your idea for factoring integers with polynomials is very natural, but unfortunately fails in both directions: not every factorization of $n$ would be detected by a factorization of $p(x)$, and not every factorization of $p(x)$ would give a factorization of $n$. For example, $p(x) = x^2+x+1$ is irreducible over $\mathbb{Q}$ (even over $\mathbb{R}$), but $p(10) = 111 = 3\times 37$, so this factorization cannot be "detected" by factoring $p(x)$. On the other hand, $q(x) = x^4 - 1 = (x-1)(x^3+x^2+x+1)$ would not detect factors of $q(2)=15$. If you have to start rummaging around for polynomials, trying several to see if you can detect a nontrivial factorization, even if you eventually "hit" on one that gives the answer the ease of factoring the polynomial may be overshadowed by the difficulty in finding a "good" polynomial in the first place, so that the entire thing may be a wash.