Univariate polynomial gcd's over the integers are now computed using the following modular method. For word size prime moduli , the gcd is computed over efficiently using in-place machine arithmetic. The modular gcd's are then combined by application of the Chinese remainder theorem. This new method is an order of magnitude more efficient for large problems. This improves the performance of arithmetic in .

bondaren@thsun1.jinr.ru