Engineering / Mathematics — Polynomial Algorithms
Faster Polynomial Arithmetic
Subquadratic polynomial multiplication by Karatsuba and FFT methods, and the crossover behaviour.
Executive summary
Polynomial multiplication is a convolution, and the same subquadratic methods that speed integer multiplication apply — with the advantage that no carries complicate the recursion.
The FFT gives quasi-linear multiplication when the base field contains suitable roots of unity, and the crossovers are lower than for integers.
Learning objectives
- Apply Karatsuba to polynomials.
- State the FFT method and its root of unity requirement.
- Identify the derived fast algorithms.
01Karatsuba for polynomials
The identity is the same as for integers, and is cleaner because there are no carries to propagate.
f = f₁X^h + f₀, g = g₁X^h + g₀ ⇒ three products suffice- Schoolbook
O(n²)Best below the crossover - Karatsuba
O(n^1.585)Crossover around degree 30 to 100 - Toom-Cook
O(n^1.465) and belowIntermediate range - FFT
O(n log n)Requires suitable roots of unity
02The FFT method
Evaluate
Compute the values of both polynomials at the n-th roots of unity, using the FFT in O(n log n).
Multiply pointwise
The product's values are the products of the values — n multiplications.
Interpolate
Recover the coefficients by an inverse FFT, again O(n log n).
Root of unity requirement
The FFT of length n requires a primitive n-th root of unity in the base field, and n must be invertible.
Fields chosen so that p − 1 is divisible by a large power of two are called FFT primes, and they are selected deliberately in implementations that rely on fast multiplication.
03Derived algorithms
Fast multiplication propagates to the rest of polynomial arithmetic, since most operations reduce to it.
| Operation | Classical | With fast multiplication |
|---|---|---|
| Multiplication | O(n²) | O(n log n) |
| Division with remainder | O(n²) | O(n log n) via Newton inversion |
| Gcd | O(n²) | O(n log² n) via half-gcd |
| Multipoint evaluation | O(n²) | O(n log² n) via subproduct tree |
| Interpolation | O(n²) | O(n log² n) |
Division uses Newton iteration to compute the reciprocal of the reversed divisor as a power series, then multiplies. The half-gcd algorithm restructures the Euclidean algorithm as a divide and conquer, and both depend entirely on multiplication being fast.
For the finite field factorisation algorithms in this collection, the dominant cost is modular composition and exponentiation, both of which reduce to multiplication — so the asymptotic improvements carry through directly.
04Frequently asked questions
Why are polynomial crossovers lower than integer ones?
Because there are no carries. The recursion is cleaner, the additions are simple coefficient operations, and the bookkeeping overhead that delays the integer crossover is largely absent.
What if the field lacks roots of unity?
Schonhage-Strassen style methods work in an auxiliary ring constructed to contain them, at the cost of a logarithmic factor. Alternatively Karatsuba or Toom-Cook are used, which have no such requirement.
Is fast multiplication worth implementing?
For general-purpose computer algebra, yes — degrees in the thousands are routine. For cryptographic finite field arithmetic, degrees are typically in the hundreds and Karatsuba is usually the practical ceiling.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 415-422.
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.