当前位置：首页 > news >正文

Barrett Reduction算法优化：更紧的界限消除冗余的减法

news 2025/5/6 6:39:44

1. 引言

Barrett Reduction 是一种被广泛使用的模 $m$ 运算算法。在zkSecurity 受NEAR团队所委托的（针对RustCrypto: NIST P-256 (secp256r1) elliptic curve——https://github.com/RustCrypto/elliptic-curves/tree/master/p256）进行的 Rust p256 crate 审计 中分析表明，Barrett Reduction 的误差界限比传统假设的要更紧。对于大多数用于密码学的模（如 NIST 曲线），商的近似误差最多为 1（而不是 2）。这个改进在实际中消除了对第二次减法的需求。通过 采用这一优化——详情见PR p256: remove unnecessary sub in scalar Barrett reduction #1155，RustCrypto p256 在标量乘法中实现了 14% 的性能提升。

2. 什么是 Barrett Reduction？

Barrett Reduction 是一种高效计算除法余数（即模运算 $\bmod m$ ）的方法，它避免了直接除法操作的高昂计算代价。

可将计算 $\bmod m$ ，表示为 $\cdot m + r$ ，其中 $q$ 是商， $r$ 是余数。在实际应用中（如密码学中的有限域运算），模 $m$ 通常是一个用 $k$ 个 limb 表示的大整数。每个 limb 是一个 32 位或 64 位的值（取决于机器字长），从而基数radix $b = 2^{32}$ 或 $2^{64}$ 。而值 $x$ 是一个 $2 k$ -limb 的整数，因为它通常来自两个 $k$ -limb 整数的乘积。

一种计算 $r$ 的方式是先计算：
$\left\lfloor \frac{x}{m} \right\rfloor$

一旦确定了 $q$ 值，就可通过 $\cdot m$ 得到余数。Barrett Reduction 提供了一种更高效的方式来近似计算 $q$ ，从而避免了昂贵的直接除法。

先将上面的公式重写为：
$\lfloor x / m \rfloor = \left\lfloor\frac{x}{m} \cdot \frac{b^{2k}}{b^{2k}}\right\rfloor = \left\lfloor\frac{x}{m} \cdot \frac{b^{2k}}{b^{k+1}\cdot b^{k-1}}\right\rfloor = \left\lfloor\frac{b^{2k}}{m} \cdot \frac{x}{b^{k-1}} \cdot \frac{1}{b^{k+1}}\right\rfloor$

到目前为止，计算仍是精确的。但在此不打算精确计算 $q$ ，而是近似计算其值：
$\tilde{q} = \left\lfloor \frac{{\color{red}{\lfloor}} \frac{x}{b^{k-1}} {\color{red}{\rfloor}} \cdot {\color{red}{\lfloor}} \frac{b^{2k}}{m} {\color{red}{\rfloor}}}{b^{k+1}}\right\rfloor$

从而允许 预先、计算：

$\mu = \left\lfloor \frac{b^{2k}}{m} \right\rfloor$

从而重写为：

$\left\lfloor \frac{ \left\lfloor \frac{x}{b^{k-1}} \right\rfloor \cdot \mu }{b^{k+1}} \right\rfloor$

注意：

运算中的 $\lfloor \frac{\cdot}{b^{k-1}} \rfloor$ 和 $\lfloor \frac{\cdot}{b^{k+1}} \rfloor$ 可以通过右移操作快速实现。

由于两次近似计算可能小于其精确结果，因此有 $\tilde{q} \leq q$ 。传统分析认为 $\tilde{q} \in [q - 2, q]$ ，（将在后面的“分析部分”中详细说明）。这意味着近似商 $\tilde{q}$ 至多比真实商 $q$ 小 2。

3. 在 $\approx \tilde{q} \cdot m + r$ 中计算 $r$

如果我们已经精确计算出 $q$ ，那么可以直接通过下式计算：
$\cdot m$

由于 $\in [0, m)$ ，这个减法仅涉及 $m$ 的比特长度。因此，可以只用最低的 $b^k$ 位来更快地完成计算：

