不同商环上的多项式乘法
- 摄影
- 2025-09-20
- 103热度
- 0评论
四种代数结构上的NTT完整教程
目录
- 二次幂分圆环 \mathbb{Z}_q[x]/(x^n-1)
- 负二次幂分圆环 \mathbb{Z}_q[x]/(x^n+1)
- 三项分圆环 \mathbb{Z}_q[x]/(x^n-x^{n/2}+1)
- 素阶数域
1. 二次幂分圆环 \mathbb{Z}_q[x]/(x^n-1)
1.1 基本概念
定义: 在 \mathbb{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 且 \omega_n^i \neq 1 对 0
1.2 NTT原理
核心思想: 利用点值表示实现快速多项式乘法
对于多项式 f(x) = f_0 + f_1x + \cdots + f_{n-1}x^{n-1}，其NTT定义为:
\text{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) \pmod{x^n-1}:
- 正向NTT:
- $F = \text{NTT}(f)$
- $G = \text{NTT}(g)$
- 点值乘法:
- $H_i = F_i \cdot G_i$ for $i = 0, 1, \ldots, n-1$
- 逆向NTT:
- $h = \text{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 < j) swap(a[i], a[j]);
for (int k = n >> 1; (j ^= k) < k; 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 (在 \mathbb{Z}_{7681} 中)
2. 负二次幂分圆环 \mathbb{Z}_q[x]/(x^n+1)
2.1 基本概念
定义: 在 \mathbb{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 在 \mathbb{Z}_q 上分解为 n 个不可约因子。
2.3 Negacyclic NTT原理
变换定义:
\text{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. 三项分圆环 \mathbb{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 \geq 1, \ell \geq 0 时
\Phi_b(x) = x^{n} - x^{n/2} + 1
3.2 分解原理
关键定理: \Phi_b(x) 可以递归分解
对于 n = 2^e \cdot 3^\ell:
\mathbb{Z}_q[x]/(x^n - x^{n/2} + 1) \cong \mathbb{Z}_q[x]/(x^{n/2} - \omega_b) \times \mathbb{Z}_q[x]/(x^{n/2} - \omega_b^5)
其中 \omega_b 是 6 次本原单位根（满足 6|(q-1)）。
递归性质:
- \alpha \cdot \beta = 1 over \mathbb{Z}_q
- \alpha + \beta = 1 over \mathbb{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，考虑 \mathbb{Z}_q[x]/\Phi_p(x)，其中 \Phi_p(x) 是 p 次分圆多项式
\Phi_p(x) = 1 + x + x^2 + \cdots + x^{p-1} = \frac{x^p - 1}{x - 1}
维数: \deg(\Phi_p(x)) = p - 1
4.2 CRT分解
前提条件: q \equiv 1 \pmod{p}
分解定理:
\mathbb{Z}_q[x]/\Phi_p(x) \cong \prod_{i=1}^{p-1} \mathbb{Z}_q
通过 p 次本原单位根 \zeta_p 实现同构。
4.3 NTT算法
点值评估:
对于 f(x) = f_0 + f_1x + \cdots + f_{p-2}x^{p-2} \in \mathbb{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
核心思想:
- 选择 \mathbb{Z}_p^* 的生成元 g
- 重新排列点值评估顺序
- 使用 p-1 长度的标准NTT（如果 p-1 有好的因子分解）
4.4.1 Rader变换
重排索引:
对于 i = g^k \pmod{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 = \frac{(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 = 45 \cdot 17 + 4$ (需要满足 $q \equiv 1 \pmod{17}$)
- $\zeta_{17} = $ 查找17次本原单位根
- $g = 3$ (3是 $\mathbb{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^e3^\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 <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <assert.h>
// 测试所有四种结构
int main() {
printf("=== Testing Four NTT Structures ===\n\n");
// 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: 需计算
