设G是一个循环群，
是群中的元素， 
是系数，Multi-Scalar Multiplication (MSM) 是计算多个乘法运算之和
的算法。由于群运算相对于有限域中元素的加法和乘法是复杂的，MSM算法的目标是尽可能减少群运算的次数。通常 G是一个定义在有限域 
上的椭圆曲线 y²=x³+ax+b 上的一个循环群，群的阶|G|为 b ≈ 256比特， 
。如果用朴素的快速幂算法，每个 
平均需要 1.5b次群运算，总计 1.5bn次，下面介绍一些针对较大的 n 的优化方法。
1 基于窗口方法的优化
我们可以将 b 比特的系数拆分成宽度为 c 的窗口：将系数写成
进制
这里 
，于是我们把原先 b 比特的 MSM 问题转化为较小的c 比特问题。我们可以提取
中相同的系数 (整句翻译成类似 putthe inputs of same scalar into a bucket)，写为另一种形式：
例如当 c = 3 时计算
计算
时，令部分和
，于是
而
的计算可以用递推公式
得到，每个的计算都只需要一次群运算。
在系数大小为 c 比特的 MSM 时，所有 
需要 
次群运算，所有
总计需要 
次群运算，将这些 求和需要 
次群运算，所以计算每一个大小为 c 的窗口需要
次群运算。计算 
只需要用普通的快速幂算法，需要 (b/c − 1)(c + 1) = b − c + b/c − 1 次群运算。
综上所述，宽度为 c 的窗口方法一共需要
(1)
次群运算。如果取 c = log n，群运算次数就是 2bn/ log n，当
时，群运算次数减少为原先的 1/12。
2 基于群自同态的优化
对于有限域上的椭圆曲线 y² = x³ + ax + b 上的循环群 G，如果能找到这样的群自同态 φ：存在 
，使得 φ(x, y) = (αx, βy) 对 G 上的所有点成立。容易证明这样的自同态是一个乘法映射，即能找到一个 λ 使得 φ(P) = λP 对所有 G 上的点 P 成立，这意味着当我们知道了一个点的坐标后，只需对横纵坐标乘上一个 Fp 中的数就能变成另一个点的坐标，这个重要的性质可以对算法进行进一步的优化。
当 λ = −1 时 α = 1, β = −1 只需要纵坐标取相反数就可以得到一个点的逆。利用这个特性，在朴素的快速幂算法中，可以把系数写成 non-adjacentform (NAF)，即写成
并且任意相邻的两个
不能同时非零。对于 b 比特的系数，能让快速幂算法从原先平均 3/2 · b 次群运算降低至 4/3 · b 次。这个技巧同样可以用在窗口方法的优化上。将 
写成
后，执行下面的操作：
可以得到
并且
。由于椭圆曲线群运算中加法和减法复杂度相同，我们可以将这些项按系数的绝对值分组(还是翻译成 bucket)，于是从原先的 
组减少为
组，总体所需的群运算次数从 (1) 减少为
如果椭圆曲线的参数比较特殊，例如 BLS 曲线可以写成 y² = x³+b，并且 p ≡ 1 (mod 3)。取
的 3 阶元素 α，存在对应的 λ 使得 λ(x, y) = (αx, y)
并且 λ³ ≡ 1 (mod |G|)。那么乘法运算可以做如下优化：
由 [1] 我们可以找到足够小的系数
使得上面的等式成立，这给了我们一个把 b 比特的乘法运算转化为两个 b/2 比特的乘法运算，应用在窗口方法中，群运算的次数减少为
上面两种优化都可以在 
时减少 5.5% 的群运算次数。
参考文献
[1] Francesco Sica, Mathieu Ciet, and Jean-Jacques Quisquater. Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms:Elliptic and hyperelliptic curves. In International Workshop on Selected Areas in Cryptography, pages 21–36. Springer, 2002.
关于我们
Sin7Y成立于2021年，由顶尖的区块链开发者和密码学工程师组成。我们既是项目孵化器也是区块链技术研究团队，探索EVM、Layer2、跨链、隐私计算、自主支付解决方案等最重要和最前沿的技术。
微信公众号：Sin7Y
GitHub：Sin7Y
Twitter：@Sin7Y_Labs
Medium：Sin7Y
Mirror：Sin7Y
HackMD：Sin7Y
HackerNoon：Sin7Y
Email：contact@sin7y.org