$\cdot m \mod b^k = (x \bmod b^k) - (q \cdot m \bmod b^k)$

（其中模 $b^k$ 运算在二进制机器上可以高效实现）
在这里插入图片描述

然而，请记住在此计算的是商的近似值 $\tilde{q}$ ，且 $\tilde{q} \in [q - 2, q]$ 。

从而可能有以下三种情况之一：

1）情况1： $\tilde{q} \cdot m$
2）情况2： $(\tilde{q} + 1) \cdot m$
3）情况3： $(\tilde{q} + 2) \cdot m$

为了计算 $r$ ，首先尝试情况 1。如果结果不小于 $m$ ，再减去一次或两次 $m$ ，将结果调整到正确范围内。

这意味着不能保证 $\tilde{r} = x - \tilde{q} \cdot m < b^k$ 立即成立。相反，值可能比 $m$ 或 $2 m$ 更大。

由于 $m < b^k$ ，可以推出：

$\cdot m < 2 \cdot b^k$

因此，可以对近似值进行上界估计：

$\leq \tilde{r} \leq r + 2m < b^k + 2 \cdot b^k = 3 \cdot b^k < b^{k+1}$

接着，可以更高效地计算 $\tilde{r}$ ：

$\tilde{r} = \left( (x \bmod b^{k+1}) - (\tilde{q} \cdot m \bmod b^{k+1}) \right) \bmod b^{k+1}$

再次强调，模 $b^{k+1}$ 运算在二进制机器上是非常高效的。

最终，可得出一个与 Handbook of Applied Cryptography 第 14 章 所描述的算法一致的形式。上述步骤与书中描述的过程紧密对应。
在这里插入图片描述

4. 更紧的界限分析

近似商 $\tilde{q}$ 的界限直接决定了需要将 $r$ 减去多少次模数 $m$ 才能使结果落入正确范围。传统上认为该界限为 $\tilde{q} \in [q - 2, q]$ 。本节将展示：在实际中使用的大多数模数中，更紧的界限成立，即 $\tilde{q} \in [q - 1, q]$ 。

回顾定义：

$\left\lfloor \frac{x}{m} \right\rfloor$

$\tilde{q} = \left\lfloor \frac{\left\lfloor \frac{x}{b^{k-1}} \right\rfloor \cdot \left\lfloor \frac{b^{2k}}{m} \right\rfloor}{b^{k+1}} \right\rfloor$

由于 $\tilde{q}$ 是通过截断 $\frac{x}{m}$ 得到的近似值，它自然满足 $\tilde{q} \leq q$ 。

设 $\alpha = x \bmod b^{k-1}$ ，则 $\alpha < b^{k-1}$ ；再设 $\beta = b^{2k} \bmod m$ ，则 $\beta < m$ 。则可以移除floor函数：

$\left\lfloor \frac{x}{b^{k-1}} \right\rfloor = \frac{x - \alpha}{b^{k-1}}$

$\left\lfloor \frac{b^{2k}}{m} \right\rfloor = \frac{b^{2k} - \beta}{m}$

于是可以简化 $\tilde{q}$ 的表达式：
$\begin{align*} \tilde{q} &= \lfloor \frac{\lfloor \frac{x}{b^{k-1}} \rfloor \cdot \lfloor \frac{b^{2k}}{m} \rfloor}{b^{k+1}} \rfloor\\ &= \lfloor \frac{ \frac{x - \alpha}{b^{k-1}} \cdot \frac{b^{2k} - \beta}{m}}{b^{k+1}} \rfloor \\ &= \lfloor \frac{(x - \alpha) \cdot (b^{2k} - \beta)}{m \cdot b^{2k}} \rfloor \\ &= \lfloor \frac{x}{m} - {\color{red}{\frac{\alpha \cdot b^{2k} + \beta \cdot (x - \alpha)}{m \cdot b^{2k}}}} \rfloor \end{align*}$

用 ${\color{red}{z}}$ 表示上述红色部分，即：

$\frac{\alpha \cdot b^{2k} + \beta \cdot (x - \alpha)}{m \cdot b^{k+1}} \quad \text{(注意：$ z \geq 0 $)}$

