系统梳理几类商环上的多项式乘法，包括二次幂分圆环、负二次幂分圆环、三项分圆环和素阶数域，为理解 NTT 与格密码实现打基础。

四种代数结构上的 NTT 完整教程

1. 二次幂分圆环 $Z_q[x]/(x^n - 1)$

1.1 基本概念

定义: 在 $Z_q[x]/(x^n - 1)$ 中，多项式运算满足约简条件 $x^n \equiv 1 \pmod{q}$ 。

前提条件:

n = 2^k，n 为 2 的幂次。
q 是素数，满足 $q \equiv 1 \pmod{2n}$ 。
存在 n 次本原单位根 $\omega_n$ ，满足 $\omega_n^n = 1$ ，且对 $0 < i < n$ 有 $\omega_n^i \ne 1$ 。

1.2 NTT原理

核心思想: 利用点值表示实现快速多项式乘法

对于多项式 $f(x) = f_0 + f_1x + \ldots + f_{n-1}x^{n-1}$ ，其 NTT 定义为:

NTT(f) = (f(\omega_n^0), f(\omega_n^1), \ldots, f(\omega_n^{n-1}))

1.3 正向NTT算法

Cooley-Tukey蝴蝶变换:

输入: 系数表示 f = [f_0, f_1, ..., f_{n-1}]
输出: 点值表示 F = [F_0, F_1, ..., F_{n-1}]

for len = 1, 2, 4, ..., n/2 do:
    omega = ω_n^(n/(2*len))  // 当前层的单位根
    for start = 0 to n-1 step 2*len do:
        w = 1
        for j = 0 to len-1 do:
            t = w * f[start + j + len]
            u = f[start + j]
            f[start + j] = u + t
            f[start + j + len] = u - t
            w = w * omega

复杂度: $O(n \log n)$

1.4 逆向NTT算法

Gentleman-Sande蝴蝶变换:

输入: 点值表示 F = [F_0, F_1, ..., F_{n-1}]
输出: 系数表示 f = [f_0, f_1, ..., f_{n-1}]

for len = n/2, n/4, ..., 1 do:
    omega = ω_n^(-n/(2*len))  // 使用逆单位根
    for start = 0 to n-1 step 2*len do:
        w = 1
        for j = 0 to len-1 do:
            u = F[start + j]
            t = F[start + j + len]
            F[start + j] = u + t
            F[start + j + len] = w * (u - t)
            w = w * omega

// 最后除以n
for i = 0 to n-1 do:
    f[i] = F[i] / n  (mod q)

1.5 多项式乘法过程

计算 $h(x) = f(x) \cdot g(x) \bmod (x^n - 1)$ :

正向NTT:
- $F = NTT(f)$
- $G = NTT(g)$
点值乘法:
- $H_i = F_i \cdot G_i$ ，其中 $i = 0, 1, \ldots, n - 1$
逆向NTT:
- $h = INTT(H)$

1.6 代码实现

void ntt_forward(int64_t a[], int n, int64_t q, int64_t omega) {
    // 位反转置换
    for (int i = 0, j = 0; i < n; i++) {
        if (i > 1; (j ^= k) >= 1);
    }

    // Cooley-Tukey蝴蝶变换
    for (int len = 2; len <= n; len <<= 1) {
        int64_t w_len = power_mod(omega, n / len, q);
        for (int i = 0; i < n; i += len) {
            int64_t w = 1;
            for (int j = 0; j < len / 2; j++) {
                int64_t t = (w * a[i + j + len/2]) % q;
                int64_t u = a[i + j];
                a[i + j] = (u + t) % q;
                a[i + j + len/2] = (u - t + q) % q;
                w = (w * w_len) % q;
            }
        }
    }
}

void ntt_inverse(int64_t a[], int n, int64_t q, int64_t omega) {
    int64_t omega_inv = mod_inverse(omega, q);
    ntt_forward(a, n, q, omega_inv);

    int64_t n_inv = mod_inverse(n, q);
    for (int i = 0; i < n; i++) {
        a[i] = (a[i] * n_inv) % q;
    }
}

1.7 应用示例

参数选择: n = 256, q = 7681，满足 $q = 30 \cdot 256 + 1$ 。

本原单位根: $\omega_{256} = 62$ ，在 $Z_{7681}$ 中。

2. 负二次幂分圆环 $Z_q[x]/(x^n + 1)$

2.1 基本概念

定义: 在 $Z_q[x]/(x^n + 1)$ 中，多项式运算满足约简条件 $x^n \equiv -1 \pmod{q}$ 。

