A Modular GCD algorithm over Number Fields presented with Multiple Extensions

M. van Hoeij, Michael Monagan

We consider the problem of computing the monic gcd of two polynomials over an algebraic number field L = Q(alpha_1,...,alpha_n). Encarnacion, Langemyr and McCallum have already shown how Brown's modular GCD algorithm for polynomials over Q can be modified to work for Q(alpha).

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.

Our fourth contribution is a generalization of the reduced discriminant to the case n>1. Although not used by our algorithm, it is useful for other algorithms, for example for the computation of the algebraic integers.