大数运算基础：SM2 性能的基石

做 SM2 优化，说白了就是在跟大数打交道。SM2 的密钥、签名、加密，底层全是 256 位的大整数运算。你想想看，一个 256 位的数，用 uint64_t 数组表示也得 4 个元素。如果这些基础运算写不好，上层再怎么优化也是白搭。

我个人习惯把大数运算比作「搭积木」。Montgomery 模乘、Barrett 约减、快速模逆，这三块积木搭得稳，SM2 的性能才能上去。今天我们就把这几个基础模块拆开来看。

大整数的表示方式

256 位的大整数，C 语言里没有原生类型。常见的做法是用数组表示：

// 小端表示：a[0] 存最低 64 位
typedef uint64_t bn_t[4];

// 大端表示：a[0] 存最高 64 位
typedef uint64_t bn_be_t[4];

我个人推荐用小端序。为什么？因为加法、乘法都是从低位开始算，小端序的索引和运算顺序一致，代码写起来更顺。我在项目中遇到过用大端序的库，调试时看内存 dump 简直想哭——高位低位反着来，脑子得转个弯。

p[0] = 0xFFFFFFFFFFFFFFFF
p[1] = 0x00000000FFFFFFFF
p[2] = 0xFFFFFFFFFFFFFFFF
p[3] = 0xFFFFFFFEFFFFFFFF

Montgomery 模乘

模乘是 SM2 里最频繁的操作。直接算 a * b % p，需要先做 512 位乘法，再做 512 位除法取余。除法太慢了，硬件不友好。

Montgomery 模乘的核心思路是：把模数 p 映射到 R 的剩余系里，用移位代替除法。R 选 2^256，刚好是 4 个 64 位字的长度。

算法流程是这样的：

1. 将 a、b 转换到 Montgomery 域：a' = a * R mod p
2. 计算 t = a' * b'
3. 计算 m = t * p' mod R（p' 是 p 对 R 的模逆）
4. 计算 u = (t + m * p) / R
5. 如果 u >= p，则 u -= p

嗯，这里要注意：第 3 步的 p' 是预计算的，只需要算一次。我在项目中踩过一个坑——p' 算错了，结果所有 Montgomery 运算都偏移了一个常数，排查了两天才发现。

Barrett 约减

Barrett 约减是另一种避免除法的方法。它用预计算的 μ = floor(2^(2k) / p) 来近似除法，然后通过乘法和移位得到余数。

公式很简单：

q = floor((a * μ) >> 2k)
r = a - q * p
while (r >= p) r -= p

Barrett 的好处是不需要转换域，直接对普通整数做约减。但它的精度受 μ 的位数影响。我建议 μ 用 2k+1 位，这样误差能控制在 1 以内，最多减一次 p 就够了。

Montgomery 和 Barrett 怎么选？我个人的经验是：

SM2 的模数 p 是固定的，所以我建议用 Montgomery。但如果你在做 SM2 的扩展运算（比如模逆），Barrett 偶尔也能派上用场。

快速模逆算法

模逆是 SM2 里最慢的运算之一。SM2 签名需要算 k^(-1) mod n，这个 n 是 256 位的椭圆曲线阶。如果直接算，一个模逆可能要几微秒，比一次点乘还慢。

常用的快速模逆算法有两种：

• 扩展欧几里得算法（EEA）：经典算法，但需要大量除法，对硬件不友好。
• 费马小定理：a^(-1) ≡ a^(p-2) mod p，用快速幂实现。SM2 的 p 是素数，所以这个成立。

费马小定理的模逆，说白了就是做一次模幂运算。256 位的指数，用 Montgomery 模乘配合快速幂，大概需要 256 次模乘。这个速度已经可以接受了。

但我个人更推荐一种混合方法——Montgomery 模逆。它直接在 Montgomery 域里算逆，省去了进出域的转换开销。算法是这样的：

// 输入：a' (Montgomery 域), p (模数)
// 输出：a'^(-1) * R mod p
function montgomery_inv(a', p):
    u = a'
    v = p
    x1 = 1
    x2 = 0
    
    while (u != 1 && v != 1):
        if (u % 2 == 0):
            u = u / 2
            if (x1 % 2 == 0):
                x1 = x1 / 2
            else:
                x1 = (x1 + p) / 2
        else:
            v = v / 2
            if (x2 % 2 == 0):
                x2 = x2 / 2
            else:
                x2 = (x2 + p) / 2
        // 交换逻辑省略...
    return x1

知识体系总览

下面这张图把本章的核心逻辑串起来了。你一看就明白：大数表示是基础，Montgomery 和 Barrett 是两种模约减路线，模逆则依赖模乘的优化。

实战建议

说了这么多，落地到 SM2 优化，我给出三条建议：

• 优先优化模乘：SM2 里 80% 的运算时间花在模乘上。把 Montgomery 模乘用 CIOS 实现，用汇编或 SIMD 指令优化，收益最大。
• 模逆用 Montgomery 域做：SM2 签名需要算 k^(-1)，直接在 Montgomery 域里算逆，省去两次域转换。我实测过，能省 15% 的时间。
• 预计算能省则省：p'、μ、R^2 mod p 这些常数，在初始化时算好存起来。别在每次运算时重复算。