A-16.2 Forward FFT (or NTT)

We assume a polynomial ring of $ℝ[X]∕(X^n+1)$ for FFT, and ${\mathbb{Z}}_p[X]∕(X^n+1)$ for NTT (where $X^n+1$ is a cyclotomic polynomial). The $x$ coordinates to evaluate the target polynomial are the $n$ distinct roots of $X^n+1$, which are ${\omega }^1$, ${\omega }^3,\dots ,{\omega }^{2n-1}$, where $\omega$ is the primitive $2n$-th root of unity. Then, the point-value representation of the 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 }^{2i+1})=\underset{j=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_j\cdot {({\omega }^{2i+1})}^j=\sum _{j=0}^{n-1}{a}_j\cdot {\omega }^{(2i+1)\cdot j}$.

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 the DFT takes $O(n^2)$, because we have to evaluate $n$ distinct $X$ values for a polynomial that has $n$ terms.

A-16.2.1 High-level Idea

FFT (or NTT) is an improved method for computing the 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-1}{X}^{\frac{n}{2}-1}$

The above method 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 the odd-powered primitive $2n$-th roots of unity $\{{\omega }^1,{\omega }^3,{\omega }^5,\cdots ,{\omega }^{2n-1}\}$is equivalent to evaluating $A_0(X)$ and $A_1(X)$ at $n$ distinct squared $n$-th roots of unity $\{{({\omega }^2)}^1,{({\omega }^2)}^3,{({\omega }^2)}^5,\dots ,{({\omega }^2)}^{2n-1}\}$ and computing $A_0(X^2)+X\cdot A_1(X^2)$. However, remember that the primitive $2n$-th root of unity $\omega$ has order $2n$ (i.e., ${\omega }^{2n}=1$ and ${\omega }^m\ne 1$ for all $m<2n$). Therefore, the second half of $\{{({\omega }^2)}^1,{({\omega }^2)}^3,{({\omega }^2)}^5,\dots ,{({\omega }^2)}^{2n-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 (i.e., $n∕2$) $n$-th roots of unity. Then, the total number of rounds of splitting is $\log <!--\; FUNCTION\; APPLICATION\; -->n$, and the maximum number of root-to-coefficient multiplications in each round is $n$, which aggregates to $O(n\log <!--\; FUNCTION\; APPLICATION\; -->n)$.

A-16.2.2 Details

Suppose we have a polynomial ring that 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 by $\omega$ a primitive $(2n=16)$-th root of unity, and the 8 distinct roots of $X^8+1$ are: $\{{\omega }^1,{\omega }^3,{\omega }^5,{\omega }^7,{\omega }^9,{\omega }^{11},{\omega }^{13},{\omega }^{15}\}$.

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 two 3-degree polynomials above 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 the $n$ distinct roots $X=\{{\omega }^1,{\omega }^3,\dots ,{\omega }^{15}\}$, we evaluate each FFT level of the above formula at $X=\{{\omega }^1,{\omega }^3,\cdots ,{\omega }^{15}\}$, starting 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 }^1,{\omega }^3,\cdots ,{\omega }^{15}\}$. However, notice that plugging in $X=\{{\omega }^1,{\omega }^3,\cdots ,{\omega }^{15}\}$ to $X^4$ results in only 2 distinct values: ${\omega }^0$ and ${\omega }^8$. This is because the order of $\omega$ is $2n$ (i.e., ${\omega }^{2n}=1$), and thus ${({\omega }^1)}^4={({\omega }^5)}^4={({\omega }^9)}^4={({\omega }^{13})}^4$, and ${({\omega }^3)}^4={({\omega }^7)}^4={({\omega }^{11})}^4={({\omega }^{15})}^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,0}(X^4),A_{0,1}(X^4),A_{1,0}(X^4),A_{1,1}(X^4)$), we compute the 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 }^1,{\omega }^3,\cdots ,{\omega }^{15}\}$. However, notice that plugging in $X=\{{\omega }^1,{\omega }^3,\cdots ,{\omega }^{15}\}$ to $X^2$ results in only 4 distinct values: ${\omega }^1$, ${\omega }^5$, ${\omega }^9$, and ${\omega }^{13}$. This is because the order of $\omega$ is $2n$ (i.e., ${\omega }^{2n}=1$), and thus ${({\omega }^1)}^2={({\omega }^9)}^2$, ${({\omega }^3)}^2={({\omega }^{11})}^2$, ${({\omega }^5)}^2={({\omega }^{13})}^2$, and ${({\omega }^7)}^2={({\omega }^{15})}^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 the computational structure of FFT Level 2 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 the 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 }^1,{\omega }^3,\cdots ,{\omega }^{15}\}$. 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 the FFT a total of $1\cdot 8=8$ times.

Generalization: Suppose that the degree of the target polynomial to evaluate is at most $n-1$ (with $n$ terms), 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 the forward FFT is: ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{l=1}^L(2^{L-l}\cdot 2^l)=L\cdot 2^L=n\log <!--\; FUNCTION\; APPLICATION\; -->n$ . Therefore, the time complexity of the forward FFT is $O(n\log <!--\; FUNCTION\; APPLICATION\; -->n)$.

Using the FFT technique, we reduce the number of $x$ points to evaluate to half as the level decreases (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 odd-powered primitive $2n$-th roots of unity.