message: Addition to FFT intro
diff: ### Multiplying polynomials with the Fast Fourier Transform (FFT)
  The algorithm that allows us to multiply polynomials in $O(n \log n)$ is called the **Cooley-Tukey fast Fourier transform**, or **FFT** for short.
  +It was discovered by [Gauss](https://en.wikipedia.org/wiki/Carl_Friedrich_Gauss) 160 years earlier, but then separately rediscovered and publicized by Cooley-Tukey.
  -The way this works is as follows. Say we have $\omega \in F$ such that $\omega^{n} = 1$, and $\omega^r \neq 1$ for any $0 < r < n$.
  +The heart of Cooley-Tukey FFT is actually about converting between coefficient and evaluation representations, rather than the multiplication itself.
  +Given polynomials $p$ and $q$ in dense coefficient representation, it works like this.
  +1. Convert $p$ and $q$ from coefficient to evaluation form in $O(n\log n)$ using Cooley-Tukey FFT
  +2. Multiply $p$ and $q$ in evaluation form by multiplying their points pairwise in $O(n)$
  +3. Convert $p$ and $q$ back to to coefficient form in $O(n\log n)$ using the inverse Cooley-Tukey FFT
  +
  +The key observation is that we can choose any $n$ distinct evaluation points to represent any degree $n - 1$ polynomial.
  +The Cooley-Tukey FFT works by selecting points that yield an efficient FFT algorithm. These points are fixed and work for any polynomials of a given degree.
  +
  +Specifically, say we have $\omega \in F$ such that $\omega^{n} = 1$, and $\omega^r \neq 1$ for any $0 < r < n$.
  Put another way, all the values $1, \omega, \omega^2, \omega^3, \dots, \omega^{n-1}$ are distinct and $\omega^n = 1$.
  