于是有：
$\tilde{q} = \lfloor \frac{x}{m} - {\color{red}{z}} \rfloor$

利用floor函数的不等式：
$\lfloor x \rfloor + \lfloor y \rfloor + 1 \ge \lfloor x + y \rfloor$
从而有：
$\lfloor \frac{x}{m} - z \rfloor + \lfloor z \rfloor + 1 \ge \lfloor \left(\frac{x}{m} - z\right) + z \rfloor = \lfloor \frac{x}{m} \rfloor = q$

即等价为：
$\tilde{q} + \lfloor z \rfloor + 1 \ge q$

因此， $z$ 的界限对于分析 $\tilde{q}$ 的界限是关键。如果能证明 $\leq z < 2$ ，那么 $\left\lfloor z \right\rfloor \leq 1$ ，就能得出：

$\tilde{q} + 2 \ge \tilde{q} + \lfloor z \rfloor + 1 \ge q$

从而验证更紧的界限。接下来，将分析 $z$ 的具体界限。

4.1 证明 $\tilde{q} \in [q - 2, q]$

有：
$\begin{align*} z &= \frac{\alpha \cdot b^{2k} + \beta \cdot (x-\alpha)}{m \cdot b^{2k}} \\ &\lt \frac{{\color{red}{b^{k-1}}} \cdot b^{2k} + \beta \cdot {\color{red}{b^{2k}}}}{m\cdot b^{2k}} \\ &= \frac{b^{k-1} + \beta}{m} \end{align*}$

已知 $b^{k-1} < m$ （因为 $m$ 是一个 $k$ -limb 整数），且 $\beta < m$ ，因此：

$\frac{b^{k-1} + \beta}{m} < \frac{m + m}{m} = 2$

由此可得：

$\lfloor z \rfloor \leq 1$

这正是所想要的。因此可得出结论：

$\tilde{q} + 2 \geq \tilde{q} + \lfloor z \rfloor + 1 \geq q$

4.2 实际中的更紧界限： $\tilde{q} \in [q - 1, q]$

至此已经证明在所有情况下 $\tilde{q} \in [q - 2, q]$ 。然而，这是一个较为宽松的界限。这里进一步说明，在实际中使用的大多数模数 $m$ 下，可以得到一个更紧的界限：即 $z < 1$ ，从而：

$\tilde{q} + 1 \geq \tilde{q} + \lfloor z \rfloor + 1 \geq q$

接下来来看哪些模数 $m$ 满足这个更紧界限。回顾之前的推导：

$\frac{b^{k-1} + \beta}{m}$

要使 $z < 1$ 成立，需要：

$b^{k-1} + \beta \leq m$

即：

$\beta \leq m - b^{k-1}$

这表示：如果 $\beta \leq m - b^{k-1}$ ，那么 $z < 1$ ，从而 $\tilde{q} \in [q - 1, q]$ 。可以将其形式化为更紧界限准则：

$\boxed{\text{Given a modulus } m \text{, if } \beta \le m - b^{k-1} \text{ (where } \beta = b^{2k} \bmod{m}\text{), then } \tilde{q} \in [q-1, q] \text{.}}$
给定模数 $m$ ，若满足 $\beta = b^{2k} \bmod m \leq m - b^{k-1}$ ，则 $\tilde{q} \in [q - 1, q]$ 。

需要注意的是： $\beta = b^{2k} \bmod m \in [0, m)$ 。在实际中， $b$ 通常为 $2^{32}$ 或 $2^{64}$ ，而 $m$ 通常接近 $b^k$ ，因此 $m - b^{k-1}$ 通常接近 $m$ 本身。

而且， $\beta = b^{2k} \bmod m$ 对于随机模数 $m$ 的分布近似于在区间 $[0, m)$ 上的均匀分布，因此 $\beta \leq m - b^{k-1}$ 的概率非常高。于是，大多数模数 $m$ 都会满足 $z < 1$ ，从而得出 $\tilde{q} + 1 \geq q$ 。

为了量化这种概率，假设常见情况是 $\frac{b^k}{2} < m < b^k$ ，且 $\beta$ 在 $[0, m)$ 上均匀分布，那么：

