Fast DBNS scalar multiplication algorithm based on halving operation
基于折半运算的快速双基数标量乘算法

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.