Paper 2022/367

Efficient Algorithms for Large Prime Characteristic Fields and Their Application to Bilinear Pairings

Patrick Longa, Microsoft Research

We propose a novel approach that generalizes interleaved modular multiplication algorithms for the computation of sums of products over large prime fields. This operation has widespread use and is at the core of many cryptographic applications. The method reformulates the widely used lazy reduction technique, crucially avoiding the need for storage and computation of "double-precision" operations. Moreover, it can be easily adapted to the different methods that exist to compute modular multiplication, producing algorithms that are significantly more efficient and memory-friendly. We showcase the performance of the proposed approach in the computation of multiplication over an extension field $\mathbb{F}_{p^k}$, and demonstrate its impact with record-breaking implementations of bilinear pairings. Specifically, we accomplish a full optimal ate pairing computation over the popular BLS12-381 curve, designed for the 128-bit security level, in under half a millisecond on a 3.2GHz Intel Coffee Lake processor, which is about $1.40\times$ faster than the state-of-the-art. Similarly, we perform the same computation over the BLS24-509 curve, targeting the 192-bit security level, in $\sim$ 2.6 milliseconds, achieving a speedup of more than $1.30\times$. We also report a significant impact on other applications, including protocols based on supersingular isogenies.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in TCHES 2023
Prime fieldsextension fieldsbilinear pairingsBLS12-381supersingular isogeniesefficient computation
Contact author(s)
plonga @ microsoft com
2023-09-11: last of 2 revisions
2022-03-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Patrick Longa},
      title = {Efficient Algorithms for Large Prime Characteristic Fields and Their Application to Bilinear Pairings},
      howpublished = {Cryptology ePrint Archive, Paper 2022/367},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.