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.