Fast subgroup checks used by EIP-2537
Fast subgroup checks used by EIP-2537
Fields and Groups
Field Fp is defined as the finite field of size p with elements represented as integers between 0 and p-1 (both inclusive).
Field Fp2 is defined as Fp[X]/(X^2-nr2) with elements el = c0 + c1 * v, where v is the formal square root of nr2 represented as integer pairs (c0,c1).
Group G1 is defined as a set of Fp pairs (points) (x,y) such that either (x,y) is (0,0) or x,y satisfy the curve Fp equation.
Group G2 is defined as a set of Fp2 pairs (points) (x', y') such that either (x', y') is (0,0) or (x', y') satisfy the curve Fp2 equation.
Curve parameters
The set of parameters used by fast subgroup checks:
|x| (seed) = 15132376222941642752
x is negative = true
Cube root of unity modulo p - Beta = 793479390729215512621379701633421447060886740281060493010456487427281649075476305620758731620350
r = 4002409555221667392624310435006688643935503118305586438271171395842971157480381377015405980053539358417135540939437 * v
s = 2973677408986561043442465346520108879172042883009249989176415018091420807192182638567116318576472649347015917690530 + 1028732146235106349975324479215795277384839936929757896155643118032610843298655225875571310552543014690878354869257 * v
Helper function to compute the conjugate over Fp2 - conjugate
conjugate(c0 + c1 * v) := c0 - c1 * v
G1 endomorphism - phi
The endomorphism phi transform the point from (x,y) to (Beta*x,y) where Beta is a precomputed cube root of unity modulo p given above in parameters sections:
phi((x,y)) := (Beta*x,y)
G2 endomorphism - psi
psi((x,y)) := (conjugate(x)*r,conjugate(y)*s)
The G1 case
Before accepting a point P as input that purports to be a member of G1 subject the input to the following endomorphism test: phi(P) + x^2*P = 0
The G2 case
Before accepting a point P as input that purports to be a member of G2 subject the input to the following endomorphism test: psi(P) + x*P = 0
Resources
- https://eprint.iacr.org/2021/1130.pdf, sec.4
- https://eprint.iacr.org/2022/352.pdf, sec. 4.2