Engineering / Mathematics — Polynomial Algorithms
Euclid's Algorithm for Polynomials
The Euclidean algorithm for polynomial gcds, its degree-based termination, and coefficient growth over the rationals.
Executive summary
Euclid's algorithm applies to polynomials over a field with degree replacing absolute value, and terminates in at most the degree many steps.
Over the rationals, coefficient growth makes the naive version impractical, and modular methods are used instead.
Learning objectives
- State the polynomial Euclidean algorithm and its cost.
- Bound the number of iterations by degree.
- Explain coefficient growth and its remedy.
01The algorithm
Polynomial Euclidean algorithm
polynomials f, g over a fieldthe monic gcd of f and g- Given f, g in F[X] with deg f ≥ deg g.
- While g ≠ 0:
- Compute r = f mod g by division with remainder.
- Set f = g, g = r.
- Normalise f to be monic and return it.
O(deg f · deg g) field operationsTermination is immediate: the degree of the remainder is strictly less than that of the divisor, so degrees strictly decrease and the process stops in at most deg g + 1 steps.
02Comparison with the integer case
| Aspect | Integers | Polynomials over a field |
|---|---|---|
| Size measure | Absolute value | Degree |
| Iteration bound | O(log min(a,b)) | O(min(deg f, deg g)) |
| Worst case | Consecutive Fibonacci numbers | Every quotient of degree 1 |
| Normalisation | Non-negative | Monic |
| Coefficient growth | None — operands shrink | Severe over Q |
The iteration bound is worse in relative terms for polynomials: degrees fall by at least one per step, so there can be as many steps as the degree, whereas integer operands shrink by a constant factor and give a logarithmic bound.
03Coefficient growth over the rationals
Three responses are standard, in increasing order of effectiveness.
- Pseudo-division
Avoids fractionsCoefficients still grow exponentially - Subresultant algorithm
Controlled growthExact division removes predictable factors at each step - Modular method
No growth at allCompute mod several primes and reconstruct
The modular method is what computer algebra systems use. Compute the gcd modulo several primes, reconstruct the coefficients, and verify by trial division. A prime is unlucky if the gcd degree drops modulo it, which is detected by comparing degrees across primes and discarding the outliers.
04Frequently asked questions
Why can the iteration count equal the degree?
Because each division can reduce the degree by only one, when the quotient is linear. Random polynomials give quotients of degree one almost always, so the worst case is also the typical case.
What is a subresultant?
A determinant of a submatrix of the Sylvester matrix, appearing as the content that can be divided out exactly at each Euclid step. Removing it keeps coefficients polynomially bounded rather than exponentially.
How is an unlucky prime detected?
The gcd computed modulo an unlucky prime has larger degree than the true gcd. Computing modulo several primes and taking the minimum degree identifies the good ones, and the final answer is verified by division.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 402-405.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.