Yes, you have to consider cases where the polynomial has non-real roots and therefore, cannot factor into linear polynomials with real coefficients.

Factoring a polynomial is equivalent to finding the zeros of the polynomial, e.g. x-r is a factor if and only if r is a root. So if you've got a good method to find the roots of a polynomial (I'm not a computer geek, but Newton's method?) then you're all set.