Paper 2026/2667

Faster complete formulas and their application to curves with efficient endomorphisms

Diego F. Aranha, Aarhus University
Paulo L. Barreto, University of Washington Tacoma
Abstract

We revisit scalar multiplication on prime curves $y^2 = x^3 + b$ with $p \equiv 1 \pmod 3$, a family that includes secp256k1, BN and BLS curves. Applying a 15-year-old technique in a new way, we improve the best complete addition from $12$ to $11$ multiplications ($10$ in mixed coordinates), the first improvement in 10 years: its final stage is a 3D cross product, which needs only five multiplications. In \texttt{libsecp256k1}, the new formulas make constant-time fixed-base scalar multiplication $5.2$\% faster. We also give a complete tripling formula that costs the same as incomplete Jacobian tripling, and combine both formulas into an exception-free width-3 $\tau$-NAF with $\tau = 1 - \omega$ and a six-point table. In an operation-count model it is about 14\% faster than exception-free GLV at 256 bits and 3--7\% faster than the fastest incomplete GLV. In RELIC, on BLS12-381, BLS24-509 and BLS48-575, the $\tau$-NAF in $\mathbb{G}_1$ is 5--7\% faster than GLV with the same complete formulas, and its regular (constant-time) variant is 8--10\% faster than regular 2-GLV with complete formulas and 3--7\% faster than 2-GLV with incomplete Jacobian formulas. In $\mathbb{G}_2$, the $\tau$-NAF is 4--11\% faster than GLS in variable time, but in constant time the cheap Jacobian doubling over extension fields makes the exception-free variant 10--19\% slower than Jacobian GLS. Finally, an `imaginary' Toom-Cook variant for the extension fields makes $\mathbb{G}_T$ exponentiation 4--6\% faster on BLS24-509 and BLS48-575, and a cyclotomic cube costing 0.77 multiplications brings the $\tau$-adic method to $\mathbb{G}_T$, where it makes exponentiation 2--3\% faster on BLS24-509 and 11\% faster on BLS48-575.

Note: Stronger GLV/GLS baselines (incl. 2-GLV) added, all benchmarks re-measured; AI disclosure added.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
Elliptic curvesPairingsComplete formulasScalar multiplication
Contact author(s)
dfaranha @ cs au dk
pbarreto @ uw edu
History
2026-11-18: revised
2026-10-28: received
See all versions
Short URL
https://ia.cr/2026/2667
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2667,
      author = {Diego F. Aranha and Paulo L. Barreto},
      title = {Faster complete formulas and their application to curves with efficient endomorphisms},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2667},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2667}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.