On Degrees of Modular Common Divisors and the Big Prime g c d Algorithm

Abstract EN

We consider a few modifications of the Big prime modular g c d algorithm for polynomials in Z [ x ] .

Our modifications are based on bounds of degrees of modular common divisors of polynomials, on estimates of the number of prime divisors of a resultant, and on finding preliminary bounds on degrees of common divisors using auxiliary primes.

These modifications are used to suggest improved algorithms for g c d calculation and for coprime polynomials detection.

To illustrate the ideas we apply the constructed algorithms on certain polynomials, in particular on polynomials from Knuth’s example of intermediate expression swell.