3. 数学基础（下）：点加与倍点运算、标量乘法与快速幂算法、射影坐标系优化

好，咱们接着聊 SM2 的数学基础。上一章我们把椭圆曲线上的点、群、阶这些概念理清了。这一章，我们要动真格的了——怎么在计算机里真正算起来。

说白了，SM2 的所有密码操作，最终都归结到一件事：标量乘法。也就是给定一个整数 k 和一个点 P，算出 kP。听起来简单，但这里面坑不少。我当年第一次实现 SM2 时，就因为在点加运算上没处理好，导致签名验证死活过不去……嗯，后来才发现是坐标系统的问题。

3.1 点加与倍点：椭圆曲线的“原子操作”

在椭圆曲线上，两个点相加有一套几何规则。你想想看，给定曲线上两点 P 和 Q，连接它们的直线与曲线交于第三点 R'，然后关于 x 轴对称得到 R，这就是 P+Q 的结果。

但计算机不认几何，只认代数。所以我们要把几何规则翻译成代数公式。

3.1.1 仿射坐标系下的点加公式

对于 SM2 使用的曲线 y² = x³ + ax + b (mod p)，设 P = (x₁, y₁)，Q = (x₂, y₂)，且 P ≠ ±Q：

λ = (y₂ - y₁) / (x₂ - x₁) mod p
x₃ = λ² - x₁ - x₂ mod p
y₃ = λ * (x₁ - x₃) - y₁ mod p

这里有个关键点：除法是在有限域中进行的，实际上是乘以分母的模逆元。模逆元运算很慢，这是后面我们要优化的核心原因。

3.1.2 倍点公式

当 P = Q 时，就是倍点运算。几何意义是过 P 点作切线：

λ = (3x₁² + a) / (2y₁) mod p
x₃ = λ² - 2x₁ mod p
y₃ = λ * (x₁ - x₃) - y₁ mod p

3.2 标量乘法与快速幂：从 kP 到高效实现

现在问题来了：要算 kP，难道要一个一个点加？k 是 256 位的整数，最大约 2²⁵⁶，一个一个加，宇宙毁灭了都算不完。

这里就要用到快速幂算法，也叫“倍点-点加”法。它的核心思想很简单：把 k 写成二进制，然后从左到右扫描。

3.2.1 从左到右的二进制方法

输入：整数 k = (k_{n-1} ... k₁ k₀)₂，点 P
输出：kP

Q = 无穷远点 O
for i from n-1 down to 0:
    Q = 2Q          // 倍点
    if k_i == 1:
        Q = Q + P   // 点加
return Q

举个例子，k = 13 = 1101₂：

你看，只用 4 次倍点和 3 次点加就算出了 13P。对于 256 位的 k，最多需要 256 次倍点和 256 次点加，效率提升了天文数字级别。

3.3 射影坐标系：为什么需要它？

好，现在算法效率上来了，但还有一个大问题：模逆运算。

你想想看，每次点加都要算一次模逆（求 λ 时的除法）。一次模逆的开销大约是模乘的 10-100 倍，具体取决于实现。256 位大数的模逆，用扩展欧几里得算法也要跑好几百次循环。

那怎么办？换个坐标系。

3.3.1 雅可比射影坐标

在雅可比射影坐标下，每个点用三个坐标表示 (X, Y, Z)，对应仿射坐标：

x = X / Z²
y = Y / Z³

无穷远点 O 对应 Z = 0。

这样做的好处是：点加和倍点运算中，完全不需要模逆。所有运算只涉及模加、模减、模乘。只在最后需要输出结果时，才做一次模逆把射影坐标转回仿射坐标。

3.3.2 射影坐标下的点加公式

设 P = (X₁, Y₁, Z₁)，Q = (X₂, Y₂, Z₂)，且 P ≠ ±Q：

U₁ = X₁ * Z₂²
U₂ = X₂ * Z₁²
S₁ = Y₁ * Z₂³
S₂ = Y₂ * Z₁³
H = U₂ - U₁
R = S₂ - S₁

X₃ = R² - H³ - 2 * U₁ * H²
Y₃ = R * (U₁ * H² - X₃) - S₁ * H³
Z₃ = H * Z₁ * Z₂

看着复杂，但全是模乘，没有模逆。我算过一笔账：一次射影坐标点加大约需要 12 次模乘 + 4 次模平方，而仿射坐标需要 1 次模逆 + 若干模乘。当模逆比模乘慢 20 倍以上时，射影坐标就全面胜出了。

3.3.3 混合加法

实际实现中还有一个常用技巧：混合加法。如果一个点是用射影坐标，另一个点是用仿射坐标（Z=1），公式可以简化，省掉一些乘法。

我个人习惯在标量乘法的主循环里用混合加法：把累加器 Q 保持为射影坐标，而基点点 P 保持为仿射坐标。这样每次点加都能省 4-5 次模乘。

3.4 本章知识体系总览

下面这张图把本章的核心逻辑串起来了：

3.5 实战建议与性能对比

说了这么多，到底用哪种方案？我直接给结论：