The SAC-1 Polynomial GCD and Resultant System

Abstract

This is the eighth in the series of SAC-1 subsystems for Symbolic and Algebraic Calculation. The present subsystem provides programs for computing the greatest common divisors and resultants of multivariate polynomials, which are based on the new and much faster modular algorithms of W.S. Brown and G.E. Collins. The system also contains modular-algorithm programs far polynomial multiplication and trial division, and improved programs for the Chinese remainder theorem and interpolation. This report contains, for each program in the system, a user's functional specification, a formal algorithm description, a theoretical computing time, and a Fortran program listing. Illustrative empirical computing times are given for many of the programs, and a test program is included for assistance in implementation and use of the system.