Paper 2026/2667
Faster complete formulas and their application to curves with efficient endomorphisms
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
-
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}
}