Gcd computation over algebraic function fields.
Mahdi Javadi, MITACS
Abstract: We will present SparseModGcd, an algorithm which computes polynomials gcds over an algebraic function field with multiple field extensions using sparse interpolation. Our algorithm is an extension to Monagan and van Hoeij's ModGcd algorithm which uses dense interpolation and supports one field extension. We will show that SparseModGcd is more efficient when the gcd of the inputs is sparse. It is also competetive to ModGcd for dense polynomials.