Fast Fourier Transform and Polynomial Multiplication

Core Idea

The Fast Fourier Transform (FFT) computes the Discrete Fourier Transform (DFT) of a sequence of n values in O(n log n) time, down from the naive O(n^2). Its primary algorithmic application is O(n log n) polynomial multiplication: evaluate two degree-n polynomials at the n-th roots of unity (via FFT), multiply the values pointwise in O(n), then interpolate back (via inverse FFT). The Cooley-Tukey algorithm achieves this through a divide-and-conquer decomposition that splits even- and odd-indexed coefficients, exploiting the symmetry properties of roots of unity (the "butterfly" structure). The FFT is the foundation for Schonhage-Strassen integer multiplication (O(n log n log log n)) and has applications throughout signal processing, string matching, and computational algebra. It is frequently cited as one of the ten most important algorithms of the 20th century.

Explainer

The Fast Fourier Transform is one of the most consequential algorithms in all of computer science and applied mathematics. Its core contribution is reducing the Discrete Fourier Transform (DFT) — a linear transformation that converts between the coefficient representation and the frequency representation of a sequence — from O(n^2) to O(n log n). This speedup has had immense practical impact in signal processing, image compression, telecommunications, and scientific computing, but its role in algorithm design centers on polynomial multiplication: the FFT makes it possible to multiply two polynomials of degree n in O(n log n) time, a fundamental operation with consequences throughout theoretical computer science.

The algorithm exploits the algebraic structure of roots of unity. Let omega = e^(2*pi*i/n) be a primitive n-th root of unity. The DFT evaluates a polynomial A(x) = a_0 + a_1*x + ... + a_{n-1}*x^{n-1} at the points 1, omega, omega^2, ..., omega^{n-1}. The Cooley-Tukey FFT splits A into even-indexed and odd-indexed coefficients: A(x) = A_even(x^2) + x*A_odd(x^2). The magic is that evaluating A_even and A_odd at the squares of the n-th roots of unity is exactly evaluating them at the (n/2)-th roots of unity — because squaring the n-th roots collapses them to the (n/2)-th roots. This gives a perfect divide-and-conquer: two recursive FFTs of size n/2, plus O(n) "butterfly" operations to combine. The recurrence T(n) = 2T(n/2) + O(n) gives T(n) = O(n log n).

Polynomial multiplication follows a three-step pipeline. To multiply A(x) and B(x), both of degree n: (1) evaluate A and B at 2n roots of unity using two FFTs (O(n log n) each), (2) multiply the values pointwise to get the values of C = AB at the 2n roots of unity (O(n)), (3) apply the inverse FFT to recover the coefficients of C (O(n log n)). The correctness relies on the fundamental fact that a polynomial of degree d is uniquely determined by its values at d+1 points, and that pointwise multiplication of values corresponds to polynomial multiplication. The total cost is O(n log n), an exponential improvement over the O(n^2) of naive coefficient-by-coefficient convolution.

The connection to integer multiplication runs through the observation that multiplying two n-bit integers is essentially multiplying two polynomials (with base-B "coefficients") followed by carry propagation. The Schonhage-Strassen algorithm (1971) made this practical by performing the FFT over the ring Z/(2^m + 1)Z rather than over the complex numbers. In this ring, 2 is a root of unity of order 2m, so all arithmetic is exact (no floating-point roundoff) and each operation takes O(m) bit operations. The recursive structure (use the FFT to multiply large integers, but the FFT itself requires integer multiplications for the butterfly operations) is handled by recursing until the integers are small enough for schoolbook multiplication. The resulting O(n log n log log n) complexity was the best known for 36 years, until Furer improved the log log n factor in 2007, and Harvey and van der Hoeven achieved the conjectured optimal O(n log n) in 2021.

Beyond multiplication, the FFT appears throughout algorithm design. Fast string matching can be reduced to polynomial multiplication (represent text and pattern as polynomials, compute their convolution). The FFT is essential for fast algorithms in computational geometry (polygon area, point-set diameter), coding theory (Reed-Solomon encoding/decoding), and combinatorics (computing convolutions that arise in counting problems). The Number Theoretic Transform (NTT) — the FFT over finite fields — is the basis for fast modular arithmetic in cryptography and for efficient implementations of operations in lattice-based cryptographic schemes. The FFT's combination of theoretical elegance (a single divide-and-conquer idea, enabled by the algebraic structure of roots of unity) and extraordinary practical impact places it among the greatest algorithmic achievements of the 20th century.