README file for the RECDEN data structure and GCD routines. Michael Monagan. To use the code you need to read in this file recden which contains the main code for the data structure and basic operations. To learn to use the data structure, there are examples in the Maple worksheet demo.mws To compute multivariate GCDs you need to read in these files 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 files testNgcd testMgcd testPgcd 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 MGCD(f1,f2), PGCD(f1,f2), and 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 > 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 > NGCD(F1,F2); NGCD: GCD in Q[a, b][x] mod 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