A Sparse Modular GCD Algorithm for Polynomials over Algebraic Function Fields

We present a first sparse modular algorithm for computing a greatest common divisor of two polynomials f1, f2 ∈ L[x] where L is an algebraic function field in k ≥ 0 parameters with r ≥ 0 field extensions. Our algorithm extends the dense algorithm of Monagan and van Hoeij from 2004 to support multiple field extensions and to be efficient when the gcd is sparse. Our algorithm is an output sensitive Las Vegas algorithm. We have implemented our algorithm in Maple. We provide timings demonstrating the efficiency of our algorithm compared to that of Monagan and van Hoeij and with a primitive fraction-free Euclidean algorithm for both dense and sparse gcd problems