On the generation of the pseudo-remainder in polynomial division
Y. L. Varol · The Computer Journal · 1977
All the known methods for finding the GCD-greatest common divisor – of two polynomials are based on some variation of Euclid's algorithm, which uses repeated division of the successive divisors by the remainders. Two new algorithms for generating the remainder resulting from the pseudo-division of polynomials over a commutative ring are suggested. They are compared with respect to memory and CPU requirements. It is found that the new algorithms are more efficient, in particular, when the difference between the degrees of the polynomials is large, and/or the commutative ring is not that of the integers.