A-16.4 Inverse FFT (or NTT)

Once 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 $A(X)=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{a}_i{X}^i$, the forward FFT process is computationally equivalent to evaluating the polynomial at $n$ distinct $n$-th roots of unity as follows:

$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{𝑖𝑗}}$

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

$y_i^{⟨a⟩}=W\cdot \overrightarrow{a}$, where $W=\left[\begin{array}{cccc}\hfill {({\omega }^0)}^0\hfill & \hfill {({\omega }^0)}^1\hfill & \hfill \cdots \hfill & \hfill {({\omega }^0)}^{n-1}\hfill \\ \hfill {({\omega }^1)}^0\hfill & \hfill {({\omega }^1)}^1\hfill & \hfill \cdots \hfill & \hfill {({\omega }^1)}^{n-1}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill {({\omega }^{n-1})}^0\hfill & \hfill {({\omega }^{n-1})}^1\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{n-1})}^{n-1}\hfill \end{array}\right]$ , $\overrightarrow{a}=(a_0,a_1,\cdots ,a_{n-1})$

We denote each element of $W$ as: ${(W)}_{i,j}={\omega }^{\mathit{𝑖𝑗}}$. 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^{⟨a⟩}=W^{-1}\cdot (W\cdot \overrightarrow{a})=(W^{-1}\cdot W)\cdot \overrightarrow{a}=I_n\cdot \overrightarrow{a}=\overrightarrow{a}$. As a solution, we propose the inverse matrix $W^{-1}$ as follows: ${(W^{-1})}_{j,k}=n^{-1}\cdot {\omega }^{-\mathit{𝑗𝑘}}$. 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 }^{-\mathit{𝑗𝑘}}\cdot {\omega }^{\mathit{𝑘𝑖}})=n^{-1}\cdot \sum _{k=0}^{n-1}{\omega }^{-\mathit{𝑗𝑘}}\cdot {\omega }^{\mathit{𝑘𝑖}}=n^{-1}\cdot \sum _{k=0}^{n-1}{\omega }^{(i-j)\cdot k}$

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

If $j=i$, the above condition holds, because ${(W^{-1}\cdot W)}_{j,i}=n^{-1}\cdot \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{(0)\cdot k}=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 }^{(i-j)\cdot k}$. Leveraging the Geometric Sum formula $\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{x}^i={\displaystyle \frac{x^n-1}{x-1}}$,

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

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

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

# Here, the denominator can’t be 0, since $i\ne j$ and $-n<i-j<n$ (as $0\le i<n$ and $0\le j<n$)

$=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 follows:

$\overrightarrow{c}=W^{-1}\cdot y_i^{⟨c⟩}$, where $c_i=n^{-1}\cdot \underset{j=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{y}_i^{⟨c⟩}\cdot {\omega }^{-\mathit{𝑖𝑗}}$

The above inverse FFT computation is equivalent to evaluating the polynomial $\widehat{C}(X)=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{y}_i^{⟨c⟩}\cdot X^i$ at $X=\{{\omega }^0,{\omega }^{-1},{\omega }^{-2},\cdots ,{\omega }^{-(n-1)}\}$, which is equivalent to evaluating $\widehat{C}(X)$ at $X=\{{\omega }^0,{\omega }^{n-1},{\omega }^{n-2},\cdots ,{\omega }^1\}$. For this evaluation, we can use the same optimization technique explained in the forward FFT process (§A-16.2.2) whose time complexity is $O(n\log <!--\; FUNCTION\; APPLICATION\; -->n)$.