A Sparse Modular GCD Algorithm for Number Fields and Finite Fields
Jennifer de Kleine
We extend the sparse modular GCD algorithm of Zippel to work over finite fields and algebraic number fields. Our algorithm supports multiple field extensions. We have done an implementation in the new recursive dense polynomial data structure "recden" in Maple. Our implementation works for monic polynomials over the rationals, finite fields and number fields and we are currently working on handling the non-monic case.