Complexity Analysis on Elliptic Scalar Multiplication

Elliptic scalar multiplication is the most cost operation of the elliptic curve cryptosystems. The fast implementation of Elliptic Curve Cryptography mainly depends on the fast computation of elliptic scalar multiplication kP. This paper analysis and compare the complexity of the “add and double methods” and Montgomery methods. We show that the Montgomery methods has more cost than the “add-and-double” method if the ratio of the cost of field inversion and field multiplication is more than 2 under the affine coordinate representations without concern the cost of field adding and field squaring in GF(2^m). In fact, the ration of I and M is more than 7 as the size of binary field is not less than 128, which means that the algorithm 3.1 outperforms the algorithm 3.2.