Fun article, but it was missing a little bit that took me a minute to get. So if you&#x27;re already familiar with fourier transforms, this might be the missing piece to this article:<p>Multiplication of polynomials when expressed in the domain of &quot;array of coefficients&quot; is a convolution operation: really you&#x27;re summing (AB)_k = sum_{i=0}^k A_i B_{k-i} to find the kth coefficient of the result. The indices for B go backwards to those of A and they add up to the fixed quantity k, so we&#x27;re just looking at a discrete convolution of these two arrays.<p>And what does Fourier Transform do? It turns convolutions into point-wise multiplication in the &#x27;time&#x27; domain. The convolution started as an n^2 operation but the point-wise multiplication is n, so we&#x27;re left with the FFT time of n log n. So this is another instance of the &quot;formulate problem as a convolution, FFT, perform point-wise multiplication in the time domain, inverse FFT, done&quot; class of algorithms.<p>(I got stuck a while trying to figure out how polynomial multiplication is convolution. Literally it&#x27;s point-wise multiplication of two functions, not a convolution, so everything seemed backwards.)