How to factor a polynomial over a number field

Michael Monagan, CECM

Let k be an algebraic number field and let f(x) be a polynomial in k[x].
How can we factor f(x) into irreducible factors over k?
For example, how would we factor the polynomial

                                5    4  1/2      3          1/2
                        f(x) = x  - x  2    - 2 x  + 3 x + 2

where k = Q(sqrt(2)).  I will explain the idea behind an algorithm of
Barry Trager from 1976.  The algorithm reduces factorization over k to
factorization of a polynomial g over Q where the deg[x](g) = deg[x](f)*deg(k:Q).
I will develop Trager's algorithm from properties of resultants and talk about
the complexity of each of the three main steps in the algorithm, namely:

     (i) computing resultants in Q[x,y],
    (ii) factoring polynomials over Q, and
   (iii) computing polynomial GCDs in k[x].