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

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

news 来源：原创 2025/8/24 14:09:00

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)

6. 结论

本分析表明：在实际使用的大多数模数中，对商的近似值 $\tilde{q}$ 的误差界限可以从传统的 $[q - 2, q]$ 收紧为 $[q - 1, q]$ 。

这一更紧的界限在大多数情况下消除了第二次减法的必要性，从而实现了更快速、更高效的实现。

本文还展示了该优化如何应用于现实中的加密库，如 RustCrypto 的 P-256 标量域实现中，仅删除不必要的减法，就显著提升了性能。这一发现同样适用于其他依赖固定模数的密码系统及零知识证明框架。

参考资料

[1] zkSecurity团队2025年5月1日博客 Optimizing Barrett Reduction: Tighter Bounds Eliminate Redundant Subtractions

1. 引言

2. 什么是 Barrett Reduction？

3. 在 x ≈ q ~ ⋅ m + r x \approx \tilde{q} \cdot m + r x≈q~​⋅m+r 中计算 r r r