The 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).
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.