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.