This ISSAC'2004 paper is presented with just one algebraic extension, defined by a minimal polynomial m. There are no mathematical reasons for this restriction, the reasons for these were: notational convenience, and the fact that we only implemented (at the time at least) the one-extension case in the function field case. The proof of Theorem 1 + 2 would be identical in case of multiple extensions (see also the ISSAC'2002 paper on the multiple-extension case). The algorithms are implemented by Michael Monagan and are now part of Maple. As a result, gcd's over algebraic extensions are now much faster (see link in file COMMENT_Maple11).

Note that Theorem 1 + 2 and the proof are also valid in case of reducible minimal polynomial(s).

There is now also a paper that treats the sparse case as well, see:

Seyed Mohammad Mahdi Javadi, Michael B. Monagan: A sparse modular GCD algorithm for polynomials over algebraic function fields. ISSAC 2007: 187-194

The algorithm in this ISSAC'2007 paper works well in the sparse as well as in the dense case; it is the best algorithm for computing polynomial gcd's.