A New Modular GCD Algorithm which is lucky everywhere

George Labahn, Department of Computer Science, University of Waterloo





Modular computation is a standard method for overcoming the problem of
intermediate expression swell in computer algebra problems. It involves
mapping a problem to a number of `image' problems but in simpler
arithmetic domians, solving the image problems and then reconstructing
the results into a solution to the original problem.  It is typically the
method of choice for something like GCD computation of two polynomials
having integer or polynomial coefficients.

In the case of the modular GCD agorithm, there are two problems that
occur during such a computation. The first is that sometimes the solution
to an image problem must be discarded (case of `unlucky' images). The
second is that one must know when to reconstruct - a deterministic stopping
step requires too many images (and hence subproblems) while a heuristic
early stopping step requires an expensive verification step.

In this talk we present a new modular algorithm for GCD computation which makes
use of unlucky images and stops early without any need for a verification.