A Modular GCD algorithm over Number Fields presented with Multiple Extensions

The topic of this paper is an algorithm for computing the gcd of two polynomials with coefficients in an algebraic number field. We generalized Encarnacion's algorithm to the case of number fields given by more than one generator, and also simplified the algorithm.

It turned out that a discriminant-test in this algorithm was not necessary. All one needs to do to guarantee that the algorithm works is to avoid primes modulo which the degree of an input polynomial or minimal polynomial decreases. For the case Q[x] one can prove that by showing that the true gcd g, when reduced mod p, is a factor of both f1 mod p and f2 mod p, and hence g mod p divides the modular gcd (the gcd of f1 mod p and f2 mod p). Without a discriminant-test, one can not use this argument for number fields because one does not know if the true gcd can be reduced mod p. But it turned out that one can still obtain the same result with a different argument: Instead of considering g mod p, we take the modular gcd, and Hensel-lift it to characteristic 0. The result is defined over the p-adic numbers, and is of the form ..*f1 + ..*f2. Hence it must be divisible by g. After that one can prove correctness of the algorithm in the same way as is well known for Q[x].

The implementation is also discussed in the paper. To make the algorithm efficient it is important to have a suitable data structure. We also discuss rational reconstruction and trial division issues.

Download this paper.

In the previous version of this paper (FSU preprint 02-03), we also give a generalization of the reduced discriminant, which is not used by our algorithm, but has other useful applications.