Polynomial Arithmetic and GCD in Unique Factorisation Domains

Q: Why not just work over Q and clear denominators at the end?

Because rational arithmetic invokes an integer GCD at every coefficient operation and the intermediate fractions grow rapidly. Clearing denominators once at the start and working in ℤ throughout is faster by a wide margin.

Q: What makes the subresultant divisions exact?

Subresultant theory identifies the precise factor by which each pseudo-remainder is divisible — a determinant of a submatrix of the Sylvester matrix. Dividing by it is exact, which is why no fractions appear and no information is discarded.

Q: How many primes does a modular GCD need?

Enough for the product to exceed twice the coefficient bound on the true GCD, usually obtained from Mignotte's bound on divisors. In practice implementations add primes until two successive reconstructions agree and the result passes trial division.

Executive summary

Euclid's algorithm survives the move to polynomials; its coefficients do not

Polynomials over a field admit the Euclidean algorithm unchanged. Over a UFD such as ℤ there is no division, only pseudo-division, and the coefficients of the remainder sequence grow exponentially — even when the input and the final GCD are tiny. The subresultant algorithm and the modular approach are the two standard remedies, and choosing between them is the main design decision in this layer.

Learning objectives

Choose a dense or sparse representation appropriately.
Perform pseudo-division and state its scaling factor.
Apply Gauss's lemma to split a GCD into content and primitive part.
Explain the coefficient explosion in the naive remainder sequence.
Select between subresultant and modular GCD strategies.

Section 01Representation and arithmetic

Representation choices
Representation	Stores	Suits	Weakness
Dense array	Every coefficient from 0 to deg	Most polynomials in this subject — minimal polynomials, modular factors	Wasteful for x¹⁰⁰⁰ + 1
Sparse list	Only non-zero (exponent, coefficient) pairs	Very sparse high-degree polynomials	Slower per operation; more complex code
Modular / evaluated	Values at chosen points	Multiplication and interpolation-based algorithms	Degree must be bounded in advance

Multiplication follows the same hierarchy as integer multiplication: schoolbook at O(n²), Karatsuba, and FFT-based methods that multiply by evaluation and interpolation. The crossovers are again machine-dependent and must be measured.

Degree bookkeeping

The most common source of subtle bugs is a stale degree field after coefficients cancel. Every routine that can reduce the degree must renormalise before returning, exactly as multiprecision integers must be normalised.

Section 02Division and pseudo-division

Over a field, division with remainder always works. Over ℤ it does not: dividing x² by 2x leaves the ring. Pseudo-division repairs this by pre-multiplying the dividend by a power of the divisor's leading coefficient.

lc(B)^m−n+1 A = QB + R, with deg R < deg B

Here m = deg A and n = deg B. The scaling factor is exactly what makes every quotient and remainder coefficient an element of the ring — and exactly what makes the coefficients grow.

Coefficient explosion is exponential

Iterating pseudo-division to build a remainder sequence multiplies in a fresh power of a leading coefficient at every step. For inputs of degree around 10 with small coefficients, intermediate coefficients of dozens of digits are routine, and the final GCD may be 1. The work is entirely wasted, and the effect worsens sharply with degree.

Section 03Content, primitive part and Gauss's lemma

The content of a polynomial over a UFD is the GCD of its coefficients; the primitive part is the polynomial divided by its content. Gauss's lemma states that the product of primitive polynomials is primitive, from which the GCD splits cleanly:

gcd(A, B) = gcd(cont A, cont B) · gcd(pp A, pp B)

The content GCD is an ordinary integer GCD. The primitive part GCD is the hard half, and it is the only part the remainder sequence needs to handle. Removing content at every step keeps coefficients smaller but costs a GCD of all coefficients per step — the primitive remainder sequence, which trades one cost for another.

Section 04Choosing a GCD strategy

What is the coefficient ring?
- Field Plain Euclidean algorithm — no growth problem exists.
- ℤ or ℤ[y] How large are the inputs?
  - Small Subresultant PRS — deterministic, single-pass, growth provably controlled.
  - Large Modular GCD — compute modulo several primes, reconstruct by CRT, verify by trial division.
- Number field Modular with prime ideals — reduce modulo primes of good reduction, then lift.

Comparison of GCD strategies over ℤ
Strategy	Growth control	Determinism	Notes
Naive PRS	None — exponential	Deterministic	Reference only; unusable
Primitive PRS	Good	Deterministic	A content GCD at every step
Subresultant PRS	Provably bounded by subresultant theory	Deterministic	The standard exact method; divisions are exact by construction
Modular (Brown)	None needed — work is modular	Probabilistic	Fastest for large inputs; must detect unlucky primes and verify the result
Heuristic (GCDHEU)	Evaluation at a large integer	Probabilistic	Very fast when it succeeds; needs a verification step

Always verify a modular GCD

An unlucky prime can produce a candidate GCD of too high a degree. The verification is simple — divide both inputs by the candidate and confirm the remainders vanish — and it converts a probabilistic algorithm into a certain one.

ReferenceFrequently asked questions

Why not just work over Q and clear denominators at the end?

Because rational arithmetic invokes an integer GCD at every coefficient operation and the intermediate fractions grow rapidly. Clearing denominators once at the start and working in ℤ throughout is faster by a wide margin.

What makes the subresultant divisions exact?

Subresultant theory identifies the precise factor by which each pseudo-remainder is divisible — a determinant of a submatrix of the Sylvester matrix. Dividing by it is exact, which is why no fractions appear and no information is discarded.

How many primes does a modular GCD need?

Enough for the product to exceed twice the coefficient bound on the true GCD, usually obtained from Mignotte's bound on divisors. In practice implementations add primes until two successive reconstructions agree and the result passes trial division.

NavigateContinue in this stream

Curated next steps from this page. The site also surfaces algorithmically related reading below.

ProvenanceSources and further reading

This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.