2. ML-KEM数学基础

ML-KEM（FIPS 203）的安全性建立在格上困难问题之上，而它的全部运算都发生在两个数学舞台上：模整数环 Z_q 与多项式环 R_q = Z_q[X]/(X^n+1)。本节不追求形式化证明，而是把实现者必须"算得对"的四个数学构件讲清楚：模运算与多项式环的表示、NTT 正逆变换、压缩/解压缩函数、以及 CBD 与拒绝采样。理解它们的输入输出与边界条件，是后续编写密钥生成、封装、解封装代码的前提。

一、模运算与多项式环：一切运算的容器

ML-KEM-768 的参数为 n = 256、q = 3329、k = 3。所有系数都是 Z_q 中的元素，即取值在 [0, 3328] 的整数，加减乘之后必须对 q 取模。由于 q = 3329 是素数且 q ≡ 1 (mod 256)，X^256+1 在 Z_q 上完全分裂为 256 个一次因式，这正是 NTT 能高效工作的代数根源。

多项式环的乘法是"负循环卷积"：两个次数小于 256 的多项式相乘后，对 X^256+1 取模，意味着 X^256 ≡ -1，因此 X^{256+i} 的系数要取负后叠加到 X^i 上。这一点与常见的循环卷积（X^n-1）符号相反，是初学者最容易写错的地方。直接做卷积需要约 n^2 = 65536 次乘加，而 NTT 把它降到约 n log n 量级。

实现上通常把多项式存为 int16_t coeffs[256]，并采用"延迟归约"策略：中间结果允许落在 [-q, q] 甚至更宽的范围，只在必要时做条件加减，避免每次乘法都执行昂贵的除法取模。例如 Barrett 归约用预计算的 v = floor(2^26 / q) 通过乘法和移位近似求余，Montgomery 归约则把取模与乘法合并。这些技巧不改变数学语义，只改变性能。

二、NTT 正变换与逆变换

NTT 是系数表示与"点值表示"之间的可逆映射。在 ML-KEM 中，它把 256 个系数变换为 128 个二次剩余对上的求值结果，因为 X^256+1 的因式是成对出现的：(X^2 - ζ^{2i+1})。因此 NTT 输出是 128 个 Z_q 中的二次多项式，每个含两个系数，共 256 个值。

变换使用 7 层蝶形运算（2^7 = 128），每层处理 128 个蝶形。核心运算是 (a, b) → (a + b·w, a - b·w)，其中 w 是预计算的旋转因子（twiddle factor）。ML-KEM 规范固定了 ζ = 17 作为 256 次本原单位根，所有旋转因子都由它派生，并以特定顺序排列在常量表中。逆变换使用 w^{-1}，最后整体乘以 n^{-1} mod q = 3303。

工程上要特别注意三点：其一，正变换与逆变换的蝶形顺序、旋转因子索引必须与规范逐位一致，否则结果虽"像"正确却无法互通；其二，点乘阶段是两个 NTT 域多项式的 128 组二次多项式相乘，每组需要 4 次基乘加，而非简单的逐系数相乘；其三，逆变换后的系数需要归约到标准区间 [0, q)，因为后续压缩函数依赖这个约定。

三、压缩与解压缩函数

ML-KEM 的公钥、密文体积远小于原始多项式，靠的就是压缩。定义 Compress_d(x) = round((2^d / q) · x) mod 2^d，Decompress_d(y) = round((q / 2^d) · y)。直观理解：把 [0, q) 均匀映射到 [0, 2^d) 的整数格点上，解压缩再映射回来，误差不超过 q / 2^{d+1}。

ML-KEM-768 中，公钥向量用 d = 12 压缩（几乎无损，因为 2^12 = 4096 > q），密文中的 u 用 d = 10，v 用 d = 4。压缩是有损的，解封装时噪声预算必须容纳这部分误差。实现时不要用浮点 round，而应用整数运算：((x << d) + q/2) / q 再取低 d 位，并注意 q/2 的取整方向要与规范一致，否则边界值会差 1。

四、采样算法：CBD 与拒绝采样

密钥生成需要从特定分布采样。ML-KEM 使用两种采样器，用途截然不同。

CBD（中心二项分布）用于生成私钥向量和误差向量。CBD_η 从 2η 比特中取两个 η 位整数 a, b，输出 a - b，取值落在 [-η, η]。η = 2 时每个系数只需 4 比特，一个 64 位字可产出 16 个系数，256 个系数正好用 32 字节种子经 SHAKE256 扩展后按位切片得到。实现要点是按小端序逐位读取，且 a 取低位、b 取高位，顺序颠倒会得到不同但"看似合理"的密钥。

拒绝采样用于从 Z_q 上均匀采样，生成矩阵 A 的元素。做法是把 SHAKE128 的输出按 3 字节一组解析为 12 位整数，若小于 q 则接受，否则丢弃并继续读取。由于 4096 / 3329 ≈ 1.23，接受率约 81%，平均每个系数消耗约 1.23 组三元组。拒绝采样保证了输出严格均匀，这是安全证明所要求的；用"取模"代替拒绝会引入微小偏差，不可接受。

把四者串起来看：采样产生系数域多项式，NTT 把乘法搬到点值域，压缩在传输前削减比特。每一环都有明确的数学契约与边界约定，实现者的任务不是重新发明数学，而是让每一个取模、每一次移位、每一个索引都与规范严格对齐。