A modular GCD algorithm over number fields presented with multiple extensions
Mark van Hoeij, Michael Monagan · 2002
We consider the problem of computing the monic gcd of two polynomials over a number field L = ℚ(α1,…,αn). Encarnacion, Langemyr and McCallum have already shown how Brown's modular GCD algorithm for polynomials over ℚ can be modified to work for ℚ(α).Our first contribution is an extension of Encarnacion's modular GCD algorithm to the case n > 1 without converting to a single field extension. Our second contribution is a proof that it is not necessary to test if p divides the discriminant. This simplifies the algorithm; it is correct without this test.Our third contribution is the design of a data structure for representing multivariate polynomials over number fields with multiple field extensions. We have a complete implementation of the modular GCD algorithm using it. We provide details of some practical improvements.