Divide-and-Pair SMT for gnark-crypto Twisted Edwards Curves

This note summarizes the subgroup-membership test (SMT) induced by the divide-and-pair framework (https://eprint.iacr.org/2026/749) for the twisted Edwards curves currently present in gnark-crypto.

Main rule

Let $E/\mathbb{F}_p$ be a twisted Edwards curve with group order $h \cdot r$, where $r$ is prime and $h$ is a small power of $2$.

The divide-and-pair SMT depends on:

• whether $h \mid (p - 1)$, which determines whether the relevant Tate pairing is already non-degenerate over $\mathbb{F}_p$;
• whether the rational small torsion is cyclic or split.

For $E/\mathbb{F}_p: ax^2+y^2=1+dx^2y^2$, the rational $2$-torsion is:

• cyclic if $\text{Legendre}(ad) = -1$;
• split if $\text{Legendre}(ad) = +1$.

Why this works:

• $E$ is birational over $\mathbb{F}_p$ to the Montgomery curve $B y^2 = x^3 + A x^2 + x$ with $A = \frac{2(a+d)}{a-d}, \qquad B = \frac{4}{a-d}.$
• The rational $2$-torsion on the Montgomery model is determined by the roots of $x^3 + A x^2 + x = x(x^2 + A x + 1).$
• One $2$-torsion point is always rational, namely $x = 0$.
• The other two $2$-torsion points are rational iff $x^2 + A x + 1$ splits over $\mathbb{F}_p$, i.e. iff its discriminant $A^2 - 4$ is a square in $\mathbb{F}_p$.
• Using $A = 2(a+d)/(a-d)$, we get $A^2 - 4 = \frac{16ad}{(a-d)^2}.$
• Since $16$ and $(a-d)^2$ are squares, $A^2 - 4$ is a square iff $ad$ is a square.

Therefore:

• $\text{Legendre}(ad) = -1$ means there is only one rational nonzero $2$-torsion point, so the rational $2$-primary torsion is cyclic;
• $\text{Legendre}(ad) = +1$ means the full rational $2$-torsion is split, so the rational $2$-primary torsion has rank $2$.

Equivalently:

• if $\text{Legendre}(ad) = -1$ and $h = 8$, then $E(\mathbb{F}_p) \cong \mathbb{Z}/(8r)$;
• if $\text{Legendre}(ad) = -1$ and $h = 4$, then $E(\mathbb{F}_p) \cong \mathbb{Z}/(4r)$;
• if $\text{Legendre}(ad) = +1$ and $h = 4$, then $E(\mathbb{F}_p) \cong \mathbb{Z}/(2r) \times \mathbb{Z}/2$.

In all gnark-crypto twisted Edwards companion curves, $h \mid (p - 1)$ always because $p$ is the subgroup order $r$ of the SNARK curve chosen s.t. a high power of $2$ divides $r-1$, so no $\mathbb{F}_{p^2}$ extension is needed.

Curves

Consequences

• All cofactor-$8$ companion Edwards curves in gnark-crypto admit the most favorable base-field divide-and-pair SMT: a single degree-$8$ Tate pairing, equivalently an octic residuosity check on a precomputed Miller value.
• BLS12-377 similarly admits a single degree-$4$ pairing check.
• Bandersnatch is different: its rational $2$-torsion is split, so SMT requires two independent degree-$2$ checks. This matches the existing gnark-crypto implementation, which uses two Legendre-symbol tests: https://hackmd.io/@yelhousni/tate-subgroup.
• Since the base field already gives non-degeneracy for the relevant $2$-power torsion, extending to $\mathbb{F}_{p^2}$ would not simplify SMT for any of these curves.
• In all cases present in gnark-crypto the Divide-and-Pair SMT reduces to the Koshelev test.
• Code in: https://github.com/Consensys/gnark-crypto/pull/833