A modular GCD algorithm over number fields presented with multiple extensions
Mark van Hoeij, Michael Monagan · International Symposium on Symbolic and Algebraic Computation · 2002
We consider the problem of computing the monic gcd of two polynomials over a number field L = ℚ(α1,…,αn). Encarnacion, Langemyr and McCallum have already shown how Brown's modular GCD algorithm for polynomials over ℚ can be modified to work for ℚ(α).Our first contribution is an extension of Encarnacion's modular GCD algorithm to the case n > 1 without converting to a single field extension. Our second contribution is a proof that it is not necessary to test if p divides the discriminant. This simplifies the algorithm; it is correct without this test.Our third contribution is the design of a data structure for representing multivariate polynomials over number fields with multiple field extensions. We have a complete implementation of the modular GCD algorithm using it. We provide details of some practical improvements.
Cited by 31 works. doi:10.1145/780506.780520
Authors
References
- Probabilistic algorithms for sparse polynomials
- On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
- Lectures on the Theory of Algebraic Numbers
- P-adic reconstruction of rational numbers
- The Bath algebraic number package
- Computing GCDs of Polynomials over Algebraic Number Fields
- The computation of polynomial greatest common divisors over an algebraic number field
- A modular GCD algorithm over number fields presented with multiple extensions
- On the design and implementation of Brown's algorithm over the integers and number fields
- Some results on the defect