---
# System prepended metadata

title: VI. Number Theoretic Transform (NTT)

---

# 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).
![unity](https://hackmd.io/_uploads/ryWWJcf6kl.png)
- 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)$
![IMG_0319](https://hackmd.io/_uploads/Bkf_lJ7pJx.jpg)
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.
![Screenshot 2025-03-27 at 6.21.55 PM](https://hackmd.io/_uploads/SyleDozaJx.png)
- 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$
![Screenshot 2025-03-27 at 9.11.36 PM](https://hackmd.io/_uploads/rkuqApfpke.png =75%x)
In the above circuit, $\hat{a}_i$ stands for $f(\omega_n^i)$. The following figure shows how it works.
![Screenshot 2025-03-27 at 9.15.07 PM](https://hackmd.io/_uploads/ByzEeAGT1e.png =90%x)
- 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.

![Screenshot 2025-03-27 at 9.56.14 PM](https://hackmd.io/_uploads/SyXmFAGake.png)


## 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/