A Hilbert class polynomial packages the possible j-invariants needed by complex multiplication into one polynomial. For a selected discriminant, reduce and factor that polynomial modulo the field prime q; each root is a candidate j-invariant for an elliptic curve over that field. section 14.3 section 14.4
Write the polynomial as H(x)=∏ᵢ(x−jᵢ). Its factors are unique, and each root jᵢ can lead to a curve with the desired prime field and large prime factor for pairings. Different moduli produce different factorization results, even when the discriminant is unchanged. section 14.4 section 14.5.2
Equation 14.5
\[H(x)=\prod_i (x-j_i) \label{edq4}\]This product form makes the operational goal explicit: factor H(x) modulo q until the individual j-invariant roots are available. section 14.4
Root finding is recursive. Given P(x), first compute h(x)=xᵖ mod P(x), then take gcd(h(x)−x,P(x)) to isolate factors containing roots modulo p. Split larger factors repeatedly; solve degree-1 factors directly and degree-2 factors with the quadratic formula modulo q. A zero constant term identifies a root of zero and permits division by x before continuing. section 14.4 section 14.5.2
Turn roots into a verified curve with this flow:
- Read the polynomial associated with the selected discriminant, then factor it modulo q to collect all roots. section 14.5.2
- For each root j, compute c=j/(1728−j), then form y²=x³+3cx+2c. section 14.3 section 14.5.2
- Compute the target cardinality q+1−t and multiply a random curve point by it; the point at infinity accepts the candidate. section 14.5.2 section 14.7
- If no candidate passes, choose a quadratic nonresidue f and test the twist y²=x³+3cf²x+2cf³. section 14.3 section 14.5.2
Degree-one and degree-two handling
A monic degree-one Hilbert polynomial yields its root as the negative constant coefficient. For a degree-two polynomial, normalize it to monic form, compute the discriminant, take its modular square root, and divide the two signed numerators by 2. Higher-degree inputs enter the recursive splitting loop instead. section 14.5.2 section 14.4
A root is not by itself proof that the resulting curve has the required cardinality: the sign choice in the trace can select the wrong curve. Testing candidate curves and then their twist resolves that ambiguity. Curves with the same j-invariant are isomorphic, while the discriminant selects the Hilbert class polynomial used to obtain j. section 14.3 section 14.7