前提条件:

n = 2^k，n 为 2 的幂次。
q 是素数，满足 $q \equiv 1 \pmod{2n}$ 。
存在 2n 次本原单位根 $\psi$ ，满足 $\psi^{2n} = 1$ 且 $\psi^n = -1$ 。

2.2 特殊性质

关键特性:

x^n + 1 = \prod_{i=0}^{n-1}(x - \psi^{2i+1})

因此， $x^n + 1$ 在 $Z_q$ 上分解为 n 个一次因子。

2.3 Negacyclic NTT原理

变换定义:

NegaNTT(f)_i = f(\psi^{2i+1}) = \sum_{j=0}^{n-1} f_j \cdot \psi^{(2i+1)j}

其中 $\psi = \omega_{2n}$ 是 2n 次本原单位根。

2.4 正向Negacyclic NTT

算法流程:

输入: f = [f_0, f_1, ..., f_{n-1}]
输出: F = [f(ψ), f(ψ³), ..., f(ψ^(2n-1))]

Step 1: 预处理（添加扭转因子）
for i = 0 to n-1 do:
    f[i] = f[i] * ψ^i

Step 2: 标准NTT（使用ω_n = ψ²）
NTT_forward(f, ω_n)

Step 3: 后处理
for i = 0 to n-1 do:
    F[i] = f[i]

关键点: 扭转因子 $\psi^i$ 将 negacyclic 卷积转化为标准 cyclic 卷积。

2.5 逆向Negacyclic NTT

输入: F = [F_0, F_1, ..., F_{n-1}]
输出: f = [f_0, f_1, ..., f_{n-1}]

Step 1: 标准逆NTT
INTT(F, ω_n)

Step 2: 移除扭转因子
for i = 0 to n-1 do:
    f[i] = F[i] * ψ^(-i)

Step 3: 除以n
for i = 0 to n-1 do:
    f[i] = f[i] / n  (mod q)

2.6 完整代码实现

// 预计算扭转因子
void precompute_psi_powers(int64_t psi_powers[], int n, int64_t psi, int64_t q) {
    psi_powers[0] = 1;
    for (int i = 1; i < n; i++) {
        psi_powers[i] = (psi_powers[i-1] * psi) % q;
    }
}

// Negacyclic正向NTT
void negacyclic_ntt_forward(int64_t a[], int n, int64_t q, 
                             int64_t psi_powers[], int64_t omega) {
    // Step 1: 添加扭转因子
    for (int i = 0; i < n; i++) {
        a[i] = (a[i] * psi_powers[i]) % q;
    }

    // Step 2: 标准NTT (omega = psi^2)
    ntt_forward(a, n, q, omega);
}

// Negacyclic逆向NTT
void negacyclic_ntt_inverse(int64_t a[], int n, int64_t q, 
                             int64_t psi_inv_powers[], int64_t omega) {
    // Step 1: 标准逆NTT
    ntt_inverse(a, n, q, omega);

    // Step 2: 移除扭转因子
    for (int i = 0; i < n; i++) {
        a[i] = (a[i] * psi_inv_powers[i]) % q;
    }
}

// 多项式乘法 in Z_q[x]/(x^n+1)
void poly_mul_negacyclic(int64_t c[], int64_t a[], int64_t b[], 
                         int n, int64_t q, int64_t psi, int64_t omega) {
    int64_t psi_powers[n], psi_inv_powers[n];
    int64_t a_ntt[n], b_ntt[n];

    // 预计算
    precompute_psi_powers(psi_powers, n, psi, q);
    int64_t psi_inv = mod_inverse(psi, q);
    precompute_psi_powers(psi_inv_powers, n, psi_inv, q);

    // 复制并转换
    memcpy(a_ntt, a, n * sizeof(int64_t));
    memcpy(b_ntt, b, n * sizeof(int64_t));

    negacyclic_ntt_forward(a_ntt, n, q, psi_powers, omega);
    negacyclic_ntt_forward(b_ntt, n, q, psi_powers, omega);

    // 点值乘法
    for (int i = 0; i < n; i++) {
        c[i] = (a_ntt[i] * b_ntt[i]) % q;
    }

    // 逆变换
    negacyclic_ntt_inverse(c, n, q, psi_inv_powers, omega);
}

2.7 参数示例

Kyber 参数:

n = 256
q = 3329
$\psi = 17$ ，满足 $\psi^{512} = 1$ 、 $\psi^{256} = -1$
$\omega = \psi^2 = 289$

