Large-integer multiplication becomes faster when we stop treating the operands as indivisible numbers and start treating them as coefficient vectors.
The school multiplication algorithm multiplies every digit of one operand by every digit of the other. That gives a quadratic pattern of elementary products. Faster methods change the representation. Karatsuba reduces four half-size products to three. Toom–Cook evaluates at several points and interpolates. Transform methods convert convolution into pointwise multiplication.
This is Guide 14 in the Bukit Timah Tutor Computational Number Theory series. It explains the multiplication primitive whose cost sits underneath modular exponentiation, primality testing, factorisation and big-integer arithmetic. It follows Guide 13 on Montgomery and Barrett reduction. Return to the BTT Mathematics Hub for the wider Mathematics estate.
1. Multiplication as digit convolution
Write a nonnegative integer in base B:
A = a0+a1B+a2B²+… C = c0+c1B+c2B²+…
Before carrying, the coefficient of B^k in AC is
d_k = Σ(i+j=k) a_i c_j.
This is a discrete convolution. Ordinary long multiplication computes the convolution directly. Carry propagation is a separate normalization stage that converts possibly large coefficients d_k back into base-B digits.
The distinction is important. Convolution is bilinear algebra; carrying is positional representation. Transform-based multiplication accelerates the convolution, then performs exact carry recovery afterward.
2. Schoolbook multiplication and its quadratic shape
If each operand has n base-B digits, the direct method forms about n² digit products. The exact bit cost depends on the digit size and machine model, but the structural count is quadratic in the number of limbs.
For small operands, schoolbook multiplication is often best because the constants are small and the implementation is simple. A theoretically faster method has setup, temporary storage and recursive overhead.
This produces an important engineering rule: asymptotic superiority does not determine the best crossover point. Mature big-integer libraries switch algorithms according to operand size and platform.
3. Karatsuba’s three-product idea
Split two integers around a power M=B^m:
A = A1 M + A0 C = C1 M + C0.
Ordinary expansion uses four half-size products:
AC = A1C1 M² +(A1C0+A0C1)M +A0C0.
Karatsuba observes that the middle coefficient can be recovered from one additional product:
z0 = A0C0 z2 = A1C1 z1 = (A0+A1)(C0+C1)−z0−z2.
Then AC=z2M²+z1M+z0. Three recursive multiplications replace four.
4. Worked Karatsuba example
Multiply 1234 by 5678 using M=100. Then A1=12,A0=34,C1=56,C0=78.
z0 = 34·78 = 2652 z2 = 12·56 = 672 z1 = (12+34)(56+78)−2652−672 = 46·134−3324 = 6164−3324 = 2840.
Recombine:
AC = 672·10000 + 2840·100 + 2652 = 7006652.
Direct multiplication confirms 1234·5678=7,006,652.
The recurrence T(n)=3T(n/2)+O(n) leads to growth n^(log2 3), about n^1.585, in the usual digit-operation model.
5. Why Karatsuba is an evaluation method
Associate A with the degree-one polynomial A0+A1X and C with C0+C1X. Their product has three coefficients. Evaluating at X=0,1 and conceptually infinity determines those coefficients from three products.
This viewpoint generalises. Toom–Cook splits an operand into more blocks, interprets it as a higher-degree polynomial, evaluates at selected points, multiplies the values and interpolates the coefficient polynomial.
Karatsuba is therefore the first member of a larger family: evaluate → multiply pointwise → interpolate → recombine.
6. Toom–Cook and the tradeoff in more splits
Toom-3 writes each integer as a quadratic polynomial in M. Their product has degree four. Five suitable evaluation points determine the five coefficients, replacing nine block products by five larger combinations.
The savings in recursive multiplications come with more additions, subtractions, exact small divisions and interpolation bookkeeping. The algorithm is attractive only above a suitable operand size.
Different Toom variants choose different split counts. Increasing the split count reduces the exponent of the multiplication recurrence but increases constants and implementation complexity.
7. Convolution is polynomial multiplication
Let
a(X)=Σ a_iX^i, c(X)=Σ c_jX^j.
The product coefficients are exactly the digit convolution d_k. If we can multiply these polynomials faster than the quadratic coefficient loop, we can multiply large integers faster.
A transform evaluates a polynomial at many structured points. At each point, polynomial multiplication becomes ordinary scalar multiplication:
(ac)(ω)=a(ω)c(ω).
The inverse transform reconstructs the coefficients. This replaces one hard convolution with two forward transforms, pointwise products and one inverse transform.
8. Roots of unity and the discrete Fourier transform
Choose N evaluation points 1,ω,ω²,…,ω^(N−1), where ω is a primitive N-th root of unity. The discrete Fourier transform maps coefficients to values at these points.
A naïve evaluation at N points still costs O(N²). The fast Fourier transform exploits symmetries when N has a convenient factorisation, especially powers of two. Separating even and odd coefficient indices gives two transforms of half the size.
a(X)=a_even(X²)+X a_odd(X²).
Evaluations at paired roots ω^k and −ω^k share the same half-size transform values. This gives the classic divide-and-conquer FFT recurrence with O(N log N) arithmetic operations.
9. Zero padding prevents circular wraparound
An N-point transform naturally computes cyclic convolution modulo X^N−1. To recover ordinary polynomial multiplication, choose N larger than the maximum possible product degree and pad both coefficient arrays with zeros.
If the input lengths are r and s, the ordinary product has length at most r+s−1. Therefore use a transform length N≥r+s−1, commonly rounded up to a convenient power of two.
Without enough padding, high-degree coefficients wrap around and contaminate low-degree positions. A transform can execute perfectly while solving the wrong convolution problem.
10. A tiny convolution example
Take coefficient vectors [3,1,4] and [2,5]. Their direct convolution is:
d0 = 3·2 = 6 d1 = 3·5+1·2 = 17 d2 = 1·5+4·2 = 13 d3 = 4·5 = 20.
The polynomial product is 6+17X+13X²+20X³. Any correct FFT or NTT implementation, after inverse transformation and normalization, must recover these exact four coefficients.
For integer multiplication in a chosen base, carry propagation is then applied to the coefficient list.
11. Floating-point FFT requires an error budget
A complex FFT uses approximate floating-point arithmetic. After the inverse transform, coefficients expected to be integers are rounded. Correctness therefore depends on proving or engineering that numerical error stays safely below one half in every coefficient.
The coefficient base B, transform length, floating-point precision and implementation details all affect the bound. Choosing very large base digits reduces transform length but increases coefficient magnitudes and numerical error.
A result that happens to round correctly on a sample is not a proof that every allowed input will round correctly. Exact big-integer libraries use carefully designed splitting, extra precision, error analysis or integer transforms to control this issue.
12. Number-theoretic transforms use exact modular arithmetic
An NTT replaces complex roots of unity with roots of unity in a finite field. Choose a prime modulus p such that N divides p−1, then select an element ω of exact order N modulo p.
The transform has the same butterfly structure as an FFT, but every addition and multiplication is exact modulo p. The inverse uses ω^−1 and multiplication by N^−1 modulo p.
The output is the convolution modulo p. To recover an ordinary integer convolution, the true coefficients must be known to lie in a range that makes modular reconstruction unambiguous.
13. Why coefficient bounds matter in an NTT
If each input coefficient lies between 0 and B−1 and the shorter input has length m, then each convolution coefficient is at most m(B−1)². A single modulus p larger than this bound is enough to recover each coefficient directly from its residue.
When one convenient NTT prime is too small, use several coprime primes. Compute the convolution modulo each prime and reconstruct the exact coefficient with the Chinese Remainder Theorem.
The product of the chosen moduli must exceed the possible coefficient range. CRT without a range bound determines a residue class, not which integer coefficient in that class was intended.
14. An NTT design checklist
First choose the transform length N. Then choose one or more primes whose p−1 contains N as a divisor. Verify that the chosen root has exact order N, not merely that ω^N=1.
Next bound the convolution coefficients. Ensure the modulus product is large enough. Run forward transforms, pointwise multiplication and inverse transforms, then reconstruct coefficients and propagate carries.
Finally multiply the reconstructed integer operands by an independent trusted method on bounded tests. Transform invertibility, coefficient reconstruction and carry propagation are separate invariants and should be tested separately.
15. Carry propagation after convolution
Suppose the raw convolution coefficients are d0,d1,… in base B. Process from low to high:
carry = 0
for k:
total = d_k + carry
digit_k = total mod B
carry = floor(total/B)
Continue emitting digits while carry remains nonzero.
For signed coefficient schemes, such as balanced digit representations, normalization requires an appropriate signed carry rule. The arithmetic representation must be fixed before the carry algorithm is specified.
16. Transform multiplication and modular arithmetic connect
The NTT itself repeatedly performs modular additions and multiplications. Therefore the fast modular-reduction methods from Guide 13 can appear inside the multiplication algorithm from this guide.
The dependency can run in both directions. Large modular arithmetic benefits from fast integer multiplication; fast transform multiplication may itself benefit from efficient modular multiplication under carefully chosen NTT primes.
Algorithmic number theory is often layered in this way. A higher-level algorithm depends on a primitive whose own efficient implementation uses another number-theoretic structure.
17. Verification through evaluation
Exact coefficient reconstruction is the strongest check for a known product, but additional checks can catch implementation errors cheaply. For integer operands A and C, compare the low few limbs with ordinary school multiplication. Compare the full product modulo several small unrelated primes.
If P is the reported product, verify P mod q=(A mod q)(C mod q) mod q for several test primes q. Such modular checks cannot prove equality alone unless the modulus product exceeds the possible error range, but they are useful debugging certificates.
For transform code, also verify that inverse(forward(v)) reproduces v for many vectors within the supported domain.
18. Complexity should name the multiplication model
Let M(n) denote the cost of multiplying n-bit integers. Schoolbook multiplication gives a quadratic baseline. Karatsuba and Toom–Cook improve the exponent. Transform methods approach quasi-linear behaviour over suitable ranges.
Harvey and van der Hoeven proved an asymptotic O(n log n) integer-multiplication algorithm. This theoretical result does not mean a practical library should use that construction for ordinary operand sizes. Practical implementations use multiple algorithms with empirical crossover points.
When another number-theory algorithm is described using O(M(n)) multiplication cost, this notation deliberately hides the currently selected multiplication engine. It lets higher-level complexity analysis improve automatically when the multiplication primitive improves.
19. Common mistakes
1. Confusing cyclic convolution with ordinary convolution. 2. Forgetting zero padding. 3. Choosing an NTT root whose order divides N but is smaller than N. 4. Reconstructing from CRT without a coefficient bound.
5. Treating floating-point FFT coefficients as exact before error analysis. 6. Forgetting carry propagation after a correct convolution. 7. Claiming the fastest asymptotic algorithm is automatically the fastest practical algorithm. 8. Counting transform operations while ignoring the cost of modular or floating-point arithmetic inside them.
20. Practice set
1. Express ordinary base-B multiplication as convolution. 2. Reproduce the Karatsuba calculation for 1234·5678. 3. Explain why Karatsuba needs only three recursive products. 4. What is the general Toom–Cook idea?
5. Convolve [3,1,4] with [2,5]. 6. Why must a transform be zero padded? 7. What structural property makes FFT divide-and-conquer possible? 8. State one source of numerical risk in complex FFT multiplication.
9. What condition on p permits an N-point NTT? 10. Why must the root have exact order N? 11. Give a coefficient bound when one input length is m and digits are below B. 12. Why may several NTT primes be needed?
13. What does CRT reconstruct in transform multiplication? 14. What does carry propagation reconstruct? 15. Give one independent product check using small primes. 16. Explain why M(n) is useful notation in higher-level algorithms.
21. Answers and checks
1. The pre-carry coefficient at position k is Σ(i+j=k)a_i c_j. 2. The three products are 2652,672 and 6164; the middle coefficient is 2840 and the result is 7,006,652. 3. The cross terms are recovered from the product of the two sums. 4. Split into blocks, evaluate block polynomials, multiply pointwise and interpolate.
5. [6,17,13,20]. 6. Otherwise high coefficients wrap around through cyclic convolution. 7. Structured roots of unity pair the even and odd subproblems. 8. Rounding error can move an inverse-transform coefficient across the wrong integer boundary.
9. N must divide p−1 for an N-th root of unity in Fp*. 10. A smaller-order root causes repeated evaluation points and destroys invertibility. 11. m(B−1)² is a simple upper bound. 12. One convenient modulus may be too small to determine the integer coefficient uniquely.
13. The exact convolution coefficients from their residues modulo several primes. 14. The normalized base-B digits of the integer product. 15. Check P mod q=(A mod q)(C mod q) mod q. 16. It separates higher-level algorithm analysis from the choice of multiplication engine.
Sources and further study
Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, discusses fast arithmetic in computational number theory. David Harvey and Joris van der Hoeven, Integer multiplication in time O(n log n), gives the asymptotic result. For practical multi-algorithm arithmetic, the GNU MP manual on multiplication algorithms is a useful implementation reference.
Continue through Batch 04
Return to Guide 13: Montgomery & Barrett Reduction. Continue to Guide 15: Integer Lattices, Gram–Schmidt and LLL Reduction and Guide 16: Algebraic Number Fields, Ideals, Norms and Computational Arithmetic.