基于折半运算的快速双基数标量乘算法

Fast DBNS scalar multiplication algorithm based on halving operation

为了提高椭圆曲线标量乘法效率,对二元域上椭圆曲线的基于双基数的标量乘法进行改进。在底层域推导出直接计算3kP的快速算法,该算法只需一次求逆;新设计的以1/2和3为基的双基数编码可结合高效的直接计算3kP和折半运算,基于该双基数编码的标量乘算法只涉及到点加运算、折半运算、三倍点和直接计算3kP,底层域运算复杂性得到降低,在NIST推荐的椭圆曲线上比Dimitrov算法效率提高70%以上,比Wong方法提高10%以上。

To raise the efficiency of scalar multiplication on elliptic curve, a scalar multiplication algorithm based on double base number system over binary field was improved. Firstly a fast direct computing 3^kP algorithm in field was deduced, which only needed one inversion; the new double base number chain based on 1/2 and 3 could be integrated with high-speed direct computing 3^kP and halving algorithm. Scalar multiplication based on the new chain only employed point addition, halving algorithm, triplication and direct computing 3^kP. Thus the complexity was depressed and the efficiency was improved about 70% over Dimitrov algorithm and about 10% over Wong method on the elliptic curves recommended by NIST.