验证:

q = 3329
psi = 17
print(pow(psi, 512, q))  # 应该输出 1
print(pow(psi, 256, q))  # 应该输出 3328 (即 -1 mod 3329)

3. 三项分圆环 $Z_q[x]/(x^n - x^{n/2} + 1)$

3.1 基本概念

定义: 三项分圆环的约简多项式为 $\Phi_b(x) = x^n - x^{n/2} + 1$ 。

特殊形式: 当 $n = 2^e \cdot 3^\ell$ ， $e \ge 1, \ell \ge 0$ 时:

\Phi_b(x) = x^n - x^{n/2} + 1

3.2 分解原理

关键定理: $\Phi_b(x)$ 可以递归分解。

对于 $n = 2^e \cdot 3^\ell$ :

Z_q[x]/(x^n - x^{n/2} + 1) \cong Z_q[x]/(x^{n/2} - \omega_b) \times Z_q[x]/(x^{n/2} - \omega_b^5)

其中 $\omega_b$ 是 6 次本原单位根，满足 $6 \mid (q - 1)$ 。

递归性质:

$\alpha \cdot \beta = 1$ over $Z_q$
$\alpha + \beta = 1$ over $Z_q$
因此 $\alpha = \omega_6$ ， $\beta = \omega_6^5 = \omega_6^{-1}$

3.3 混合基NTT（Radix-2/3）

基本思想: 根据 n 的因子分解，交替使用Radix-2和Radix-3分解

3.3.1 Radix-2步骤

对于 mathbb{Z}_q[x]/(x^n - x^{n/2} + 1)，其中 n = 2m:

分解: x^n - x^{n/2} + 1 = (x^m - ω_6) · (x^m - ω_6^5)

对于多项式 f(x) = Σ f_i x^i:

f_left = f mod (x^m - ω_6)
f_right = f mod (x^m - ω_6^5)

计算方式:
for i = 0 to m-1:
    f_left[i] = f[i] + ω_6 * f[i+m]
    f_right[i] = f[i] + ω_6^5 * f[i+m]

3.3.2 Radix-3步骤

对于 mathbb{Z}_q[x]/(x^n - x^{n/3} + 1)，其中 n = 3m:

分解: x^n - x^{n/3} + 1 可以分解为三个因子

使用 3次单位根 ω_3 (满足 ω_3^3 = 1):

f_0 = f mod (x^m - ω_18)
f_1 = f mod (x^m - ρ·ω_18)  
f_2 = f mod (x^m - ρ²·ω_18)

其中 ρ = ω_3, ω_18 是18次本原单位根

3.4 完整NTT算法

算法结构:

function TriNTT(f, n, structure):
    if n == 1:
        return f

    if 2 | n:  // Radix-2分解
        m = n / 2
        omega = ω_6^k  // 根据层级选择合适的单位根

        f_left = [f[i] + omega * f[i+m] for i in 0..m-1]
        f_right = [f[i] + omega^5 * f[i+m] for i in 0..m-1]

        left_result = TriNTT(f_left, m, structure/2)
        right_result = TriNTT(f_right, m, structure/2)

        return concatenate(left_result, right_result)

    else if 3 | n:  // Radix-3分解
        m = n / 3
        omega = ω_18^k
        rho = ω_3

        f_0 = compute_branch_0(f, m, omega)
        f_1 = compute_branch_1(f, m, omega, rho)
        f_2 = compute_branch_2(f, m, omega, rho)

        result_0 = TriNTT(f_0, m, structure/3)
        result_1 = TriNTT(f_1, m, structure/3)
        result_2 = TriNTT(f_2, m, structure/3)

        return concatenate(result_0, result_1, result_2)

3.5 代码实现

// 三项分圆环NTT的完整实现
typedef struct {
    int radix;  // 2 or 3
    int64_t omega;
} NTT_Layer;

// 预计算NTT层结构
void compute_ntt_structure(NTT_Layer layers[], int* num_layers, 
                           int n, int64_t q) {
    *num_layers = 0;
    int current_n = n;
    int level = 0;

    while (current_n > 1) {
        if (current_n % 2 == 0) {
            layers[level].radix = 2;
            // 计算该层的ω_6系列单位根
            layers[level].omega = compute_omega_6_power(level, q);
            current_n /= 2;
        } else if (current_n % 3 == 0) {
            layers[level].radix = 3;
            // 计算该层的ω_18系列单位根
            layers[level].omega = compute_omega_18_power(level, q);
            current_n /= 3;
        }
        level++;
    }
    *num_layers = level;
}

