A sparse modular GCD algorithm for polynomials over algebraic function fields
Seyed Mohammad Mahdi Javadi, Michael Monagan · 2007
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.