The fast implementation of bilinear pairing on elliptic curve has heavily depended on the Miller’s algorithm.In this paper

an improved Miller’s algorithm is presented and the basic idea of this algorithm is that it combines the {2

3}-double-base chains with the Miller’s algorithm

thus

it can reduces the iteration times in Miller’s algorithm efficiently during the computation of bilinear pairing.What is important

this new algorithm can not only be applied to the case of super-singular elliptic curve

but also can be applied to the case of ordinary elliptic curve.As indicated by the experimental results in this paper

the computational efficiency of our new method has been improved by 10.6%~20.3% on average than other existing methods.