As you correctly states it, your question is not completely well-defined. Actually, two quite different problems have been studied a lot: factorization of *dense* polynomials and of *sparse* polynomials. These two problems differ by the input they receive. This is especially relevant for univariate polynomials.

**Factorization of dense polynomials** is the problem of given a sequence $[a_0,\dotsc,a_n]$, factorize $P(X)=\sum_{i=0}^n a_i X^i$.
**Factorization of sparse polynomials** is the problem of given a sequence of couples $[(a_0,d_0),(a_1,d_1),\dotsc,(a_n,d_n)]$, factorize $P(X)=\sum_{i=0}^n a_i X^{d_i}$.

Clearly, in the sparse version, your polynomials can have large degrees (exponential in the size of the input) while in the dense version, the degree is bounded by the size of the input. This is why the dense case is pretty well understood (for univariate as well as for multivariate polynomials) whence in the sparse case only some partial results are known.

A good way to know what has been done on the subject is to have a look to Erich Kaltofen's publications on this subject. You'll find his results and of course the relevant literature in the references. He also has several surveys on polynomial factorization, you can in particular have a look to the most recent one (2003).