To use the code you need to read in these files.

recden - data structure an utility file
PGCD - compute GCD over characteristic p
AGCD - split field extensions of low degree
NGCD - number field case using rational reconstruction
MGCD - rational case (no field extensions)

The test file 

testNgcd

contains examples which show how to create input polynomials
in Maple's representation using RootOfs and convert them to the
new data structure and then compute the gcd using NGCD(f1,f2).
The inputs can be multivariate.
The Maple worksheet

gcd.mws

contains examples of gcd computations over the integers, finite
fields and algebraic number fields.

The improvements currently being worked on are
1: a better rational reconstruction algorithm which requires fewer primes
2: reconstructing the (smaller) cofactor instead when the cofactor is small
3: replacing the expensive trial divisions.

Here is an example:
The output of NGCD is supposed to show what it is doing.
The print statements can be deleted if desired.

> alias( alpha=RootOf(x^6-x-11), beta=RootOf(y^3-2) );
                                           alpha, beta

> g := x^3-alpha*x-beta+3;
                                        3
                                  g := x  - alpha x - beta + 3

> f1 := expand( g*(x^3+alpha*x^2-5*beta+1) ):
> f2 := expand( g*(x^3-5*alpha*x^2-beta^2+11) ):
> F1 := rpoly(f1,[x,a,b],[a=alpha,b=beta]);
              2                                       2      2             3      4    5      6
F1 := (3 + 5 b  - 16 b + (-1 + 5 b) a x + (-b + 3) a x  + (-a  - 6 b + 4) x  - a x  + x  a + x )

          6            3
    mod <a  - a - 11, b  - 2>

> F2 := rpoly(f2,[x,a,b],[a=alpha,b=beta]);
                      2     2                            2            2    2        3      4
F2 := (35 - 11 b - 3 b  + (b  - 11) a x + (-15 + 5 b) a x  + (-b + 5 a  - b  + 14) x  - a x

          5      6        6            3
     - 5 x  a + x ) mod <a  - a - 11, b  - 2>

> NGCD(F1,F2);
NGCD: GCD in Q[a, b][x] mod <b^3-2, a^6-a-11>
NGCD: I will split b^3-2
NGCD: I won't split a^6-a-11
 NGCD: Prime 1 = 46327 ... 46309 ... 46307 ... 46301 ... 46279 ... 46273 ... 46271 ... 46261 ... 46237 ... 46229 ... 46219
  AGCD: b^3-2 = (b+21120)*(b+513)*(b+24586) mod 46219
   AGCD: | b = 25099
   AGCD: | b = 45706
   AGCD: | b = 21633
  AGCD: images done for b^3-2 - interpolating ...
 NGCD: Prime 2 = 46199 ... 46187 ... 46183 ... 46181 ... 46171
  AGCD: b^3-2 = (b+32959)*(b+28380)*(b+31003) mod 46171
   AGCD: | b = 13212
   AGCD: | b = 17791
   AGCD: | b = 15168
  AGCD: images done for b^3-2 - interpolating ...
NGCD: Trial divisions over Z starting after 2 primes
                GCD = 58.56777494, REC = 0., DIV = 14.32225064, PHI = 5.626598465

                                           3        6            3
                          (-b + 3 - a x + x ) mod <a  - a - 11, b  - 2>

Michael Monagan