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.