Algorithm for directly computing 7Pelliptic curves and its application
Tao Dong-ya · Journal of Computer Applications · 2013
To raise the efficiency of scalar multiplication on elliptic curve,based on the idea of trading inversions for multiplications,two efficient algorithms were proposed to compute 7P directly over binary field F2n in terms of affine coordinates.The common divisor and division polynomial were respectively introduced to compute 7P in two algorithms,their computational complexity were 2I+7S+14M and I+6S+20M,saving one inversion and two inversions respectively,compared with the Purohit′s method(PUROHIT G N,RAWAT S A,KUMAR M.Elliptic curve point multiplication using MBNR and Point halving.International Journal of Advanced Networking and Applications,2012,3(5): 1329-1337).Moreover,a new method was given to compute 7kP directly,which was more efficient than computing 7P for k times.Finally,these new algorithms were applied to scalar multiplication combined with point halving and extended MBNS(Multi-Base Number Representation).The experimental results show that the efficiency of the new method is improved about 30%-37% over the Purohit's method and about 9%-13% over the Hong's method(HONG Y F,GUI F,DING Y.Extended algorithm for scalar multiplication based on point halving and MBNS.Computer Engineering,2011,37(4): 163-165) on the elliptic curves recommended by NIST(National Institute of Standards and Technology),when the number of pre-storages points is 2 and 5.The new method can reduce the computational complexity of scalar multiplication efficiently with a few more pre-computation storage.