A-16.2 Forward FFT (or NTT)

We assume a polynomial ring of either $ℝ[X]∕X^n+1$ for FTT, and $\mathbb{Z}{[X]}_p∕X^n+1$ for NTT (where $X^n+1$ is a cyclotomic polynomial). The $x$ coordinates to evaluate the target polynomial are $n$ distinct $n$-th roots of unity that satisfy $X^n=1$, which are: $\{1,\omega ,{\omega }^2,\cdots ,{\omega }^{n-1}\}$. In the case of FFT (i.e., $ℝ[X]∕X^n+1$), the primitive $n$-th root of unity is $\omega =e^{\frac{2\mathit{𝑖𝜋}}{n}}$. In the case of NTT (i.e., ${\mathbb{Z}}_p[X]∕X^n+1$ where $p$ is a prime), the primitive $n$-th root of unity $\omega =g^{\frac{p-1}{n}}$, where $g$ is the generator of ${\mathbb{Z}}_p^{\times }$ and $n$ divides $p-1$ (a variation of Summary A-10.5 in §A-10.5).

Then, the point-value representation of polynomial $A(X)$ is $((x_0,y_0^{⟨a⟩}),(x_1,y_1^{⟨a⟩}),\cdots (x_{n-1},y_{n-1}^{⟨a⟩}))$, where:

