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 **