Polynomial Arithmetic and GCD
Polynomial Multiplication Strategies
Schoolbook, Karatsuba and evaluation-interpolation methods for polynomial multiplication, and where the crossovers lie.
Engineering / MathematicsPolynomial Arithmetic and GCD2 min readKV-MATH-0555
Polynomial multiplication follows the integer case almost exactly, with one simplification and one complication: there are no carries, but the coefficients can grow.
Schoolbook
Accumulate every pairwise product of coefficients into the appropriate output position. Cost is the product of the degrees.
Karatsuba for polynomials
The same three-product identity applies. Split each polynomial at the midpoint of its degree, form three half-size products, and recombine.
| Method | Cost | Range |
|---|---|---|
| Schoolbook | O(d^2) | Low degree, the usual case here |
| Karatsuba | O(d^1.585) | Moderate degree |
| Toom-Cook | Better exponent | High degree |
| FFT-based | Near linear | Very high degree |
Evaluation and interpolation
A product of degree d is determined by its values at d + 1 points. Evaluate both factors at enough points, multiply pointwise, and interpolate.
Evaluation-interpolation multiplication
- Choose pointsPick more evaluation points than the output degree.
- EvaluateEvaluate both operands at each point.
- Multiply pointwiseOne coefficient multiplication per point.
- InterpolateRecover the product coefficients.
Coefficient growth
Modular reduction after multiplication
In a finite field extension, multiplication is followed by reduction modulo the defining polynomial. Choosing a sparse modulus makes that reduction linear rather than quadratic — see finite field multiplication.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 3.1.2. 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.