二元Edwards曲线的半分算法

利用二元Edwards曲线加法公式的对称性得到可做半分的公式.在推导半分算法过程中曲线参数有两种情况:d1≠d2和d1=d2.当曲线参数d1≠d2时,利用和Weierstrass曲线的双有理等价关系、迹函数和半迹函数,得到了Edwards曲线的半分算法.而当曲线参数d1=d2时,给出了定理证明,虽然在这种情况下倍加公式更简单,但半分算法反而更复杂.进一步分析了半分算法的效率,指出虽然在二元Edwards曲线上可以进行半分运算,但目前半分算法的效率仍然比不上倍加方法.利用ω一坐标简化半分算法并应用在标量乘计算上.

Halving on binary Edwards curves

The formulas of binary Edwards curves which can be halved are transformed from the doubling ones by using the symmetry of the formulas.Two situations are to be handled in the derivation by the parameters of the curves.In the case of d1≠d2,it is naturally to get a halving algorithm by using the relation of birational equivalence from the Weierstrass curves,the trace functions and the half-trace functions.In the case of d1=d2,a theorem is given to prove it.It is not easy to get a halving algorithm,although the doubling formulas are simpler in this case.Then the efficiency of the halving algorithm is analyzed.The result shows that the efficiency of the halving algorithm cannot catch up with that of the doubling one.Using the ω-coordinate,the halving algorithm is simplified,and is further used to compute the scalar multiplication.