// Radix-2蝴蝶操作
void radix2_butterfly(int64_t f[], int m, int64_t omega, int64_t q) {
    int64_t temp[m];
    int64_t omega5 = power_mod(omega, 5, q);

    for (int i = 0; i < m; i++) {
        int64_t t = (omega * f[i + m]) % q;
        temp[i] = (f[i] + t) % q;

        int64_t t2 = (omega5 * f[i + m]) % q;
        f[i + m] = (f[i] + t2) % q;

        f[i] = temp[i];
    }
}

// Radix-3蝴蝶操作
void radix3_butterfly(int64_t f[], int m, int64_t omega, 
                      int64_t rho, int64_t q) {
    int64_t temp0[m], temp1[m], temp2[m];
    int64_t rho2 = (rho * rho) % q;

    for (int i = 0; i < m; i++) {
        int64_t f0 = f[i];
        int64_t f1 = f[i + m];
        int64_t f2 = f[i + 2*m];

        // Branch 0: x^m - ω_18
        temp0[i] = (f0 + (omega * f1) % q + (omega * f2) % q) % q;

        // Branch 1: x^m - ρ·ω_18
        int64_t omega_rho = (omega * rho) % q;
        int64_t omega_rho2 = (omega * rho2) % q;
        temp1[i] = (f0 + (omega_rho * f1) % q + (omega_rho2 * f2) % q) % q;

        // Branch 2: x^m - ρ²·ω_18
        int64_t omega_rho2_2 = (omega * rho2) % q;
        int64_t omega_rho4 = (omega * (rho2 * rho2) % q) % q;
        temp2[i] = (f0 + (omega_rho2_2 * f1) % q + (omega_rho4 * f2) % q) % q;
    }

    memcpy(f, temp0, m * sizeof(int64_t));
    memcpy(f + m, temp1, m * sizeof(int64_t));
    memcpy(f + 2*m, temp2, m * sizeof(int64_t));
}

// 主NTT函数
void trinomial_ntt_forward(int64_t f[], int n, int64_t q, 
                           NTT_Layer layers[], int num_layers) {
    int current_size = n;
    int offset = 0;

    for (int layer = 0; layer < num_layers; layer++) {
        int radix = layers[layer].radix;
        int64_t omega = layers[layer].omega;
        int new_size = current_size / radix;

        if (radix == 2) {
            // 对每个分块应用Radix-2
            for (int block = 0; block < (1 << layer); block++) {
                int start = block * current_size;
                radix2_butterfly(f + start, new_size, omega, q);
            }
        } else {  // radix == 3
            // 计算ρ (三次单位根)
            int64_t rho = compute_omega_3(q);

            for (int block = 0; block < offset; block++) {
                int start = block * current_size;
                radix3_butterfly(f + start, new_size, omega, rho, q);
            }
        }

        current_size = new_size;
        offset *= radix;
    }
}

3.6 参数示例

示例1: $n = 768 = 2^8 \cdot 3$

q = 3457，满足 $q \equiv 1 \pmod{6}$ 且 $q \equiv 1 \pmod{768}$
分解层次: 8 次 Radix-2 + 1 次 Radix-3
$\omega_6$ : 计算满足 $\omega_6^6 = 1$ 的元素
$\omega_3$ : 计算满足 $\omega_3^3 = 1$ 的元素

示例2: $n = 384 = 2^7 \cdot 3$

分解层次: 7次Radix-2 + 1次Radix-3

3.7 复杂度分析

时间复杂度:

Radix-2 层: 每层 $O(n)$ ，共 $\log_2(n / 3^\ell)$ 层
Radix-3 层: 每层 $O(n)$ ，共 $\ell$ 层
总复杂度: $O(n \cdot (\log_2 n + \ell \log 3))$

空间复杂度: O(n)

4. 素阶数域

4.1 基本概念

定义: 对于素数 p，考虑 $Z_q[x]/\Phi_p(x)$ ，其中 $\Phi_p(x)$ 是 p 次分圆多项式。

\Phi_p(x) = 1 + x + x^2 + \ldots + x^{p-1} = (x^p - 1)/(x - 1)

维数: $\deg(\Phi_p(x)) = p - 1$

4.2 CRT分解

前提条件: $q \equiv 1 \pmod{p}$

分解定理:

Z_q[x]/\Phi_p(x) \cong \prod_{i=1}^{p-1} Z_q

通过 p 次本原单位根 $\zeta_p$ 实现同构。

