On A Modular Algorithm For Computing GCDs Of Polynomials Over Algebraic Number Fields

Modular methods for computing the gcd of two univariate polynomials over an algebraic number field require a priori knowledge about the denominators of the rational numbers in the representation of the gcd. We derive a multiplicative bound for these denominators without assuming that the number generating the field is an algebraic integer. Consequently, the gcd algorithm of Langemyr and McCallum [J. Symbolic Computation, 8:429-448, 1989] can now be applied directly to polynomials that are not necessarily represented in terms of an algebraic integer. Worst-case analyses and experiments with an implementation show that by avoiding a conversion of representation the reduction in the computing time can be significant. We also suggest the use of an algorithm for recovering a rational number from its modular residue so that the denominator bound need not be computed explicitly. Experiments and analyses indicate that this is a good practical alternative.