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
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:
postscript file, or
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.