The j-invariant is a value used to identify an elliptic curve’s isomorphism class. Curves with the same j-invariant are isomorphic and have the same number of points. Its practical role is to turn selected pairing parameters into concrete curve coefficients: after obtaining j, compute a curve equation rather than searching blindly through coefficients. section 14.1 section 14.7
For pairing-friendly curve construction, begin with a field prime q, trace of Frobenius t, and discriminant D, related by D y² = 4q − t². The cardinality relation is #E = q + 1 − t = h·r. Complex multiplication uses q and D to obtain roots of a polynomial; those roots are j-invariants for curves matching the selected parameters. section 14.1 section 14.2
A Hilbert class polynomial supplies the candidate values. Written H(x) = ∏ᵢ(x − jᵢ), each root jᵢ modulo q is a possible j-invariant. Factor the polynomial recursively: solve degree-1 and degree-2 factors directly, and split higher-degree factors with modular polynomial operations until their roots are available. section 14.4 section 14.5.2
From a root to a candidate curve
Given a root j, compute c = j/(1728 − j), then form y² = x³ + 3cx + 2c. Thus a₄ = 3c and a₆ = 2c. Test each candidate using #E = q + 1 − t: multiplying a random curve point by #E must produce the point at infinity. If candidates fail, compute and test a twist by changing the coefficients. section 14.3 section 14.5.2
An implementation-oriented workflow is:
- Accept the discriminant, prime q, and trace t; select the matching Hilbert class polynomial. section 14.5.2
- Factor the polynomial modulo q and collect every root as a candidate j-invariant. section 14.4
- Convert each root into a₄ and a₆, then test the claimed cardinality with a random point. section 14.5.2
- When no direct candidate passes, construct and verify a twist of the first attempted curve. section 14.5.2
Figure 14.1 Pairing-friendly curves algorithm. Above the dashed line is one program that searches for good parameters. Below the dashed line is a program that finds one curve for one set of parameters.
The flow separates parameter sweeping from curve finding: the latter factors a polynomial to obtain j-invariants, then derives curve coefficients. section 14.2
