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.