Polynomial Arithmetic and GCD
Polynomial GCD over a Unique Factorisation Domain
Computing polynomial GCDs over the integers, the growth problem in remainder sequences, and the modular approach that sidesteps it.
Engineering / MathematicsPolynomial Arithmetic and GCD2 min readKV-MATH-0559
Polynomial GCD over the integers is where coefficient growth first becomes intolerable. The naive algorithm is correct and unusable; there are two standard repairs and they take opposite approaches.
The problem
Applying the Euclidean algorithm with pseudo-division multiplies the dividend by a power of the leading coefficient at every step. The coefficients grow exponentially in the number of steps even when the GCD is one.
Repair one: control the sequence
| Remainder sequence | Growth | Cost per step |
|---|---|---|
| Pseudo-remainder | Exponential | Cheap |
| Primitive | Minimal | A coefficient GCD every step |
| Sub-resultant | Near minimal | One exact division every step |
Repair two: avoid the sequence
Compute the GCD modulo several primes, where no growth occurs, and reconstruct by the Chinese remainder theorem.
Modular polynomial GCD
- Bound the resultUse a Mignotte-style bound on the coefficients of any factor — see Mignotte bounds.
- Choose primesAvoid primes dividing either leading coefficient.
- Compute modulo eachOrdinary field GCD, no growth.
- Detect unlucky primesA GCD of unexpectedly high degree indicates an unlucky prime; discard it.
- Reconstruct and verifyReassemble, then confirm by exact division into both inputs.
Unlucky primes
Verification
Multivariate
For several variables, the same two strategies apply with evaluation at points replacing reduction modulo primes. The unlucky-evaluation problem is the exact analogue of the unlucky prime.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.2.4. 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.