$\Pr[\beta \leq m - b^{k-1}] = \frac{m - b^{k-1}}{m} > 1 - \frac{2}{b}$

从而有：

当 $b = 2^{32}$ 时，满足更紧界限的概率超过 $\frac{1}{2^{31}}$
当 $b = 2^{64}$ 时，该概率超过 $\frac{1}{2^{63}}$

因此，在实际中几乎所有模数都满足更紧界限 $\tilde{q} \in [q - 1, q]$ 。

直观解释是这样的： $\mu = \left\lfloor \frac{b^{2k}}{m} \right\rfloor$ 是 $b^{2k} \div m$ 的商，而 $\beta$ 是其余数。如果 $\beta$ 很小，那么 $\mu$ 非常接近实际的商，从而计算 $\tilde{q}$ 时的近似误差就很小。本分析表明：只要 $\beta \leq m - b^{k-1}$ ，就可以保证计算出的 $\tilde{q}$ 最多比 $q$ 小 1。而这个对 $\beta$ （或 $m$ ）的要求相当宽松，因此大多数模数都满足这个更紧的界限。

5. Barrett 除法在实际实现中的优化

更紧的界限使得 Barrett 除法的实现更加高效。根据传统分析，为了使结果落入正确范围，可能需要将 $r$ 减去模数 $m$ 两次。而对于一个给定的模数 $m$ ，如果满足更紧的界限条件，那么最多只需减一次 $m$ ，这意味着可以节省一次减法操作。

这对于常数时间实现尤为重要，因为常数时间实现通常会总是执行最多次数的减法。如，在 RustCrypto 的 P-256 标量域实现 中，始终执行两次减法：

pub(super) const fn barrett_reduce(lo: U256, hi: U256) -> U256 {[...]let r1 = [a0, a1, a2, a3, a4];let r2 = q3_times_n_keep_five(&q3);let r = sub_inner_five(r1, r2);// Result is in range (0, 3*n - 1),// and 90% of the time, no subtraction will be needed.let r = subtract_n_if_necessary(r);let r = subtract_n_if_necessary(r);U256::new([r[0], r[1], r[2], r[3]])
}

由于 P-256 的标量域满足 $\beta \leq m - b^{k-1}$ ，所以更紧的界限 $\tilde{q} \in [q - 1, q]$ 成立。这意味着计算得到的 $\tilde{q}$ 最多只比真实商 $q$ 小 1。

也就是说，为了得到最终结果，最多只需要将 $r$ 减去一次 $m$ 。因此，以上代码中的第二次 subtract_n_if_necessary 调用是不必要的，可以安全地删除，从而提升运行效率。

基准测试显示，仅仅去掉第二次减法操作，就可以使乘法和求逆的性能提升 14%。

scalar operations/multime:   [38.900 ns 38.957 ns 39.026 ns]change: [-14.379% -14.052% -13.734%] (p = 0.00 < 0.05)Performance has improved.
scalar operations/inverttime:   [20.716 µs 20.758 µs 20.823 µs]change: [-14.817% -14.331% -13.969%] (p = 0.00 < 0.05)Performance has improved.

如前一节分析所示，更紧的界限在几乎所有模数中都成立。因此，这项优化适用于大多数固定模数的 Barrett 除法实现（如用于椭圆曲线加密 ECC、零知识证明 ZKP）。

以下是一个 Python 脚本，用于测试某个模数 $m$ 是否满足更紧的界限：

# Barrett 除法的更紧界限判断准则def tighter_bound_criterion(m):def inner_test(m, b):# 选择 k，使得 b^{k-1} < m < b^kk = 1while b**k < m:k += 1print("k = ", k)beta = b**(2*k) % m# 判断是否满足更紧的界限return beta <= m - b**(k-1)# 同时测试 b=2^32 和 b=2^64return inner_test(m, 2**32) and inner_test(m, 2**64)# P-256 标量域
assert(tighter_bound_criterion(0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551) == True)# P-256 基域
assert(tighter_bound_criterion(0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff) == True)