FFT/NTT

(Polynomial) Multiplication

Multiplication is a very costly operation, while it is widely used in latticed-based cryptography. An intuitive way to solve multiplication is point-wise multiplication that we learnt in primary school, which has complexity of $O(n^2)$.

Karatsuba’s algorithm takes $O(n^{\log_{2}3})$.

Lagrange interpolation takes $O(n^2)$ as well.

Vandermonde matrix takes $O(n^3)$ if we use the naive way to calculate the inverse matrix.

FFT utilize the periodic structure of root of unity in a ring, reducing the complexity by divide and conquer. A FFT problem can be divided into odd and even problem with extra computation $O(n)$ . Therefore, by master theorem, $T(n) = 2T(\frac{n}{2}) +O(n)$ , the total complexity is $O(n\log n)$ .

Overall Procedure

The overall procedure can be seen as follows

1. Using FFT to calculate $n$ points on the polynomial. Think of it as calculating the Vandermonde matrix.
2. Compute multiplication of both $n$ points.
3. Inverse FFT to give the output polynomial coefficient.

Matrix Recursion Form

The Discrete Fourier Transform (DFT) matrix of size $ n $ , denoted $ F_n $ , can be recursively decomposed as:

\[F_n = T_n \cdot \left[ \begin{matrix} F_{n/2} & 0 \\ 0 & F_{n/2} \end{matrix} \right] \cdot P_n\]

1. $ P_n $ — Bit-reversal permutation matrix
   Reorders the input vector so that even and odd indexed entries are grouped together. This enables divide-and-conquer recursion. For example,
   \(x = [x_0,\ x_1,\ x_2,\ x_3,\ x_4,\ x_5,\ x_6,\ x_7] \;\longmapsto\; [x_0,\ x_2,\ x_4,\ x_6,\ x_1,\ x_3,\ x_5,\ x_7]\)
2. $F_{n/2} \oplus F_{n/2} $ — Block-diagonal recursive DFTs
   Performs two independent DFTs of size $ n/2 $ on the even and odd parts of the reordered input.

3. $ T_n $ — Twiddle factor merge matrix
   Applies the necessary phase shifts (roots of unity) to the odd sub-part and combine the two half-DFTs into the full DFT result. It has the form:

   \[T_n = \left[ \begin{matrix} I_{n/2} & D_{n/2} \\ I_{n/2} & -D_{n/2} \end{matrix} \right]\]

   where $ D_{n/2} = \text{diag}(1, \omega_n, \omega_n^2, \dots, \omega_n^{n/2-1}) $ .
   This can also be expressed as:

   \[X_{k}=E_{k}+\omega^{k}O_{k},\] \[X_{k+n/2}=E_{k}-\omega^{k}O_{k},\]

   where $ E_k $ and $ O_k $ are the results from the even and odd indexed subproblems, respectively, and $ \omega^k $ is the twiddle factor corresponding to the $ k $ th and $ k+n/2 $ th output.

Butterfly Network

In practical implementations of algorithms, recursion is often avoided to reduce memory overhead, and an iterative approach is used instead. The butterfly network is essentially the iterative form of the FFT, where each stage corresponds to a sequential application of $T_n$ in reverse order (ascending). As shown above, the two equations precisely capture the operation performed in each butterfly.