Is factoring polynomials as hard as factoring integers?

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.

As was mentioned there are (theoretical) polynomial time algorithms for factoring polynomials such as LLL. However, they do not perform well in practice, so various other algorithms are typically employed (e.g. Berlekamp, Zippel's sparse modular, etc). For some references see my answer to a prior question here on the best ways to factor polynomials.

The method you propose seems related to an old method due to Bernoulli, Schubert, Kronecker, Hausmann, et al. You can find a nice presentation of this algorithm with worked examples in Sec.16.1 pp. 347ff in: Mora. Solving polynomial equation systems, I. The Kronecker-Duval Philosophy. This may be accessible by Google books. To find said section quickly simply search for "Schubert". See also Mignotte's interesting paper [2] on the history (abstract appended below).

ABSTRACT. The First General Method of Factorization of Polynomials.
On a Memoir of F.T. Schubert.

We analyse two little known papers of N. Bernoulli (1708) and F.T. Schubert (1794) on the factorization of integer polynomials as well as the work of L. Kronecker and B.A. Hausmann on the same topic. The factorization method of Bernoulli-Schubert uses the calculus and the interpolation of finite differences. It was rediscovered by Kronecker (1882), who used Lagrange interpolation. Both procedures allow the effective factorization of polynomials having small degrees and coefficients. An algorithm combining the results of Bernoulli-Schubert and Kronecker was obtained by B.A. Hausmann. His method is particularly useful for the factorization of stable polynomials. The three methods are briefly compared with modern factorization algorithms.

[1] Edwards, H. Kronecker's Algorithmic Mathematics
(Presented at "Computability in Europe 2008," Athens, June 19, 2008.)
http://www.math.nyu.edu/faculty/edwardsd/athens.pdf

[2] Maurice Mignotte; Doru Stefanescu
La première méthode générale de factorisation des polynômes.
Autour d'un mémoire de F.T. Schubert
Revue d'histoire des mathématiques 7, fascicule 1 (2001), 67-89
http://smf4.emath.fr/Publications/RevueHistoireMath/7/html/smf_rhm_7_67-89.html