如何写出最快的椭圆曲线(secp256k1)算法
secp256k1是bitcoin和ethereum中重要的数字签名算法，关于secp256k1的数学原理本文不做介绍（网上可以找到很多优秀的资料），只聊聊技术实现上的性能优化。
0. 性能对比
关于我实现的C# secp256k1可查看源码：
https://github.com/ibukisaar/CSharpSecp256k1
1. 大数运算
大数运算(加减乘)可利用LLVM IR中自带的大整型，这会比自己写汇编来得方便点，不过需要注意不能进行除法和求余运算，好在后续也不需要这两个运算。
参考：https://llvm.org/docs/LangRef.html#integer-type
从clang 11开始，可以在C/C++中直接使用LLVM IR中的大整型，例如：
typedef unsigned _ExtInt(256) u256; // 表示256位无符号整型
参考：https://releases.llvm.org/11.0.0/tools/clang/docs/LanguageExtensions.html#extended-integer-types
不过可惜的是，LLVM并不会对256位大整型a*a的情况再进一步优化，在x64平台理论上只需要10个mul指令，而LLVM依然使用16个mul指令。后续我可能会研究一下LLVM Pass来进一步优化C# secp256k1库。
2. 大数快速取模
在secp256k1中只需要对2个256位大整型取模，它们分别是：
P=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
N=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
这2个数都有个优点那就是非常接近2^256，于是u512%P和u512%N可以分别优化成：
有趣的是，运算时的中间结果并一定要对P或N取模，而只要保持同余就行。不过这就需要具体分析作出取舍了，不再过多介绍。
关于大数快速取模可参考我的知乎文章：
https://zhuanlan.zhihu.com/p/78183896
3. 加法链
secp256k1中有3个运算非常耗时，都属于大数模幂运算，分别是：
对于上面3个运算，采用快速幂并不是最快的，使用加法链可以进一步减少乘法次数。
例如求x^23，使用快速幂需要7次乘法：
x^2 // 1次
x^4 // 1次
x^8 // 1次
x^16 // 1次
x^23 = x^16 * x^4 * x^2 * x // 3次
而使用加法链只需要6次乘法：
x^2 // 1次
x^3 = x^2 * x // 1次
x^5 = x^2 * x^3 // 1次
x^20 = ((x^5)^2)^2 // 2次
x^23 = x^20 * x^3 // 1次
当指数很大时，加法链减少的乘法次数很可观，但是求最短加法链是个非常难的问题，目前针对P和N的加法链应该不是最优的。
参考：https://briansmith.org/ecc-inversion-addition-chains-01
一个可以求加法链的开源程序：
https://github.com/mmcloughlin/addchain
4. 雅可比坐标
将椭圆曲线中的二维坐标映射到雅可比坐标可避免运算过程中求逆。
这块我可能讲不清楚，我并不是数学专业的，可以参考其他大佬的文章：
https://zhuanlan.zhihu.com/p/87490028
次方案
secp256k1在素域中大部分都是在进行四则运算，因此将坐标采用分数表示也可以避免求逆，但是此方案是不如雅可比坐标的，最终(u256/u256 X, u256/u256 Y)变换到(u256 X, u256 Y)会比雅可比坐标多出1次求逆运算。
5. w-NAF
和加法链很像，不过它是用于减少椭圆曲线点乘法(点*标量)的加法次数。
例如求31P，采用类似快速幂的算法需要8次加法：
2P // 1次
4P // 1次
8P // 1次
16P // 1次
31P = P + 2P + 4P + 8P + 16P // 4次
如果我们将它变成求32P-P，那么只需要6次加法：
2P // 1次
4P // 1次
8P // 1次
16P // 1次
32P // 1次
31P = 32P + (-P) // 1次
点取负运算：
-(X, Y) = (X, -Y mod P)
可以看到点取负性能代价很低，因此可以忽略不计。
参考：https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
6. 打表
secp256k1关于基点(G)的点乘法很频繁，因此可以考虑打表加速G的点乘法。
与G相乘的是一个256位的无符号整型，设为a，我们将它看成256进制，于是这个数可以表示为：
secp256k1椭圆曲线是个阿贝尔群，根据阿贝尔群的定义，很容易得到：
对于256进制中的每位，我们只需要计算出所有的256种情况并存进表里即可，表共需要32*256项，并且每位刚好对应了1 byte。
于是关于G的点乘法只需要31次加法。
7. 总结
还有些无关紧要的细节就不说了，例如使用格雷码(graycode)加速基点乘法表的创建。
有什么疑问欢迎在评论区提出，不过我能力有限并不是100%能解答。
