Polynomial Arithmetic and GCD
The Polynomial Euclidean Algorithm over a Field
The Euclidean and extended Euclidean algorithms for polynomials over a field, and their role in inversion and interpolation.
Engineering / MathematicsPolynomial Arithmetic and GCD2 min readKV-MATH-0557
Over a field, the polynomial Euclidean algorithm is a direct transcription of the integer one, with degree playing the role of magnitude. It terminates in at most the degree many steps and suffers no coefficient growth.
The algorithm
Normalisation
The GCD is defined only up to a unit, so a convention is needed. The standard choice over a field is to make the result monic.
The extended algorithm
Carrying Bezout coefficients through gives polynomials expressing the GCD as a combination of the inputs.
Inversion in a quotient ring
An element of the quotient by an irreducible polynomial is invertible exactly when it is coprime to that polynomial, and the extended algorithm produces the inverse.
Inversion in a polynomial quotient ring
- Run extended EuclidAgainst the defining polynomial.
- Check the GCDIf it is not constant, the element is not invertible — and the GCD is a proper factor of the modulus.
- NormaliseScale the Bezout coefficient so the product is one.
Half-GCD
As with integers, a divide-and-conquer variant achieves O(M(d) log d) by computing the transformation matrix for many steps at once. It matters only at high degree, but it is the basis of fast rational reconstruction and of Schoof's algorithm.
Resultants from the remainder sequence
The sequence of remainders carries more information than the GCD alone: the resultant can be read from the leading coefficients along the way. See resultants.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.2.1. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.