On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors

1971/10/01 by W. S. Brown, Warren S. Brown · 4 citations
Mathematics · Computer Science · Engineering · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #graph theory and CDMA systems

paper · pdf · doi:10.1145/321662.321664

Abstract

This paper examines the computation of polynomial greatest common divisors by various generalizations of Euclid's algorithm. The phenomenon of coefficient growth is described, and the history of successful efforts first to control it and then to eliminate it is related.

Cited by

• On Fast Matrix Inversion via Fast Matrix Multiplication
• A Modular Algorithm for Computing Polynomial GCDs over Number Fields presented with Multiple Extensions
• Finding Exact Minimal Polynomial by Approximations
• Macsyma: A personal history

Related

• A note on extended Euclid's algorithm
• Computing greatest common divisor of several parametric univariate polynomials via generalized subresultant polynomials
• Euclid's Number-Theoretical Work
• On degrees of modular common divisors and the Big prime gcd algorithm
• Cyclotomic Factors and LRS-Degeneracy