Fast Algorithm Of Elliptic Curve Cryptosystem

Elliptic curve cryptosystem was introduced in the mid-1980s independently by Miller and Koblitz, which has been proven in practice to be one of three safe and effective public-key cryptosystems. In the elliptic curve cryptosystem, the core operation is elliptic curve scalar multiplication (nP), which is crucial to efficient implementation of elliptic curve cryptosystem. Therefore, a lot of research has been done for the improvement of scalar multiplication at present. The method of the improvement of scalar multiplication generally can be divided into four categories, namely, improving the operation efficiency of field, using different coordinate systems, improving the addition chain of n in scalar multiplication, as well as optimizing some special curves.In this paper, we mainly improve the method of addition chain of n in scalar multiplication from two different aspects. On the one hand, we improve the mixed having and ternary method to express n from the standard non-singular elliptic curve with character 2. On the other hand, we improve the mixed binary and ternary method to express n from the standard elliptic curve with character more than 3 , and we generalize the mixed binary, ternary and quinary method to express n. Some examples are given in order to achieve improved algorithms, and various computational quantity of algorithms are compared. The results show that our approaches lead to lower complexity which contributes to the efficient implementation of elliptic curve scalar multiplication.