Paper 2026/749

Divide-and-Pair: Faster subgroup membership testing for elliptic curves

Abstract

Subgroup membership testing (SMT) on an elliptic curve with non-trivial cofactor is essential to prevent small-subgroup attacks in cryptographic protocols. In the existing literature, there exist two non-trivial methods for SMT on elliptic curves with modest cofactor (typically a power of $2$): Pornin's approach tests membership by repeatedly dividing by prime divisors of the cofactor (mostly halving), finishing with a Legendre symbol; Koshelev's approach replaces all divisions with Tate pairings (possibly in the quadratic extension of the base field), but requires non-degeneracy conditions that are not always met. In this paper, we observe that both approaches sit at the extremes of a single division-pairing trade-off. The resulting method, \mainalgorithm, is always at least as fast as either Pornin's or Koshelev's method and strictly faster in many cases. We instantiate \mainalgorithm on five curves in widespread use, including Curve25519, Curve448, GC256A, Four$\mathbb{Q}$ and Jubjub. Our Go implementation, built on the open-source \texttt{gnark-crypto} library, achieves significant speedups over state-of-the-art tests, namely of $1.6\times$ on Curve25519, $1.3\times$ on Curve448, $1.4\times$ on GC256A, $10.8\times$ on Four$\mathbb{Q}$ and $7\times$ on Jubjub.