Computing univariate GCDs over number fields
Michael Monagan, Roger Margot · 1998
We compare the two main competing methods for fast univariate polynomial GCD computation over an algebraic number field, namely, the modular method of Langymyr et al (1987), and the heuristic method of Smedley et al (1988). Because of recent improvements to the modular method by Encarnacion (1994), we expected that the modular method, if implemented “properly”, would now be the method of choice in Maple. This turned out to be the case for several kinds of GCD problems. As an exercise, to complete the comparison, we implemented also a Hensel based method. We then realized that Hensel lifting is “pointless ” when applied to univariate GCD computation and implemented a more direct method that we call the prime-power method. It turns out that not only is the prime-power method simple to implement, it is also better than the heuristic method. Due to the large effort required to implement the modular method “properly”, we recommend that the prime-power method to systems ' implementors as a very good choice. We also use the prime-power method to improve polynomial trial division which is the bottleneck in some GCD computations.