# VI. Number Theoretic Transform (NTT)

[TOC]

## Introduction
This is the sixth chapter of [Understanding Homomorphic Encryption](https://hackmd.io/@spockwall/rJgV4qFgZe) series. The Number Theoretic Transform (NTT) is a powerful mathematical tool that has become increasingly important in developing Post Quantum Cryptography (PQC) and Homomorphic Encryption (HE). Its ability to efficiently calculate polynomial multiplication using the convolution theorem with a quasilinear complexity $O(n\text{log} n)$ instead of $O(n^2)$ when implemented with Fast Fourier Transform-style algorithms has made it a key component in modern cryptography. FFT-style NTT algorithm or fastNTT is particularly useful in lattice-based cryptography.

## Preliminaries
### Polynomial Ring
- $\mathbb{Z}[X]=\{a_0+a_1x+a_2x^2+ ... + a_nx^N, a_i \in \mathbb{Z} , i\in[0,N] \}$
- $\mathbb{R}[X]=\{a_0+a_1x+a_2x^2+ ... + a_nx^N, a_i \in \mathbb{R} , i\in[0,N] \}$
- $\mathcal{R}[X]=\{a_0+a_1x+a_2x^2+ ... + a_nx^N, a_i \in \mathcal{R} , i\in[0,N] \}$
- $\mathcal{R}$ represents a ring which can be $\mathbb{Z}, \mathbb{Z}_q=\mathbb{Z}/q\mathbb{Z}, ...$
### Quotient of a Polynomial Ring
- Let a polynomial ring $\mathbb{Z}[X]$.
- If $\mathbb{Z}[X]$ is factored out by an ideal generated by $f(x)$, then we define a quotient of a polynomial ring $\mathbb{Z}[X]/\langle f(x)\rangle$. Also, we can further define $\mathbb{Z}_q[X]/\langle f(x)\rangle$ as the polynomials in $\mathbb{Z}[X]/\langle f(x)\rangle$, whose coeffcients are modulo by $q$
- Example:
- $\mathbb{Z}_5[x]/<x^2+1>=\{0,1,2,3,4,x,x+1,x+2,x+3,x+4\}$
### Schoolbook method for polynomial multiplication
- $p(x)=1+2x+3x^2+4x^3$
- $q(x)=5+6x+7x^2+8x^3$
- Schoolbook method
\begin{array}{l}
\phantom{..}1+2x+3x^2+4x^3 \\
\times 5+6x+7x^2+8x^3 \\
\hline
\phantom{..}5+10x+15x^2+20x^3 \\
\phantom{.......}6x+12x^2+18x^3+24x^4 \\
\phantom{.............}7x^2+14x^3+21x^4+28x^5 \\
\phantom{....................}8x^3+16x^4+24x^5+32x^6 \\
\hline
\phantom{..}5+16x+34x^2+60x^3+61x^4+52x^5+32x^6
\end{array}
- $p(x)\cdot q(x)=5+16x+34x^2+60x^3+61x^4+52x^5+32x^6$
- The complexity is $O(n^2)$
### Cyclic Convolution
- Also called **positive wrapped convolution (PWC**)
- Suppose that $p(x)$ and $q(x)$ are polynomials of degree $n−1$ in the quotient ring $\mathbb{Z}[x]/(x^n− 1)$
- Let $n=4$, the result of **PWC** is
\begin{aligned}
PWC(x)&=p(x)\cdot q(x)\text{ mod } x^4-1\\
&=5+16x+34x^2+60x^3+61x^4+52x^5+32x^6 \text{ mod }x^4−1\\
&=66+68x+66x^2+60x^3 \text{ mod }x^4−1
\end{aligned}
- Note that to modulo $(x^4−1)$ is simply replacing $x^4$ with $1$.

### Negacyclic Convolution
- Also called **negative wrapped convolution (NWC)**
- Suppose that $p(x)$ and $q(x)$ are polynomials of degree $n−1$ in the quotient ring $\mathbb{Z}[x]/(x^n+1)$
- Let $n=4$, the result of **NWC** is
\begin{aligned}
NWC(x)&=p(x)\cdot q(x)\text{ mod } x^4+1\\
&=5+16x+34x^2+60x^3+61x^4+52x^5+32x^6 \text{ mod } x^4+1\\
&=-56-36x+2x^2+60x^3 \text{ mod } x^4+1\\
\end{aligned}
- Note that to modulo $(x^4+1)$ is simply replacing $x^4$ with $-1$.
- $PWC$ and $NWC$ are handled differently in Fast-NTT implementations.

### Primitive n-th Root of Unity
- See [the first chapter](https://hackmd.io/TDwmj5IlRxiDeEpwdngUEQ) for more details.
- An n-th root of unity, where $n$ is a positive integer, is a number $z$ satisfying the equation.
\begin{equation}
z^n=1
\end{equation}
- In complex $\mathbb{C}$, $z$ is in form:
\begin{equation}
z=e^{\frac{2k\pi i}{n}}=cos{\frac{2k\pi}{n}}+i\cdot sin{\frac{2k\pi}{n}}, \quad i=\sqrt{-1}, \,\,k =0,1,2,...,n-1
\end{equation}
- Visualization of root of unity in a unit circle centering at (0,0).
- An n-th root of unity is said to be **primitive** if it is not an m-th root of unity for some smaller $m$, that is if
\begin{aligned}
{\displaystyle z^{n}=1\quad {\text{and}}\quad z^{m}\neq 1{\text{ for }}m=1,2,3,\ldots ,n-1.}
\end{aligned}
- Define a primitive n-th root of unity $\omega$ in $\mathbb{Z}_q$, we get
\begin{equation}
\begin{cases}
\,\,\omega^n=1 \,\text{ mod }\, q\\
\,\,\omega^k\not=1 \,\text{ mod }\, q \text{, for k<n}
\end{cases}
\end{equation}
- In a ring $\mathbb{Z}_{7681}$ and $n = 4$, the 4-th root of unity which satisfy the condition $ω^4 = 1$ mod $7681$ are $\{3383, 4298, 7680\}$. Out of three roots, $7680$ is not a primitive n-th root of unity, as there exist $k = 2 < n$ that satisfy $ω^2 = 1$ mod 7681. Therefore $ω = 3383$ or $ω = 4298$ are the primitive 4-th root of unity in $\mathbb{Z}_{7681}$.

## NTT
### Polynomial representaion
- There are two common form for polynomials representaion, cofficient representation and Evaluation representation.
- Coefficient: $p(x)=1+2x+3x^2+4x^3 \rightarrow [1,2,3,4]$
- Evaluation at $x=1, x=2, x=3, x=4$: $p(x)=1+2x+3x^2+4x^3 \rightarrow [(1,10),(2,49),(3,142),(4,313)]$
- A degree $n-1$ polynomial can be reconstructed by interpolation with n distinct points.
- We can dot product 2 vectors in evaluation representation and reconstruct the result to be the multiplication of two polynomials. Note that we will evalute at the roots of unity. (We will learn why soon.)
- We can now define the general form of NTT: $\hat{\mathbf{a}_j}=\Sigma_{i=0}^{n-1}\omega^{ij}a_i$, evaluating a polynomial at $x=1, \omega, \omega^2, \omega^3$
- For example, in $\mathbb{Z}_{7681}[x]/(x^4−1)$
- $p(x)=1+2x+3x^2+4x^3$
- $\omega^4=1\rightarrow \omega=3383$ or $4298$, we use $\omega=3383$
\begin{aligned}
\hat{\mathbf{p}} =
\begin{bmatrix}
\omega^{0 \times 0} & \omega^{0 \times 1} & \omega^{0 \times 2} & \omega^{0 \times 3} \\
\omega^{1 \times 0} & \omega^{1 \times 1} & \omega^{1 \times 2} & \omega^{1 \times 3} \\
\omega^{2 \times 0} & \omega^{2 \times 1} & \omega^{2 \times 2} & \omega^{2 \times 3} \\
\omega^{3 \times 0} & \omega^{3 \times 1} & \omega^{3 \times 2} & \omega^{3 \times 3}
\end{bmatrix}
\begin{bmatrix}
1 \\ 2 \\ 3 \\ 4
\end{bmatrix} =
\begin{bmatrix}
1\cdot(\omega^0)^0 + 2\cdot(\omega^0)^1 + 3\cdot(\omega^0)^2 + 4\cdot(\omega^0)^3 \\
1\cdot(\omega^1)^0 + 2\cdot(\omega^1)^1 + 3\cdot(\omega^1)^2 + 4\cdot(\omega^1)^3 \\
1\cdot(\omega^2)^0 + 2\cdot(\omega^2)^1 + 3\cdot(\omega^2)^2 + 4\cdot(\omega^2)^3 \\
1\cdot(\omega^3)^0 + 2\cdot(\omega^3)^1 + 3\cdot(\omega^3)^2 + 4\cdot(\omega^3)^3
\end{bmatrix}
\end{aligned}
\begin{aligned}
\hat{\mathbf{p}} =
\begin{bmatrix}
\omega^0 & \omega^0 & \omega^0 & \omega^0 \\
\omega^0 & \omega^1 & \omega^2 & \omega^3 \\
\omega^0 & \omega^2 & \omega^4 & \omega^6 \\
\omega^0 & \omega^3 & \omega^6 & \omega^9
\end{bmatrix}
\begin{bmatrix}
1 \\ 2 \\ 3 \\ 4
\end{bmatrix}=
\begin{bmatrix}
\omega^0 & \omega^0 & \omega^0 & \omega^0 \\
\omega^0 & \omega^1 & \omega^2 & \omega^3 \\
\omega^0 & \omega^2 & \omega^0 & \omega^2 \\
\omega^0 & \omega^3 & \omega^2 & \omega^1
\end{bmatrix}
\begin{bmatrix}
1 \\ 2 \\ 3 \\ 4
\end{bmatrix} =
\begin{bmatrix}
10 \\ 913 \\ 7679 \\ 6764
\end{bmatrix}
\end{aligned}
- $q(x)=5+6x+7x^2+8x^3$
- $\omega^4=1$, we use $\omega=3383$
\begin{aligned}
\hat{\mathbf{q}} =
\begin{bmatrix}
\omega^{0 \times 0} & \omega^{0 \times 1} & \omega^{0 \times 2} & \omega^{0 \times 3} \\
\omega^{1 \times 0} & \omega^{1 \times 1} & \omega^{1 \times 2} & \omega^{1 \times 3} \\
\omega^{2 \times 0} & \omega^{2 \times 1} & \omega^{2 \times 2} & \omega^{2 \times 3} \\
\omega^{3 \times 0} & \omega^{3 \times 1} & \omega^{3 \times 2} & \omega^{3 \times 3}
\end{bmatrix}
\begin{bmatrix}
5 \\ 6 \\ 7 \\ 8
\end{bmatrix} =
\begin{bmatrix}
26 \\ 913 \\ 7679 \\ 6764
\end{bmatrix}
\end{aligned}
- $\hat{\mathbf{p}}^T \cdot \hat{\mathbf{q}}=[260, 4021, 4, 3660]$
- Remember the result, after we learn inverse-NTT, we will resuse it again.

## Inverse NTT
- If we have a evaluation form of a polynomial, we can recontruct it back by interpolation.
- The result of NTT is in evaluation form, so we can reconstruct the polynomial back.
- For example: $\hat{\mathbf{p}}=[10, 913, 7679, 6764]\rightarrow p(x)=1+2x+3x^2+4x^3$
- We define the inverse matrix of NTT:
\begin{equation}
a_i=n^{-1}\Sigma_{j=0}^{n-1}\omega^{-ij}\hat{\mathbf{a}_j},
\end{equation}
- Note that $n^{-1}*n \,\,\text{mod}\,\,7681=1\rightarrow n^{-1}=5761$, and we get
\begin{aligned}
p =n^{-1}
\begin{bmatrix}
\omega^{-0 \times 0} & \omega^{-0 \times 1} & \omega^{-0 \times 2} & \omega^{-0 \times 3} \\
\omega^{-1 \times 0} & \omega^{-1 \times 1} & \omega^{-1 \times 2} & \omega^{-1 \times 3} \\
\omega^{-2 \times 0} & \omega^{-2 \times 1} & \omega^{-2 \times 2} & \omega^{-2 \times 3} \\
\omega^{-3 \times 0} & \omega^{-3 \times 1} & \omega^{-3 \times 2} & \omega^{-3 \times 3}
\end{bmatrix}
\begin{bmatrix}
10 \\ 913 \\ 7679 \\ 6764
\end{bmatrix} =
\begin{bmatrix}
1 \\ 2 \\ 3 \\ 4
\end{bmatrix}
\end{aligned}
- Now, we can turn $\hat{\mathbf{p}}^T \cdot \hat{\mathbf{q}}=[260, 4021, 4, 3660]$ back into polynomial form in the ring $\mathbb{Z}[x]/(x^4−1)$.
\begin{aligned}
p(x)\cdot q(x) =n^{-1}
\begin{bmatrix}
\omega^{-0 \times 0} & \omega^{-0 \times 1} & \omega^{-0 \times 2} & \omega^{-0 \times 3} \\
\omega^{-1 \times 0} & \omega^{-1 \times 1} & \omega^{-1 \times 2} & \omega^{-1 \times 3} \\
\omega^{-2 \times 0} & \omega^{-2 \times 1} & \omega^{-2 \times 2} & \omega^{-2 \times 3} \\
\omega^{-3 \times 0} & \omega^{-3 \times 1} & \omega^{-3 \times 2} & \omega^{-3 \times 3}
\end{bmatrix}
\begin{bmatrix}
260 \\ 4021 \\ 4 \\ 3660
\end{bmatrix} =
\begin{bmatrix}
66 \\ 68 \\ 66 \\ 60
\end{bmatrix}
\end{aligned}
\begin{equation}
p(x)\cdot q(x) \,\,\text{mod}\,\, (x^4− 1)=66+68x+66x^2+60x^3 \in \mathbb{Z}[x]/(x^4− 1)
\end{equation}
- We have to discuss the correctness of $p\cdot q$, since the $p\cdot q$ is originally a degree-6 polynomial, and degree-6 polynomial must be reconstructed by interpolation with 7 distinct points.
- We do know that $p(x)\cdot q(x)=r(x)+(x^4-1)g(x)$, where $r(x)$ is a polynomial of degree 3. Thus, if we evaluate $p(x)\cdot q(x)$ at $x=1, \omega, \omega^2, \omega^3$, which are root of $x^4-1$, the term: $(x^4-1)g(x)$ will be cancelled. We get
\begin{align*}
p(1)\cdot q(1)&=r(1) \\
p(\omega)\cdot q(\omega)&=r(\omega) \\
p(\omega^2)\cdot q(\omega^2)&=r(\omega^2) \\
p(\omega^3)\cdot q(\omega^3)&=r(\omega^3) \\
\end{align*}
- It is equivalent to evaluate $r(x)$ at $x=1, \omega, \omega^2, \omega^3$ as a form of interpolation, and $r(x)$ is the value of $p(x)\cdot q(x)$ in ring $\mathbb{Z}[x]/(x^4− 1)$, since $(x^4-1)g(x)$ is cancelled by $(x^4-1)$.

## Fast-NTT
- The complexity of naive NTT is $O(n^2)$, no faster than the schoolbook method. In this section, we will leverage divide and conquer to reduce the complexity from $O(n^2)$ to $O(n\,\text{log}\,n)$.
- Considering an polynomial $f(x)$ evaluted at $\omega_n^k$, where $\omega_n$ is an primitive n-th root of unity.
\begin{split}
f(ω^k_n) &= \displaystyle\sum_{i = 0}^{n - 1} a_i\,ω^{ki}_n \\
&= \displaystyle\sum_{i = 0}^{\frac{n}{2} - 1} a_{2i}\,ω^{2ki}_n \,+\, ω^k_n\displaystyle\sum_{i = 0}^{\frac{n}{2} - 1}a_{2i + 1}\,ω^{2ki}_n \\
&= f_{even}(\omega_n^{2k})+\omega_n^k\cdot f_{odd}(\omega_n^{2k})
\end{split}
- We seperate f(x) by even terms and odd terms, and we get $f_{odd}(x^2)$ and $f_{even}(x^2)$. After that, we can do further recursion to realize divide and conquer. See following example.
- Let $f(x)=a_0+a_1 x+\cdots a_7 x^7 \Rightarrow$ calculate $f(w)$
Recursively calculating $f_{odd}(x^2)$ and $f_{even}(x^2)$, we can evaluate $f(\omega)$ in $O(n\,\text{log}\,n)$

### Fast-NTT in circuits
- In practical, it more often to implement fast-ntt in circuit form. Two kinds of circuits are used as follows.
- The following, we show the circuit evaluating $f(x)=a_0+a_1x+...+a_7x^7\in \mathbb{Z}[x]/(x^8− 1)$ at $x=\omega_8^0, \omega_8^1, \omega_8^2,...,\omega_8^7$
In the above circuit, $\hat{a}_i$ stands for $f(\omega_n^i)$. The following figure shows how it works.
- Using Gentlemen-Sande butterfly to reconstruct it back to the polynomial.
- It is available to implement Fast-NTT iteratively but not recusively.

## Standards
This table shows the different polynomial rings that are used in modern lattice-based cryptosystems. Cryptographers apply several tricks to accelerate FFT/NTT depending on the ring, such as Incomplete FFT, or Good's trick.


## Reference
- https://www.youtube.com/watch?v=h7apO7q16V0
- https://arxiv.org/pdf/2211.13546
- https://fprox.substack.com/p/number-theoretic-transform-with-rvv
- https://cryptographycaffe.sandboxaq.com/posts/ntt-02/