
How to factor a polynomial over a number fieldMichael 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]. 