D.7.5.1 EGCD

Procedure from library zeroset.lib (see zeroset_lib).

Usage:

EGCD(f, g); where f,g are polynomials

Purpose:

compute the polynomial gcd of f and g over Q(a)[x]

Return:

polynomial h s.t. h is a greatest common divisor of f and g (not nec. monic)

Assume:

basering = Q(a)[t]

Example:

LIB "zeroset.lib";
ring R = (0,a), x, lp;
minpoly = a2+1;
poly f =  x4 - 1;
poly g = x2 - 2*a*x - 1;
EGCD(f, g);
→ (-4a)*x-4