Engineering / Mathematics — Polynomial Algorithms
Speeding Up Polynomial Algorithms via Modular Computation
Applying evaluation homomorphisms and modular reduction to control coefficient and degree growth in polynomial computation.
Executive summary
Polynomial computations over the integers or over multivariate rings suffer expression swell exactly as integer computations do, and the remedy is the same: map to a simpler ring, compute, and reconstruct.
For polynomials there are two homomorphisms available — reduction modulo a prime, and evaluation at a point — and both are used.
Learning objectives
- Identify the two available homomorphisms.
- Assemble the modular pipeline for polynomials.
- Recognise and handle unlucky primes and evaluation points.
01Two homomorphisms
Reduction modulo a prime
Maps Z[X] to F_p[X], controlling coefficient size. Reconstruction is Chinese remaindering plus recentring.
Evaluation at a point
Maps R[X, Y] to R[X] by fixing Y, controlling the number of variables. Reconstruction is interpolation.
Both reduce a hard computation to easier instances, and both are inverted by a reconstruction step. Multivariate problems typically use both together — reduce coefficients modulo a prime and evaluate all but one variable.
| Problem | Homomorphism | Reconstruction |
|---|---|---|
| Polynomial gcd over Z | Reduce mod p | CRT plus recentring |
| Multivariate gcd | Evaluate variables | Interpolation |
| Resultant | Reduce and evaluate | Both |
| Factorisation over Z | Reduce mod p | Hensel lifting, then recombination |
02The pipeline
Bound the result
Degree bounds from the inputs; coefficient bounds from Mignotte's or Hadamard's inequality.
Choose primes and points
Enough to determine the answer given the bounds.
Compute images
Run the algorithm in each F_p[X], where coefficients cannot grow.
Reconstruct
Chinese remainder across primes, interpolate across evaluation points.
Verify
Trial division for a gcd, or multiplication for a factorisation — always cheap relative to the computation.
03Unlucky choices
| Symptom | Cause | Remedy |
|---|---|---|
| Gcd degree varies across primes | Some primes unlucky | Take the minimum degree; discard the others |
| Leading coefficient vanishes | Bad evaluation point | Choose another point |
| Reconstruction fails verification | Bound too small or unlucky choice | Add primes or points and repeat |
| Result unstable as primes are added | Insufficient bound | Continue until stable across several additions |
Unlucky primes are rare because the bad primes divide a fixed non-zero quantity — a resultant or a leading coefficient — so only finitely many exist. Random selection from a large pool makes hitting one improbable, and the degree comparison detects any that slip through.
The general principle worth carrying: every step of a modular pipeline is conditional on choices that can silently go wrong, and cheap verification of the final answer is what makes the whole approach trustworthy.
04Frequently asked questions
Why is the minimum degree the right gcd degree?
Because an unlucky prime can only increase the apparent gcd degree, never decrease it — reduction can create common factors but cannot destroy them. So the smallest observed degree is the true one.
How are coefficient bounds obtained for polynomials?
Mignotte's bound limits the coefficients of any divisor of a polynomial in terms of the original's norm. It is pessimistic but rigorous, and stabilisation-based termination is often faster in practice.
Does this apply to factorisation over Z?
Yes, and it is the standard method: factor modulo a well-chosen prime, Hensel lift to a high power of that prime, then recombine the lifted factors into integer factors, verifying each 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 409-410.
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.