$y_i^{⟨a⟩}=A({\omega }^i)=\underset{j=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_j\cdot {({\omega }^i)}^j=\sum _{j=0}^{n-1}{a}_j\cdot {\omega }^{\mathit{𝑖𝑗}}$.

We call the vector ${\overrightarrow{y}}^{⟨a⟩}=(y_0^{⟨a⟩},y_1^{⟨a⟩},\cdots ,y_{n-1}^{⟨a⟩})$ the Discrete Fourier Transform (DFT) of the coefficient vector $\overrightarrow{a}=(a_0,a_1,\cdots ,a_{n-1})$. We write this as ${\overrightarrow{y}}^{⟨a⟩}=\mathsf{\text{𝖣𝖥𝖳}}(\overrightarrow{a})$. As explained in §A-16.1, the computation of DFT takes $O(n^2)$, because we have to evaluate $n$ distinct $X$ values for a polynomial which has $n$ terms.

A-16.2.1 High-level Idea

FFT (or NTT) is an improved way of computing DFT which reduces the time complexity from $O(n^2)$ to $O(n\log <!--\; FUNCTION\; APPLICATION\; -->n)$. The high-level idea of FFT is to split the $(n-1)$-degree (or lesser degree) target polynomial $A(X)$ to evaluate into 2 half-degree polynomials $A_0(X)$ and $A_1(X)$ as follows:

$A(X)=a_0+a_{1}X+a_2{X}^2+\cdots +a_{n-1}{X}^{n-1}$

$A(X)=A_0(X^2)+X\cdot A_1(X^2)$ $A_0(X)=a_0+a_{2}X+a_4{X}^2+\cdots +a_{n-2}{X}^{\frac{n}{2}-1}$

$A_1(X)=a_1+a_{3}X+a_5{X}^2+\cdots +a_{n-2}{X}^{\frac{n}{1}-1}$

The above way of splitting a polynomial into two half-degree polynomials is called the Cooley-Tukey step. As we split $A(X)$ into two smaller-degree polynomials $A_0(X)$ and $A_1(X)$, evaluating $A(X)$ at $n$ distinct $n$-th roots of unity $\{{\omega }^0,{\omega }^1,{\omega }^2,\cdots ,{\omega }^{n-1}\}$ is equivalent to evaluating $A_0(X)$ and $A_1(X)$ at $n$ distinct squared $n$-th roots of unity $\{{({\omega }^2)}^0,{({\omega }^2)}^1,{({\omega }^2)}^2,\cdots ,{({\omega }^2)}^{n-1}\}$ and computing $A_0(X^2)+X\cdot A_1(X^2)$. However, remember that the primitive $n$-th root of unity $\omega$ has order $n$ (i.e., ${\omega }^n=1$ and ${\omega }^m\ne 1$ for all $m<n$). Therefore, the second half of $\{{({\omega }^2)}^0,{({\omega }^2)}^1,{({\omega }^2)}^2,\cdots ,{({\omega }^2)}^{n-1}\}$ is a repetition of the first half. This implies that we only need to evaluate $A_0(X)$ and $A_1(X)$ at ${\displaystyle \frac{n}{2}}$ distinct $x$ coordinates each instead of $n$ distinct coordinates, because the polynomial evaluation results for the other half are the same as those of the first half (as their input $x$ to the polynomial is the same).

We recursively split $A_0(X)$ and $A_1(X)$ into half-degree polynomials and evaluate them at half-counted $n$-th roots of unity. Then, the total rounds of splitting are $\log <!--\; FUNCTION\; APPLICATION\; -->n$, and each round’s maximum number of root-to-coefficient multiplications is $n$, which aggregates to $O(n\log <!--\; FUNCTION\; APPLICATION\; -->n)$.

A-16.2.2 Details

Suppose we have a polynomial ring which is either ${\mathbb{Z}}_p[X]∕X^8+1$ (i.e., over a finite field with prime $p$) or $ℝ[X]∕X^8+1$ (over complex numbers). We denote the primitive $(n=8)$-th roots of unity as $\omega$, and the $n$ distinct $(n=8)$-th roots of unity are: $\{{\omega }^0,{\omega }^1,{\omega }^2,{\omega }^3,{\omega }^4,{\omega }^5,{\omega }^6,{\omega }^7\}$.

Now, we define our target polynomial to evaluate as follows:

$A(X)=a_0+a_{1}X+a_2{X}^2+a_3{X}^3+a_4{X}^4+a_5{X}^5+a_6{X}^6+a_7{X}^7$

We split this 7-degree polynomial into the following two 3-degree polynomials (using the Cooley-Tukey step):

$A_0(X)=a_0+a_{2}X+a_4{X}^2+a_6{X}^3$

$A_1(X)=a_1+a_{3}X+a_5{X}^2+a_7{X}^3$

$A(X)=A_0(X^2)+X\cdot A_1(X^2)$

We recursively split the above two 3-degree polynomials into 1-degree polynomials as follows:

$A_{0,0}(X)=a_0+a_{4}X$, ... $A_{0,1}(X)=a_2+a_{6}X$

$A_0(X)=A_{0,0}(X^2)+X\cdot A_{0,1}(X^2)$

$A_{1,0}(X)=a_1+a_{5}X$, ... $A_{1,1}(X)=a_3+a_{7}X$

$A_1(X)=A_{1,0}(X^2)+X\cdot A_{1,1}(X^2)$

$A(X)=A_0(X^2)+X\cdot A_1(X^2)$

$A(X)=\underset{\text{FFT Level 3}}{\underbrace{\underset{\text{FFT Level 2}}{\underbrace{(\underset{\text{FFT Level 1}}{\underbrace{A_{0,0}(X^4)}}+X^2\cdot \underset{\text{FFT Level 1}}{\underbrace{A_{0,1}(X^4)}})}}+X\cdot \underset{\text{FFT Level 2}}{\underbrace{(\underset{\text{FFT Level 1}}{\underbrace{A_{1,0}(X^4)}}+X^2\cdot \underset{\text{FFT Level 1}}{\underbrace{A_{1,1}(X^4)}})}}}}$

To evaluate $A(X)$ at $n$ distinct roots of unity $X=\{{\omega }^0,{\omega }^1,\cdots ,{\omega }^7\}$, we evaluate the above formula’s each FFT level at $X=\{{\omega }^0,{\omega }^1,\cdots ,{\omega }^7\}$, from level $1\le l\le 3$.

FFT Level $𝐥=1$: We evaluate $A_{0,0}(X^4)$, $A_{0,1}(X^4)$, $A_{1,0}(X^4)$, and $A_{1,1}(X^4)$ at $X=\{{\omega }^0,{\omega }^1,\cdots ,{\omega }^7\}$. However, notice that plugging in $X=\{{\omega }^0,{\omega }^1,\cdots ,{\omega }^7\}$ to $X^4$ results in only 2 distinct values: ${\omega }^0$ and ${\omega }^4$. This is because the order of $\omega$ is $n$ (i.e., ${\omega }^n=1$), and thus ${({\omega }^0)}^4={({\omega }^2)}^4={({\omega }^4)}^4={({\omega }^6)}^4$, and ${({\omega }^1)}^4={({\omega }^3)}^4={({\omega }^5)}^4={({\omega }^7)}^4$. Therefore, we only need to evaluate $A_{0,0}(X^4)$, $A_{0,1}(X^4)$, $A_{1,0}(X^4)$, and $A_{1,1}(X^4)$ at 2 distinct $x$ values instead of 8, where each evaluation requires a constant number of arithmetic operations: computing 1 multiplication and 1 addition. As there are a total of 4 polynomials to evaluate (i.e., $A_{0,1}(X^4),A_{0,1}(X^4),A_{1,0}(X^4),A_{1,1}(X^4)$), we compute FFT a total of $4\cdot 2=8$ times.

FFT Level $𝐥=2$: Based on the evaluation results from FFT Level 1 as building blocks, we evaluate $A_0(X^2)$ and $A_1(X^2)$ at $X=\{{\omega }^0,{\omega }^1,\cdots ,{\omega }^7\}$. However, notice that plugging in $X=\{{\omega }^0,{\omega }^1,\cdots ,{\omega }^7\}$ to $X^2$ results in only 4 distinct values: ${\omega }^0$, ${\omega }^2$, ${\omega }^4$, and ${\omega }^6$. This is because the order of $\omega$ is $n$ (i.e., ${\omega }^n=1$), and thus ${({\omega }^0)}^2={({\omega }^4)}^2$, ${({\omega }^1)}^2={({\omega }^5)}^2$, ${({\omega }^2)}^2={({\omega }^6)}^2$, and ${({\omega }^3)}^2={({\omega }^7)}^2$. Therefore, we only need to evaluate $A_0(X^2)$ and $A_1(X^2)$ at 4 distinct $x$ values instead of 8, where each evaluation requires a constant number of arithmetic operations: computing 1 multiplication and 1 addition (where we use the results from FFT Level 1 as building blocks and FFT Level 2’s computation structure is the same as that of FFT Level 1). There are a total of 2 polynomials to evaluate (i.e., $A_0(X^2),A_1(X^2)$), thus we compute FFT a total of $2\cdot 4=8$ times.

FFT Level $𝐥=3$: Based on the evaluation results from FFT Level 2 as building blocks, we evaluate $A(X)$ at $X=\{{\omega }^0,{\omega }^1,\cdots ,{\omega }^7\}$. For this last level of computation, we need to evaluate all 8 distinct $X$ values, since they are all unique values, and each evaluation requires a constant number of arithmetic operations: computing 1 multiplication and 1 addition. There is a total of 1 polynomial to evaluate (i.e., $A(X)$), thus we compute FFT a total of $1\cdot 8=8$ times.

Generalization: Suppose that the degree of the target polynomial to evaluate is bound by $n$ degree and we define $L=\log <!--\; FUNCTION\; APPLICATION\; -->n$ (i.e., the total number of FFT levels). Then, the forward FFT operation requires a total of $L$ FFT levels, where each $l$-th level requires the evaluation of $2^{L-l}$ polynomials at $2^l$ distinct $X$ values. Therefore, the total number of FFT computations for forward FFT is: $\log <!--\; FUNCTION\; APPLICATION\; -->(n)\cdot (2^{L-l}\cdot 2^l)=2^L\log <!--\; FUNCTION\; APPLICATION\; -->n=n\log <!--\; FUNCTION\; APPLICATION\; -->n$. Therefore, the time complexity of forward FFT is $O(n\log <!--\; FUNCTION\; APPLICATION\; -->n)$.

Using the FFT technique, we reduce the number of $x$ points to evaluate into half as the level goes down (while the number of polynomials to evaluate doubles), and their growth and reduction cancel each other, resulting in $O(n)$ for each level. Since there are $\log <!--\; FUNCTION\; APPLICATION\; -->n$ such levels, the total time complexity is $O(n\log <!--\; FUNCTION\; APPLICATION\; -->n)$. The core enabler of this optimization is the special property of the $x$ evaluation coordinates: its power (i.e., ${\omega }^i$) is cyclic. To enforce this cyclic property, FFT requires the evaluation points of $x$ to be the $n$-th roots of unity.