4.3 NTT算法

点值评估:

对于 $f(x) = f_0 + f_1x + \ldots + f_{p-2}x^{p-2}$ in $Z_q[x]/\Phi_p(x)$ :

F_i = f(\zeta_p^i), \text{ for } i = 1, 2, \ldots, p - 1

朴素算法:

def naive_ntt_prime_field(f, p, q, zeta):
    """
    f: 系数列表，长度为p-1
    p: 素数阶
    q: 模数，满足q ≡ 1 (mod p)
    zeta: p次本原单位根
    """
    F = []
    for i in range(1, p):
        zeta_i = pow(zeta, i, q)
        value = 0
        for j in range(p-1):
            value = (value + f[j] * pow(zeta_i, j, q)) % q
        F.append(value)
    return F

复杂度: $O(p^2)$

4.4 优化的NTT

Rader算法: 将素数长度FFT转化为合成数长度FFT

核心思想:

选择 $Z_p^*$ 的生成元 g。
重新排列点值评估顺序。
使用 p - 1 长度的标准 NTT，如果 p - 1 有好的因子分解。

4.4.1 Rader变换

重排索引:

对于 $i = g^k \bmod p$ ，定义:

F_{g^k} = \sum_{j=0}^{p-2} f_j \zeta_p^{g^k \cdot j}

通过变量替换 $j = g^m$ :

F_{g^k} = \sum_{m=0}^{p-2} f_{g^m} \zeta_p^{g^{k+m}}

这是一个循环卷积！

4.4.2 算法实现

def rader_ntt(f, p, q, zeta, g):
    """
    使用Rader算法的优化NTT
    f: 系数列表，长度为p-1
    p: 素数阶
    g: Z_p^*的生成元
    """
    n = p - 1

    # Step 1: 重排输入
    f_reordered = [0] * n
    power_table = [1] * n
    g_inv = mod_inverse(g, p)

    for i in range(n):
        idx = pow(g, i, p) - 1  # 减1因为索引从0开始
        f_reordered[i] = f[idx]
        power_table[i] = pow(zeta, pow(g, i, p), q)

    # Step 2: 使用合成数NTT计算循环卷积
    # 选择 m >= 2n-1 且m有好的因子分解
    m = next_power_of_2(2 * n - 1)

    # 零填充
    f_padded = f_reordered + [0] * (m - n)
    h_padded = power_table + [0] * (m - n)

    # 标准NTT（如果m是2的幂）
    F = standard_ntt(f_padded, m, q)
    H = standard_ntt(h_padded, m, q)

    # 点值乘法
    C = [(F[i] * H[i]) % q for i in range(m)]

    # 逆NTT
    c = standard_intt(C, m, q)

    # Step 3: 重排输出
    result = [0] * n
    for i in range(n):
        idx = pow(g, i, p) - 1
        result[idx] = c[i]

    return result

4.5 Bluestein算法

另一种方法: 使用chirp-z变换

核心公式:

ij = ((i + j)^2 - i^2 - j^2) / 2

因此：

\zeta_p^{ij} = \zeta_p^{(i+j)^2/2} \cdot \zeta_p^{-i^2/2} \cdot \zeta_p^{-j^2/2}

算法:

def bluestein_ntt(f, p, q, zeta):
    """
    使用Bluestein算法
    """
    n = p - 1
    m = next_power_of_2(2 * n - 1)

    # 预计算 zeta^{-i^2/2}
    zeta_inv = mod_inverse(zeta, q)
    zeta_sqrt_inv = mod_sqrt(zeta_inv, q)  # 可能需要特殊处理

    chirp = [1] * n
    for i in range(n):
        exp = (i * i) % (2 * p)
        chirp[i] = pow(zeta_sqrt_inv, exp, q)

    # 调制
    f_mod = [(f[i] * chirp[i]) % q for i in range(n)]

    # 构造卷积核
    h = [0] * m
    for i in range(n):
        exp = (i * i) % (2 * p)
        h[i] = pow(zeta_sqrt_inv, p - exp, q)
    for i in range(n-1, 0, -1):
        h[m - i] = h[i]

    # 使用标准NTT计算卷积
    F = standard_ntt(f_mod + [0]*(m-n), m, q)
    H = standard_ntt(h, m, q)
    C = [(F[i] * H[i]) % q for i in range(m)]
    c = standard_intt(C, m, q)

    # 解调
    result = [(c[i] * chirp[i]) % q for i in range(n)]

    return result

4.6 参数示例

示例1: p = 17

