非常好的教程：https://eprint.iacr.org/2024/585.pdf

给定度为 n-1 的多项式 G(x) 和 H(x)，可以得到乘法：

$$ Y(x)=G(x) \cdot H(x) = \sum^{2(n-1)}_{k=0}y_kx^k $$

其中 $y_k=\sum^k_{i=0}g_kh_{k-i} \space \text{mod} \space q$

A cyclic convolution or positive wrapped convolution 定义如下：

$$ PWC(x) = Y(x) \space \text{mod} \space (x^n-1) = \sum^{n-1}_{k=0}c_kx^k $$

A negacyclic convolution or negative wrapped convolution 定义如下：

$$ NWC(x)=Y(x) \space \text{mod} \space (x^n+1) = \sum^{n-1}_{k=0}c_kx^k $$

NTT

NTT（数论变换，Number Theoretic Transform）是 DFT 在有限域上的模拟。将 DFT 中的复数单位根替换为有限域中的 n 次本原单位根，公式：

$$ \hat{a_j}=\sum^{n-1}_{i=0}w^{ij}a_i \space \text{mod} \space p $$

输入和输出都是有限域元素，计算中没有浮点数和舍入误差，结果精确。存在高效的算法 FFT

n 次本原单位根（primitive n-th root of unity）指的是一个数 ω，满足：

• $ω^n=1$ （是 n 次单位根，n-th root of unity）
• $ω^k \ne 1$ 对于任意 $1 \le k < p$ （是本原的，primitive root）

n 次本原单位根并不是唯一的。

例如 $f(x)=1 + 2x + 3x^2+4x^3$，系数向量 $a=[1,2,3,4]$，假设 ω 为 n 次本原单位根，可以得到

$$ NTT(a) = \hat{a} = \begin{bmatrix} w^{0 \times 0} & w^{0 \times 1} & w^{0 \times 2} & w^{0 \times 3} \\ w^{1 \times 0} & w^{1 \times 1} & w^{1 \times 2} & w^{1 \times 3} \\ w^{2 \times 0} & w^{2 \times 1} & w^{2 \times 2} & w^{2 \times 3} \\ w^{3 \times 0} & w^{3 \times 1} & w^{3 \times 2} & w^{3 \times 3} \\ \end{bmatrix} \begin{bmatrix} 1 \\ 2\\ 3 \\ 4 \\ \end{bmatrix} = \begin{bmatrix} w^{0} & w^{0} & w^{0} & w^{0} \\ w^{0} & w^{1} & w^{2} & w^{3} \\ w^{0} & w^{2} & w^{0} & w^{2} \\ w^{0} & w^{3} & w^{2} & w^{1} \\ \end{bmatrix} \begin{bmatrix} 1 \\ 2\\ 3 \\ 4 \\ \end{bmatrix} $$

对于 $\text{Z}_{7681}$ 中的 n 次本原单位根 $w=3383$，可以算出 $\hat{a}=\begin{bmatrix} 10 \\ 913\\ 7679 \\ 6764 \\ \end{bmatrix}$

INTT

INTT（逆数论变换，Inverse Number Theoretic Transform）定义如下：

$$ a_i = n^{-1} \sum^{n-1}_{j=0} w^{-ij} \hat{a}_j \space \text{mod} \space p $$

对于 $\text{Z}_{7681}$ 中的 n 次本原单位根 $w=3383$ 及 $NTT(a)=\hat{a}=\begin{bmatrix} 10 \\ 913\\ 7679 \\ 6764 \\ \end{bmatrix}$，可以算出：

$$ a = n^{-1} \begin{bmatrix} w^{-0 \times 0} & w^{-0 \times 1} & w^{-0 \times 2} & w^{-0 \times 3} \\ w^{-1 \times 0} & w^{-1 \times 1} & w^{-1 \times 2} & w^{-1 \times 3} \\ w^{-2 \times 0} & w^{-2 \times 1} & w^{-2 \times 2} & w^{-2 \times 3} \\ w^{-3 \times 0} & w^{-3 \times 1} & w^{-3 \times 2} & w^{-3 \times 3} \\ \end{bmatrix}\begin{bmatrix} 10 \\ 913\\ 7679 \\ 6764 \\ \end{bmatrix} = \begin{bmatrix} 1 \\ 2\\ 3 \\ 4 \\ \end{bmatrix} $$

计算 Positive-Wrapped Convolutions

$f(x) \cdot g(x) \space \text{mod} \space (x^n-1)= INTT(NTT(a) \cdot NTT(b)) $

Primitive 2n-th Root of Unity

2n 次本原单位根指的是一个数 $\psi$，满足：

• $\psi^2=w \space \text{mod} \space p$，其中 $w$ 是 n 次本原单位根
• $\psi^n = -1 \space \text{mod} \space p$

基于 $\psi$ 的 NTT

$\hat{a}=NTT^{\psi}(a)$ 为：

$$ \hat{a}=\sum^{n-1}_{i=0}\psi^iw^{ij}a_i \space \text{mod} \space p $$

因为 $w=\psi^2$，所以有

$$ \hat{a}=\sum^{n-1}_{i=0}\psi^{2ij+i}a_i \space \text{mod} \space p $$

基于 $\psi$ 的 INTT

$a=INTT^{\psi^{-1}}(\hat{a})$ 为：

$$ a_i=n^{-1}\sum^{n-1}_{j=0}\psi^{-j}w^{-ij}\hat{a_j} \space \text{mod} \space p $$

因为 $w=\psi^2$，所以有

$$ a_i=n^{-1}\sum^{n-1}_{j=0}\psi^{-(2ij+j)}\hat{a_j} \space \text{mod} \space p $$

计算 Negative-Wrapped Convolution

$f(x) \cdot g(x) \space \text{mod} \space (x^n+1)= INTT^{\psi^{-1}}(NTT^{\psi}(a) \cdot NTT^{\psi}(b)) $

Fast-NTT

根据 $\psi^{k+2n} = \psi^k$ （周期性）和 $\psi^{k+n} = -\psi^{k}$ （对称性）可以快速计算 NTT

$\psi$ 的所有幂集合称为 twiddle factors