Kyber中常数除数快速整数除法（含舍入）算法原理与差异问询

架构老林

2026-6-16

Kyber（ML-KEM）AVX2压缩算法原理与精度差异问题

我目前正专注于Kyber（ML-KEM）的实现工作，发现其压缩操作的AVX2版本采用了快速整数除法算法。

压缩操作的核心需求

压缩操作需计算 x * (2**10 / Q)：

x为int16_t类型输入，是Q素域中的多项式系数
Q为素数：Kyber标准中为3329，下述测试代码中使用7681
结果需遵循四舍五入规则：2.1~2.499...向下取整为2，大于等于2.5则向上取整为3

参考版与AVX2版实现

参考版实现逻辑

参考版代码逻辑清晰，公式可归纳为：

((x << 10) + q/2) / q

对应代码片段：

....
uint16_t t[4];
for (i = 0; i< K; i++)
{
    for (j = 0; j< 256/ 4; j++)
    {
        for (k = 0; k < 4; k++) {
            // PARAM_Q here is 7681
            t[k] = ((((uint32_t)a->vec[i].coeffs[4 * j + k] << 10) + PARAM_Q / 2) / PARAM_Q) & 0x3ff;
        }
// other loop operations
....

AVX2优化版实现

另一个compress10的AVX2实现采用了快速整数除法策略，公式归纳为：

(((x*4 + 15) * 8737) >> 16) >> 2

对应代码片段：

// input "a" is a polyvec
//Here q is 7681, not same as current Kyber (ML-KEM)
const __m256i fdiv = _mm256_set1_epi16(8737);//fast division // floor(2^26 / q + 0.5)
const __m256i hfq = _mm256_set1_epi16(15);
for(int i = 0; i < K; i++) {
  for(int j = 0; j < 256; j++) {
    d0.vec = _mm256_loadu_si256((__m256i *)&a->vec[i].coeffs[16 * j]);

    d0.vec = _mm256_slli_epi16(d0.vec, 2);
    d0.vec = _mm256_add_epi16(d0.vec, hfq);
    d0.vec = _mm256_mulhi_epi16(d0.vec, fdiv);
    d0.vec = _mm256_srli_epi16(d0.vec, 2);

    ......
  }
}