2. PQC数学基础

后量子密码（PQC）之所以能在量子计算威胁下站稳脚跟，核心在于它把安全性建立在一些被认为连量子计算机也难以高效求解的数学难题上。格理论就是其中最典型的一类。理解格、基、行列式、SVP、CVP，以及模运算、多项式环和NTT变换，是读懂Kyber、Dilithium等主流PQC算法实现细节的前提。

一、格：离散点阵与它的“基”

直观地说，一个格（Lattice）是n维实数空间中由一组线性无关向量所有整数系数线性组合构成的离散点集。设基向量为 b₁, b₂, …, bₙ，则格 L = { Σ aᵢbᵢ | aᵢ ∈ ℤ }。这里的“整数系数”是关键：它让格成为离散的、周期性的点阵，而不是连续的向量空间。

同一格可以有无数个不同的基。例如二维格中，基 (1,0)、(0,1) 与基 (1,0)、(1,1) 生成的是同一个格，但后者的向量更长、更“歪”。基的质量直接影响格上问题的求解难度：约化基（向量短且接近正交）让SVP、CVP更容易求解，而密码学恰恰要构造“坏基”让攻击者难以约化。这就是格密码安全性的来源之一。

行列式（determinant）det(L) 是基向量构成的平行多面体的体积，它等于格的基本域体积，与基的选择无关。行列式刻画了格点的平均密度：det 越小，格点越密。在密码参数设计中，行列式与模数 q、维数 n 共同决定了格问题的困难程度。

二、SVP与CVP：格上的两个核心难题

最短向量问题（SVP）：给定格 L 的一组基，找出格中长度最短的非零向量。在二维格中，用高斯约化可以快速求出；但在高维（如 n=512、1024）下，已知最优算法仍需指数级时间，这正是格密码的安全基础。

最近向量问题（CVP）：给定格 L 和一个目标向量 t（通常不在格上），找出格中距离 t 最近的向量。CVP可看作SVP的“非齐次”版本，两者在密码分析中常相互转化。CVP的困难性支撑了基于格的加密方案：明文被编码为格点附近的扰动，解密就是解CVP恢复最近格点。

三、模运算与多项式环：从整数到环上运算

PQC算法不能直接在无限整数格上运算，必须把系数限制在有限域中，这就引入了模运算。所有系数对模数 q 取模，运算结果落在 [0, q-1] 或对称区间 [-q/2, q/2] 内。Kyber中 q=3329，Dilithium中 q=8380417，都是精心挑选的素数，使得 q ≡ 1 (mod 2n)，从而支持NTT分解。

进一步，PQC把多个系数组织成多项式环 R_q = ℤ_q[x]/(xⁿ+1)。这里 xⁿ+1 是分圆多项式，n 通常取 256、512、1024。环上元素就是次数小于 n、系数在 ℤ_q 中的多项式。多项式乘法若直接做，复杂度为 O(n²)；当 n=1024 时约百万次乘法，对嵌入式设备负担很重。NTT正是为解决这一问题而生。

四、NTT变换：把多项式乘法变成点乘

数论变换（NTT）是快速傅里叶变换在有限域上的类比。它利用 q 中存在 n 次本原单位根 ω（即 ωⁿ ≡ 1 mod q 且 ωᵏ ≠ 1，k<n），把多项式 a(x) 映射为它在 ω 的各次幂处的取值：Âᵢ = a(ωⁱ)。变换后，多项式乘法退化为逐点相乘：Ĉᵢ = Âᵢ · B̂ᵢ。做完点乘再逆变换，就得到乘积多项式。

NTT的工程意义体现在三点：第一，复杂度从 O(n²) 降到 O(n log n)，n=1024 时约一万次运算，提速近百倍；第二，适合硬件并行，蝶形运算结构规整，可在FPGA、ASIC上流水线实现；第三，避免浮点误差，全程整数模运算，结果精确可复现，这对密码学至关重要。

以Kyber为例，其NTT采用7层蝶形运算（n=256，2⁷=128个蝶形对），每层使用预计算的旋转因子表。实现时通常采用不完全NTT：只做正向变换，点乘后直接做逆向合并，省去一次完整逆变换，进一步降低开销。下表给出典型参数对比：

五、从数学到工程：一条完整的理解链

把本节概念串起来：格提供困难问题（SVP/CVP），模运算把问题限制在有限域，多项式环把高维向量打包成单个代数对象，NTT则让环上乘法高效可行。Kyber的公钥就是一个环上多项式对 (A, t=As+e)，其中 s、e 是小系数多项式，攻击者要从 t 恢复 s 等价于解一个带误差的格问题（LWE）。没有NTT，这个方案在嵌入式设备上几乎无法实用；有了NTT，它才能在毫秒级完成封装与解封装。