An Efficient Generation Method of Elliptic Curve for Pairing-Based Cryptosystems

Efficient computation of Tate pairing is a crucial factor for practical applications of pairing-based cryptosystems. Recently, there have been many improvements for the computation of Tate pairing, which focuses on the arithmetical operations above the finite field. In this paper, we analyze the structure of Miller’s algorithm firstly, which is used to implement Tate pairing. Then, according to the characteristics that Miller’s algorithm will be improved tremendous if the order of the subgroup of elliptic curve group is low hamming prime, we present an effective generation method of elliptic curve using the Fermat number, which enable it feasible that there is certain some subgroup of low hamming prime order in the elliptic curve group generated. Finally, we give an example to generate elliptic curve, which includes the subgroup with low hamming prime order. It is clear that the computation of Tate pairing above elliptic curve group generating by our method can be improved tremendously.