Factoring Polynomials over Algebraic Number Fields

Abstract

We show that if $f(x)$ is a polynomial in $Z [ \alpha ][ x ]$, where $\alpha $ satisfies a monic irreducible polynomial over Z, then $f(x)$ can be factored over $Q(\alpha )[ x ]$ in polynomial time. We also show that the splitting field of $f(x)$ can be determined in time polynomial in ([Splitting field of $f(x): Q $], $\log | (x) |$).