Polynomial Arithmetic and GCD
The Sub-Resultant GCD Algorithm
The sub-resultant remainder sequence: predicting the divisible factor at each step to keep coefficients near minimal without content computation.
Engineering / MathematicsPolynomial Arithmetic and GCD2 min readKV-MATH-0560
The sub-resultant algorithm is the classical answer to coefficient growth in polynomial remainder sequences. It works by knowing in advance what factor divides each remainder, so it can be removed by a single exact division.
The idea
Each remainder in a pseudo-remainder sequence is divisible by a predictable power of previous leading coefficients. That divisor is computed from data already at hand, and the division is exact.
The procedure
Sub-resultant remainder sequence
- Pseudo-divideCompute the pseudo-remainder of the current pair.
- Compute the divisorFrom the previous leading coefficient and the degree drop, using the sub-resultant recurrence.
- Divide exactlyRemove the factor; the division is guaranteed exact.
- AdvanceShift the pair and repeat until the remainder is zero.
Growth achieved
| Sequence | Coefficient size | Work per step |
|---|---|---|
| Pseudo-remainder | Exponential in the number of steps | Least |
| Sub-resultant | Polynomial, close to optimal | One exact division |
| Primitive | Optimal | One coefficient GCD |
Resultants as a by-product
The sub-resultant sequence is named for the sub-resultants, which are determinants of submatrices of the Sylvester matrix. The last non-zero entry of the sequence gives the resultant directly — see resultants and discriminants.
When to prefer modular methods
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.3.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.