多項式の因数分解アルゴリズムで実装が簡単なのは何だろう。 http://en.wikipedia.org/wiki/Factorization_of_polynomials の Kronecker's method
?