Euclidean algorithm for polynomials

E646780

algorithm greatest common divisor algorithm

The Euclidean algorithm for polynomials is a procedure that repeatedly applies polynomial division to compute the greatest common divisor of two polynomials over a given field or ring.

Try in SPARQL Jump to: Surface forms Statements Referenced by

Observed surface forms (1)

Surface form	Occurrences
Euclidean algorithm	1

Statements (47)

Predicate	Object
instanceOf	algorithm ⓘ greatest common divisor algorithm ⓘ
applicableOver	Euclidean domains ⓘ fields ⓘ principal ideal domains via embeddings ⓘ
basedOn	Euclidean algorithm for integers NERFINISHED ⓘ
complexityDependsOn	cost of polynomial multiplication and division ⓘ degrees of the input polynomials ⓘ
computes	greatest common divisor of polynomials ⓘ
domain	polynomials over a Euclidean domain ⓘ polynomials over a field ⓘ polynomials over a principal ideal domain ⓘ
extendedVariantComputes	Bezout coefficients for polynomials ⓘ
extendedVariantUsedFor	Chinese remainder theorem for polynomials NERFINISHED ⓘ computing inverses modulo a polynomial ⓘ
fieldOfStudy	abstract algebra ⓘ algebra ⓘ computational algebra ⓘ
finalNonzeroRemainderIs	greatest common divisor ⓘ
hasStep	repeated polynomial division with remainder ⓘ replace pair by divisor and remainder ⓘ
hasVariant	extended Euclidean algorithm for polynomials ⓘ pseudo-division based Euclidean algorithm ⓘ subresultant polynomial remainder sequence algorithm ⓘ
historicalOrigin	generalization of Euclid’s algorithm to polynomial rings ⓘ
input	two polynomials ⓘ
normalization	gcd often chosen to be monic ⓘ
output	gcd up to multiplication by a unit ⓘ greatest common divisor polynomial ⓘ
property	gcd is unique up to multiplication by a nonzero constant ⓘ
relatedConcept	polynomial remainder sequence ⓘ principal ideal in a polynomial ring ⓘ resultant of polynomials ⓘ
reliesOn	Euclidean domain structure of coefficient ring ⓘ
requires	degree function on polynomials ⓘ
satisfies	any common divisor of a and b divides gcd(a,b) ⓘ gcd(a,b) divides both a and b ⓘ
terminatesWhen	remainder is zero ⓘ
usedIn	coding theory ⓘ computation of greatest common divisors in computer algebra systems ⓘ computation of resultants ⓘ construction of minimal polynomials ⓘ control theory ⓘ factorization of polynomials ⓘ signal processing ⓘ simplification of rational functions ⓘ
uses	polynomial long division ⓘ

Referenced by (2)

Full triples — surface form annotated when it differs from this entity's canonical label.

Berlekamp–Massey algorithm → relatedTo → Euclidean algorithm for polynomials ⓘ

Gröbner basis → generalizationOf → Euclidean algorithm for polynomials ⓘ

this entity surface form: Euclidean algorithm