I'm trying to implement the algorithm for factoring polynomials over number fields on page 145 of Henri Cohen's A Course on Computational Algebraic Number Theory, but I'm not sure how the application of the sub-resultant GCD algorithm in the first step is supposed to work.
The sub-resultant algorithm is presented as being for polynomials over UFD's. I'm aware that fields are UFD's, but given that the algorithm calls for taking GCD's between coefficients of the polynomials, it seems like it only makes sense for UFD's that aren't also fields.
Isn't every nonzero element of a field a GCD of every other, and wouldn't that render all such GCD calculations in the algorithm pointless?
My first thought is that applying the sub-resultant algorithm to polynomials over number fields is to be analogous to applying it to polynomials over the rationals, though before I pursue that too far I want to make sure I understand that case correctly as well. To apply it to polynomials over the rationals, you multiply each by the lcm of the denominators of its coefficients in order to get an integer polynomial, and apply it to those instead.
If that's right, is the equivalent for polynomials over number fields multiplying each polynomial by an element of the field such that the coefficients all end up in the field's ring of integers?
I'm not sure how to do that. For what it's worth, I have the minimal polynomial of a primitive element of the number field on hand, and am representing elements of the field as rational polynomials in terms of the primitive element. I understand that the reason to use the sub-resultant algorithm rather than the basic Euclidean algorithm for rational polynomials is that being able to restrict the coefficients to the integers saves the work of having to reduce fractions every time one operates on them. In the number field case, on the other hand, if algebraic integers are more efficient to operate on than arbitrary field elements, I'm not clear on the concrete reason why, unless it happens that each coefficient can be represented using an integer polynomial rather than a rational one.
Edit: Multiplying the polynomials by field elements that bring the coefficients into the field's ring of integers can't be the intention, because the sub-resultant algorithm is for polynomials with coefficients over a UFD, while the ring of integers of a number field is not always a UFD.