二、数学基础：有限域、多项式环、格（Lattice）基础、错误学习问题（LWE/RLWE）、NTT（数论变换）原理

后量子密码（PQC）的硬件加速设计，本质上是在有限代数结构中执行大规模并行计算。无论是基于格的Kyber、Dilithium，还是基于哈希的SPHINCS+，其底层运算都离不开有限域、多项式环、格理论以及数论变换（NTT）等数学工具。对于FPGA/ASIC架构师而言，理解这些数学结构的代数性质，直接决定了硬件流水线的划分、并行度的选择以及存储带宽的优化方向。本章将系统梳理这些核心数学概念，并重点剖析它们在硬件实现中的映射关系与工程约束。

上图展示了从抽象代数结构到具体硬件实现的映射路径。有限域和多项式环定义了运算的代数规则，格理论提供了安全性基础，LWE/RLWE问题构成了密码原语，而NTT则是连接数学理论与高效硬件实现的桥梁。下面我们将逐一深入剖析每个模块的数学本质及其对硬件设计的直接影响。

2.1 有限域：模运算的硬件基础

核心原理

有限域（Galois域）GF(q)是包含q个元素的集合，其中q为素数p或素数幂p^m。在PQC中，最常用的是素数域GF(p)和二进制扩展域GF(2^m)。域上的加法和乘法都满足封闭性、结合律、交换律和分配律，且每个非零元素都有乘法逆元。对于硬件实现，模运算的效率至关重要——模加只需一次比较和条件减法，而模乘则需要更复杂的算法（如Montgomery乘法或Barrett约简）。

判断方法或操作流程

在FPGA中实现模运算时，需要根据模数q的特性选择最优算法：

• 模加/模减：使用进位链加法器，随后进行条件减法（若结果≥q则减q），延迟约2-3个LUT层级。
• 模乘：对于通用q，推荐Montgomery乘法（将模数转换为2的幂次形式）；对于特殊q（如Kyber的3329），可使用Barrett约简减少乘法次数。
• 模逆：使用扩展欧几里得算法或费马小定理（q为素数时），硬件实现通常采用二进制扩展欧几里得算法，面积开销较大，建议复用乘法器资源。

案例拆解：Kyber模乘的硬件优化

以Kyber的模乘为例，q=3329，n=256。在Xilinx UltraScale+ FPGA上，一个标准的27×18位DSP48E2可实现一次18位乘法。若直接使用通用Montgomery乘法，每次模乘需要3个DSP级联；而利用q的特殊结构，可将乘法拆分为：

// Barrett约简伪代码（q=3329）
// 输入: t = a * b (0 ≤ a,b < q)
// 输出: r = t mod q
m = (t * 20159) >> 26;  // 预计算常数 μ = floor(2^26 / q)
r = t - m * 3329;
if (r >= 3329) r -= 3329;
if (r >= 3329) r -= 3329;

该实现仅需1个DSP乘法器和少量逻辑资源，相比通用Montgomery乘法减少2个DSP。在并行度32的架构中，这相当于节省了64个DSP48E2，显著降低了功耗和面积。

常见误区与总结

2.2 多项式环：R_q的结构与运算

核心原理

多项式环R_q = Z_q[x]/(x^n+1)是RLWE问题的核心代数结构。其中n通常为2的幂次（如256、512、1024），模多项式x^n+1是分圆多项式Φ_{2n}(x)。环上的元素是次数小于n的多项式，加法和乘法均需模x^n+1约简。这一结构的关键性质是：乘法可通过NTT转化为逐点乘法，从而将O(n²)的复杂度降为O(n log n)。

判断方法或操作流程

在硬件中处理多项式运算时，需关注以下设计决策：

1. 系数表示：标准系数表示（自然序）适合加法和点乘；NTT域表示（频率序）适合乘法。需要在两种表示间切换，产生额外的转换开销。
2. 存储布局：n个系数通常存储在BRAM或寄存器堆中。对于并行NTT，需要将数据按蝶形运算的访问模式重新排列，避免存储体冲突。
3. 模约简：x^n+1的约简非常高效——只需将高半部分系数取反后加到低半部分。这一操作在硬件中仅需n/2个加法器。

案例拆解：多项式乘法在Dilithium中的应用

Dilithium使用n=256，q=8380417。其多项式乘法在NTT域中执行，但需要注意q-1 = 8380416 = 2^13 × 1023，因此存在2^13阶本原单位根。硬件实现时，需要预计算旋转因子表（twiddle factors），存储在ROM中。在并行度16的架构中，每个蝶形运算需要2次模乘和2次模加，共需32个模乘器。通过时分复用，可在16个时钟周期内完成一次256点NTT。

