A Modular GCD Algorithm over Number Fields Presented with Multiple Field Extensions.

Michael Monagan, SFU



We consider the problem of computing the monic gcd g of two polynomials f1 and f2
in the variables x1,x2,...,xm over an algebraic number field L = Q(a1,a2,...,an).
Encarnacion (1995), Langemyr and McCallum (1989) have already shown how Brown's
modular GCD algorithm (1971) for polynomials in Q[x] can be modified to 
work over Q(a1).  Our first contribution is an extenion to the case n>1 without 
converting to a single field extension (which usually causes a blowup).
We have two solutions, one which uses rational reconstruction and one which doesn't.
If we do not use rational reconstruction, then we need to know in advance a multiple
gamma of the denominators appearing in g.
For this we generalize the reduced discriminant of Bradford (1989) to n>1.
If we do use rational reconstruction, we show that it is not necessary to explicitly
test if p divides the (reduced) discriminant.
These results are proven only for L[x] and not for the multivariate case.
We have completed a Maple implementation of Browns' algorithm for the modular
GCD algorithm for the multivariate case assuming it does anyway.
In summary, we have a modular GCD code for Q(a1,a2,...,am)[x1,x2,...,xm].
The code uses the recursive dense data structure being developed at SFU.

In the talk, I will first show how the modular GCD algorithm works for Q[x]
using rational reconstruction, and also without integer reconstruction, by
working through one example.  Then I will show Encarnacions modifications to
the algorithm for Q(a1)[x], and then our modifications for the general case L[x].
I'll show an example of what the data structure looks like for the multivariate
case and a picture of the algorithm executing on a practical problem.

This is joint work with Mark van Hoeij, Florida State University at Talahassee.