q = 769，满足 $q \equiv 1 \pmod{17}$
$\zeta_{17}$ : 查找 17 次本原单位根
g = 3，3 是 $Z_{17}^*$ 的生成元
$p - 1 = 16 = 2^4$ ，可以高效使用 Radix-2 NTT

示例2: p = 127

q 需要满足 $q \equiv 1 \pmod{127}$
$p - 1 = 126 = 2 \cdot 3^2 \cdot 7$
可以使用混合基算法

4.7 实际应用

密码学应用:

NTRU Prime 使用素数阶数域。
提供更强的安全性保证。
避免某些代数攻击。

性能对比:

阶数类型	NTT 复杂度	优点	缺点
$2^k$	$O(n \log n)$	最快	结构可能被利用
$2^k \cdot 3^\ell$	$O(n \log n)$	快速且灵活	实现复杂
素数 p	$O(p^2)$ 或 $O(p \log p)$	安全性高	较慢

5. 综合比较与选择指南

5.1 性能对比

结构	维数	NTT 复杂度	模数要求	实现难度
$x^n - 1$	$n = 2^k$	$O(n \log n)$	$q \equiv 1 \pmod{2n}$	低
$x^n + 1$	$n = 2^k$	$O(n \log n)$	$q \equiv 1 \pmod{2n}$	中
$x^n - x^{n/2} + 1$	$n = 2^e \cdot 3^\ell$	$O(n \log n)$	$q \equiv 1 \pmod{6n}$	较高
$\Phi_p(x)$	$p - 1$	$O(p^2)$ 或优化后	$q \equiv 1 \pmod{p}$	高

5.2 应用场景

二次幂分圆环 $x^n \pm 1$ :

适用于需要极致性能的场景。
Kyber、Dilithium 等标准化方案。

三项分圆环:

平衡性能和灵活性。
避免完全 2 的幂次结构。
某些高级密码协议。

素阶数域:

需要最高安全性保证。
NTRU Prime。
研究用途。

5.3 实现建议

首选 x^n+1: 对于大多数应用，negacyclic NTT提供最佳平衡
考虑三项分圆环: 当需要避免2的幂次结构时
慎用素阶: 除非有特殊安全需求，否则性能损失较大

5.4 优化技巧

通用优化:
- 预计算单位根幂次
- 使用Barrett或Montgomery约减
- 向量化（SIMD）
- 多线程并行

模数选择:
- 优先选择Solinas素数（伪梅森素数）
- 确保存在所需阶的本原单位根
- 考虑硬件友好的位宽

6. 完整示例代码

6.1 测试框架

#include 
#include 
#include 
#include 
#include 

// 测试所有四种结构
int main() {
    printf("=== Testing Four NTT Structures ===nn");

    // Test 1: x^n - 1
    printf("1. Testing NTT over Z_q[x]/(x^n - 1)n");
    test_cyclic_ntt();

    // Test 2: x^n + 1
    printf("n2. Testing NTT over Z_q[x]/(x^n + 1)n");
    test_negacyclic_ntt();

    // Test 3: x^n - x^{n/2} + 1
    printf("n3. Testing NTT over Z_q[x]/(x^n - x^{n/2} + 1)n");
    test_trinomial_ntt();

    // Test 4: Φ_p(x)
    printf("n4. Testing NTT over Z_q[x]/Φ_p(x)n");
    test_prime_field_ntt();

    printf("n=== All tests passed! ===n");
    return 0;
}

7. 参考文献与扩展阅读

Cooley-Tukey FFT: J. W. Cooley and J. W. Tukey, “An algorithm for the machine calculation of complex Fourier series,” 1965
NTT in Cryptography: P. Barrett, “Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor,” 1986
Kyber: R. Avanzi et al., “CRYSTALS-Kyber Algorithm Specifications,” 2021
NTRU Prime: D. J. Bernstein et al., “NTRU Prime,” 2017
Mixed-Radix NTT: P. Longa and M. Naehrig, “Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography,” 2016

附录A: 常用参数表

A.1 Kyber参数 (x^{256} + 1)

n = 256
q = 3329
ψ = 17 (满足 ψ^512 = 1, ψ^256 = -1 mod 3329)
ω = ψ^2 = 289

A.2 三项分圆环参数

n = 768 = 2^8 · 3
q = 3457
ω_6: 需计算
ω_3: 需计算

A.3 素数参数

p = 761
q = 4591 (满足 q ≡ 1 mod 761)
ζ_761: 需计算

不同商环上的多项式乘法