Paper 2021/1162

Software Implementation of Optimal Pairings on Elliptic Curves with Odd Prime Embedding Degrees

Yu Dai, Zijian Zhou, Fangguo Zhang, and Chang-An Zhao


Pairing computations on elliptic curves with odd prime degrees are rarely studied as low efficiency. Recently, Clarisse, Duquesne and Sanders proposed two new curves with odd prime embedding degrees: \textit{BW13-P310} and \textit{BW19-P286}, which are suitable for some special cryptographic schemes. In this paper, we propose efficient methods to compute the optimal ate pairing on this types of curves, instantiated by the \textit{BW13-P310} curve. We first extend the technique of lazy reduction into the finite field arithmetic. Then, we present a new method to execute Miller's algorithm. Compared with the standard Miller iteration formulas, the new ones provide a more efficient software implementation of pairing computations. At last, we also give a fast formula to perform the final exponentiation. Our implementation results indicate that it can be computed efficiently, while it is slower than that over the BLS-446 curve at the same security level.

Available format(s)
Public-key cryptography
Publication info
Pairing ComputationsOdd Prime Embedding DegreeMiller Iteration
Contact author(s)
daiy39 @ mail2 sysu edu cn
2021-09-14: received
Short URL
Creative Commons Attribution


      author = {Yu Dai and Zijian Zhou and Fangguo Zhang and Chang-An Zhao},
      title = {Software Implementation of Optimal Pairings on Elliptic Curves with Odd Prime Embedding Degrees},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1162},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.