使用 Strauss-Shamir 方法的 EC 标量乘法
EC scalar multiplication with Strauss-Shamir method
我正在搜索关于椭圆曲线标量乘法的所谓 "Strauss-Shamir method" 的信息。这是一种在 log2(k) 次加法和加倍运算中计算 k1 · P + k2 · Q 的方法，其中 k1, k2 < k。
不幸的是，虽然该算法被左右和居中引用，但 实际 算法（我敢希望，它的分析）没有在任何地方被引用。有没有人可以向我解释一下，或者至少在 pseudocode/analysis 上给我一个 link？
非常感谢！
要将数字 P 乘以 n 位标量 k，您可以根据k的二进制展开使用加倍和加法。假设 k=9。在二进制中，即 1001，您可以这样计算 9P：
R=0
R=R*2+P //the most significant '1' bit
R=R*2 //next bit is 0
R=R*2 //next bit is 0
R=R*2+P //next bit is 1
Strauss-Shamir 技巧只是通过在链内而不是外部进行加法来计算 aP + bQ。比方说，在二进制中，a=1001 和 b=0011`。然后我们就这样做：
R=0
R=R*2+P //bits from a,b = 1,0
R=R*2 //bits from a,b = 0,0
R=R*2+Q //bits from a,b = 0,1
R=R*2+P+Q //bits from a,b = 1,1
如果您预先计算 P+Q，那么这不会比一次乘法花费更长的时间。
我正在搜索关于椭圆曲线标量乘法的所谓 "Strauss-Shamir method" 的信息。这是一种在 log2(k) 次加法和加倍运算中计算 k1 · P + k2 · Q 的方法，其中 k1, k2 < k。
不幸的是，虽然该算法被左右和居中引用，但 实际 算法（我敢希望，它的分析）没有在任何地方被引用。有没有人可以向我解释一下，或者至少在 pseudocode/analysis 上给我一个 link？
非常感谢！
要将数字 P 乘以 n 位标量 k，您可以根据k的二进制展开使用加倍和加法。假设 k=9。在二进制中，即 1001，您可以这样计算 9P：
R=0
R=R*2+P //the most significant '1' bit
R=R*2 //next bit is 0
R=R*2 //next bit is 0
R=R*2+P //next bit is 1
Strauss-Shamir 技巧只是通过在链内而不是外部进行加法来计算 aP + bQ。比方说，在二进制中，a=1001 和 b=0011`。然后我们就这样做：
R=0
R=R*2+P //bits from a,b = 1,0
R=R*2 //bits from a,b = 0,0
R=R*2+Q //bits from a,b = 0,1
R=R*2+P+Q //bits from a,b = 1,1
如果您预先计算 P+Q，那么这不会比一次乘法花费更长的时间。