---
# System prepended metadata

title: Divide-and-Pair SMT for `gnark-crypto` Twisted Edwards Curves

---

# 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 $\#E(\mathbb{F}_p) = h 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

| Curve | Cofactor | $v_2(p-1)$ | $\text{Legendre}(ad)$ | Rational structure | Divide-and-pair SMT |
|---|---:|---:|---:|---|---|
| BN254      (baby-jubjub) | 8 | 28 | $-1$ | $\mathbb{Z}/(8r)$ | $0$ halvings, $1$ degree-$8$ pairing |
| bls12-377 | 4 | 47 | $-1$ | $\mathbb{Z}/(4r)$ | $0$ halvings, $1$ degree-$4$ pairing |
| bls12-381 (Jubjub) | 8 | 32 | $-1$ | $\mathbb{Z}/(8r)$ | $0$ halvings, $1$ degree-$8$ pairing 
| bls12-381 (bandersnatch) | 4 | 32 | $+1$ | $\mathbb{Z}/(2r) \times \mathbb{Z}/2$ | $0$ halvings, $2$ degree-$2$ pairings ||
| bls24-315 | 8 | 22 | $-1$ | $\mathbb{Z}/(8r)$ | $0$ halvings, $1$ degree-$8$ pairing |
| bls24-317 | 8 | 60 | $-1$ | $\mathbb{Z}/(8r)$ | $0$ halvings, $1$ degree-$8$ pairing |
| bw6-633 | 8 | 20 | $-1$ | $\mathbb{Z}/(8r)$ | $0$ halvings, $1$ degree-$8$ pairing |
| bw6-761 | 8 | 46 | $-1$ | $\mathbb{Z}/(8r)$ | $0$ halvings, $1$ degree-$8$ pairing 

## 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