常见误区与总结

2.3 格（Lattice）基础：几何与计算难题

核心原理

格是n维欧几里得空间中的离散加法子群，可视为由n个线性无关基向量生成的所有整数线性组合。在密码学中，我们关注的是q元格（q-ary lattice），定义为Λ = {x ∈ Z^n : x ≡ A^T s (mod q)}。格上的两个核心难题是：最短向量问题（SVP）和最近向量问题（CVP）。这些问题的困难性构成了基于格的密码方案的安全性基础。

判断方法或操作流程

对于硬件设计者，理解格理论的关键在于：

• 安全性参数：格的维度n和模数q直接决定了密钥长度和运算复杂度。NIST标准中，Level 1安全强度要求n≥256，q≥3329。
• 错误向量：LWE问题中的错误e通常从离散高斯分布或中心二项分布中采样。硬件实现需要高质量的随机数生成器（TRNG）和高效的采样算法。
• 范数约束：许多方案要求向量满足特定的范数范围（如Dilithium的c ∈ {0,±1}^n），这影响硬件中的比较器和饱和逻辑设计。

案例拆解：格基约简对硬件的影响

虽然格基约简算法（如BKZ）主要用于密码分析，但理解其计算复杂度有助于评估硬件安全边界。例如，BKZ-2.0在维度n=512时，需要约2^100次操作，这决定了FPGA上并行攻击单元的规模。在防御侧，硬件设计需确保密钥生成时采样的随机性足够，避免弱密钥——这要求TRNG的熵源质量满足AIS-31标准。

常见误区与总结

2.4 错误学习问题（LWE/RLWE）：安全性的基石

核心原理

LWE问题定义为：给定矩阵A ∈ Z_q^{m×n}和向量b = A·s + e（其中s为秘密向量，e为小错误向量），恢复s是困难的。RLWE是LWE在多项式环上的变体，将矩阵乘法替换为多项式乘法，显著提高了效率。RLWE的困难性基于理想格上的近似SVP问题，且可通过量子归约证明其安全性。

判断方法或操作流程

在硬件实现中，LWE/RLWE运算的核心是：

1. 多项式乘法：使用NTT加速，这是性能瓶颈所在。
2. 错误采样：从中心二项分布（CBD）采样，硬件实现通常使用拒绝采样或逆变换采样。
3. 加法与模约简：将结果约简到[0, q)范围。

案例拆解：RLWE加密的硬件流水线

以Kyber加密为例，其核心操作为：c = NTT^{-1}(NTT(a) ∘ NTT(s)) + e。在FPGA上，该流水线分为5级：

级1: 加载a和s的NTT域系数（从BRAM读取）
级2: 逐点乘法（256个并行模乘器）
级3: 逆NTT（8级蝶形运算）
级4: 添加错误向量e（CBD采样）
级5: 模约简与输出

该设计在100MHz时钟下，单次加密延迟约2.5μs，吞吐量可达400K ops/s。若将并行度提升至64，延迟可降至0.6μs，但面积增加约3倍。

常见误区与总结

2.5 NTT（数论变换）原理与硬件实现

核心原理

NTT是离散傅里叶变换（DFT）在有限域上的推广。对于长度n=2^k的序列，NTT定义为：X_k = Σ_{i=0}^{n-1} x_i · ω^{ik} mod q，其中ω是模q的n次本原单位根。NTT的核心优势在于：循环卷积可通过逐点乘法实现，复杂度从O(n²)降至O(n log n)。在PQC中，NTT通常与负卷绕结合，实现多项式环上的乘法。

判断方法或操作流程

硬件NTT设计的关键决策点：

• 基选择：基-2（Radix-2）结构简单，但需要n/2×log2 n次蝶形运算；基-4可减少乘法次数，但控制逻辑更复杂。
• 流水线架构：迭代型（in-place）节省存储，但需要复杂的地址生成；流水线型（pipelined）吞吐量高，但寄存器开销大。
• 旋转因子存储：可预计算并存储在ROM中，或实时计算（CORDIC算法）。ROM方式更常用，但需注意存储带宽。

案例拆解：256点NTT的FPGA实现

以Kyber的256点NTT为例，q=3329，ω=17。采用基-2迭代架构，共8级蝶形运算。每级包含128个蝶形单元，每个蝶形单元需要1次模乘和2次模加。在Xilinx ZCU106开发板上，使用16个并行蝶形单元，时钟频率200MHz：

单次NTT延迟为8级×2周期=16周期，即80ns。若需更高吞吐量，可采用4个并行NTT核，将吞吐量提升至12.5M NTT/s。

常见误区与总结