A-16.4 Inverse FFT (or NTT)

So far, we have computed:

$C(X)$ : $((x_0,y_0^{⟨c⟩}),(x_1,y_1^{⟨c⟩}),\cdots (x_{n-1},y_{n-1}^{⟨c⟩}))$, where $y_i^{⟨c⟩}=y_i^{⟨a⟩}\cdot y_i^{⟨b⟩}$

Our final step is to convert $y_i^{⟨c⟩}$ back to $\overrightarrow{c}$, the polynomial coefficients of $C(X)$. We call this reversing operation the inverse FFT.

Given an $(n-1)$-degree polynomial $C(X)=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{c}_i{X}^i$, the forward FFT process is computationally equivalent to evaluating the polynomial at $n$ distinct $n$-th roots of $X^n+1$ as follows:

$y_i^{⟨c⟩}=C({\omega }^{2i+1})=\underset{j=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{c}_j\cdot {({\omega }^{2i+1})}^j=\sum _{j=0}^{n-1}{c}_j\cdot {\omega }^{(2i+1)j}$

The above evaluation is equivalent to computing the following matrix-vector multiplication:

$y_i^{⟨c⟩}=W\cdot \overrightarrow{c}$, where $W=\left[\begin{array}{cccc}\hfill {({\omega }^1)}^0\hfill & \hfill {({\omega }^1)}^1\hfill & \hfill \cdots \hfill & \hfill {({\omega }^1)}^{n-1}\hfill \\ \hfill {({\omega }^3)}^0\hfill & \hfill {({\omega }^3)}^1\hfill & \hfill \cdots \hfill & \hfill {({\omega }^3)}^{n-1}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill {({\omega }^{2n-1})}^0\hfill & \hfill {({\omega }^{2n-1})}^1\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{2n-1})}^{n-1}\hfill \end{array}\right]$, $\overrightarrow{c}=(c_0,c_1,\cdots ,c_{n-1})$

We denote each element of $W$ as: ${(W)}_{i,j}={\omega }^{(2i+1)j}$. The inverse FFT is a process of reversing the above computation. For this inversion, our goal is to find an inverse matrix $W^{-1}$ such that $W^{-1}\cdot y_i^{⟨c⟩}=W^{-1}\cdot (W\cdot \overrightarrow{c})=(W^{-1}\cdot W)\cdot \overrightarrow{c}=I_n\cdot \overrightarrow{c}=\overrightarrow{c}$. As a solution, we propose the inverse matrix $W^{-1}$ as follows:

${(W^{-1})}_{j,k}=n^{-1}\cdot {\omega }^{-(2k+1)j}$

Now, we will show why $W^{-1}\cdot W=I_n$. Each element of $W^{-1}\cdot W$ is computed as:

${(W^{-1}\cdot W)}_{j,i}=\underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(n^{-1}\cdot {\omega }^{-(2k+1)j}\cdot {\omega }^{(2k+1)i})=n^{-1}\cdot \sum _{k=0}^{n-1}{\omega }^{(2k+1)(i-j)}$

In order for $W^{-1}\cdot W$ to be $I_n$, the following should hold:

If $j=i$ holds, the above condition is satisfied because:

${(W^{-1}\cdot W)}_{j,i}=n^{-1}\cdot \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{(2k+1)(0)}=n^{-1}\cdot \sum _{k=0}^{n-1}1=n^{-1}\cdot n=1$

In the case of $j\ne i$, we will leverage the Geometric Sum formula $\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{x}^i={\displaystyle \frac{x^n-1}{x-1}}$ (the proof is provided below):

Our goal is to compute $\underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{(2k+1)(i-j)}={\omega }^{i-j}\sum _{k=0}^{n-1}{({\omega }^{2(i-j)})}^k$. Leveraging the Geometric Sum formula with $x={\omega }^{2(i-j)}$:

${\omega }^{i-j}\underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{({\omega }^{2(i-j)})}^k={\omega }^{i-j}{\displaystyle \frac{{({\omega }^{2(i-j)})}^n-1}{{\omega }^{2(i-j)}-1}}$

$={\omega }^{i-j}{\displaystyle \frac{{({\omega }^{2n})}^{i-j}-1}{{\omega }^{2(i-j)}-1}}$

$={\omega }^{i-j}{\displaystyle \frac{{(1)}^{i-j}-1}{{\omega }^{2(i-j)}-1}}$ $▹$ since the order of $\omega$ is $2n$, ${\omega }^{2n}=1$

$▹$Here, the denominator can’t be 0. Since $i\ne j$ and $|i-j|<n$, the exponent $2(i-j)$ is not a multiple of $2n$.

$=0$

Thus, ${(W^{-1}\cdot W)}_{j,i}$ is 1 if $j=i$, and 0 if $j\ne i$. Therefore, the inverse FFT can be computed as $\overrightarrow{c}=W^{-1}\cdot y^{⟨c⟩}$, where:

$c_i={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{j=0}^{n-1}{(W^{-1})}_{i,j}\cdot y_j^{⟨c⟩}$

$\underset{j=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\left(n^{-1}\cdot {\omega }^{-(2j+1)i}\right)\cdot y_j^{⟨c⟩}$ $▹$ since ${(W^{-1})}_{j,k}=n^{-1}\cdot {\omega }^{-(2k+1)j}$, and ${(W^{-1})}_{i,j}=n^{-1}\cdot {\omega }^{-(2j+1)i}$

$=n^{-1}\cdot \underset{j=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{y}_j^{⟨c⟩}\cdot {\omega }^{-(2j+1)i}$

$=n^{-1}\underset{j=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{y}_j^{⟨c⟩}\cdot ({\omega }^{-2\mathit{𝑗𝑖}}\cdot {\omega }^{-i})$ $▹$ since ${\omega }^{-(2j+1)i}={\omega }^{-2\mathit{𝑗𝑖}-i}={\omega }^{-2\mathit{𝑗𝑖}}\cdot {\omega }^{-i}$

$=n^{-1}{\omega }^{-i}\underset{j=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{y}_j^{⟨c⟩}{({\omega }^{-2})}^{\mathit{𝑗𝑖}}$

By reusing the recursive splitting technique explained in the forward process (§A-16.2.2), this inverse operation also achieves a time complexity of $O(n\log <!--\; FUNCTION\; APPLICATION\; -->n)$.