On Computing Univariate GCDs over Number Fields

Monagan, Michael and Margot, Roger (1996) On Computing Univariate GCDs over Number Fields. [Preprint]

Download (106Kb) | Preview
    Download (105Kb) | Preview


      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.

      Item Type: Preprint
      Additional Information: pubdom FALSE
      Subjects: 00-xx General
      Faculty: UNSPECIFIED
      Depositing User: Users 1 not found.
      Date Deposited: 22 Mar 2005
      Last Modified: 21 Apr 2010 11:13

      Actions (login required)

      View Item