Complex multiplication reverses the usual elliptic-curve computation. Point-counting algorithms begin with a curve and discover its Frobenius trace. The CM method begins with an imaginary quadratic order and arithmetic conditions on the trace, then constructs an elliptic curve whose endomorphism structure realises that data.
The bridge is the j-invariant. Elliptic curves with complex multiplication by an order of discriminant D have j-invariants that are algebraic integers. Their minimal polynomial over Q is the Hilbert class polynomial H_D(X). Reducing that polynomial modulo a finite-field prime can produce j-invariants of curves with the desired CM structure.
This is Guide 36 in the Bukit Timah Tutor Computational Number Theory series. It completes Batch 09 by connecting binary quadratic forms and class groups, Cornacchia norm equations, isogenies and ECPP.
1. Ordinary elliptic curves and imaginary quadratic orders
For an ordinary elliptic curve E over a finite field, the endomorphism ring over an algebraic closure is an order in an imaginary quadratic field.
Frobenius π satisfies
π²−tπ+q=0.
The discriminant of the order generated by π is
t²−4q<0.
Thus the same Frobenius discriminant that appeared in SEA now points toward imaginary quadratic arithmetic.
2. Orders and discriminants
An imaginary quadratic order has discriminant
D=f²D_K
where D_K is the fundamental discriminant of the maximal order and f is the conductor.
Different orders inside the same quadratic field can occur as elliptic-curve endomorphism rings.
The class number h(D) counts proper ideal classes of the order and also equals the degree of the corresponding Hilbert class polynomial.
3. CM j-invariants
Over C, an elliptic curve can be represented as a complex torus
C/Λ.
Usually the endomorphisms are only multiplication by ordinary integers.
A CM curve has additional endomorphisms coming from an imaginary quadratic order. The associated j-invariant is an algebraic integer.
Curves with the same j are isomorphic over an algebraic closure, although twists over a finite base field can be non-isomorphic over that field.
4. Hilbert class polynomial
For a negative discriminant D, define
H_D(X)=∏(X−j(τ_i))
over representatives τ_i of the ideal/form classes of the order.
The polynomial lies in Z[X] and has degree h(D).
Its roots are exactly the CM j-invariants for that order over C.
5. The simplest example: D=−4
The order Z[i] has discriminant −4 and class number one.
Its CM j-invariant is
j=1728.
Therefore
H_−4(X)=X−1728.
This degree-one case removes all class-polynomial ambiguity and is ideal for seeing the CM construction mechanism.
6. Reduce the class polynomial modulo 101
Take p=101.
Reduce the root:
1728 ≡11 (mod101).
So
H_−4(X) mod101 = X−11.
A curve over F101 with j-invariant11 is therefore a candidate reduction of a CM j=1728 curve.
7. Curves with j=1728
For characteristic not2 or3, a curve
E:y²=x³+Ax
with A≠0 has
j(E)=1728.
Thus over F101 we may choose
E:y²=x³+x.
Its j-invariant is the reduction of1728, namely11 in F101.
8. The trace norm equation
For CM discriminant D, Frobenius is represented by an algebraic integer whose norm is p and whose trace is t.
A common norm relation has the form
4p=t²−D v².
For D=−4 this becomes
4p=t²+4v².
With p=101:
404=t²+4v².
9. One solution gives t=2
Choose
t=2, v=10.
Then
2²+4·10²=4+400=404.
The corresponding point count is
#E(F101)=101+1−2=100.
Direct counting confirms that
E:y²=x³+x
has exactly100 F101-rational points.
10. Cornacchia appears inside CM
The equation
4p=t²+|D|v²
is a binary quadratic norm equation.
Cornacchia-style algorithms can solve such equations efficiently after an appropriate modular square root has been found.
Thus Guide31’s Euclidean descent is not an isolated classical trick: it is part of a modern elliptic-curve construction pipeline.
11. The CM construction pipeline
A simplified prime-field CM method is:
1. choose negative discriminant D 2. solve 4p=t²−Dv² for desired trace t 3. compute H_D(X) 4. find a root j of H_D mod p 5. construct an elliptic curve with that j 6. choose the correct twist 7. verify the curve order.
Each step has its own arithmetic cost and verification data.
12. Constructing a curve from j
If j is neither0 nor1728, one standard family uses a parameter derived from
k = j/(1728−j)
and constructs a curve with coefficients proportional to k.
Exact formulas vary by convention. The safe computational contract is to construct E and then recompute j(E) from its coefficients to verify the target.
The special values j=0 and1728 use simpler dedicated families.
13. Twists choose among related traces
A j-invariant does not uniquely determine an F_p-isomorphism class.
Quadratic, quartic or sextic twists can share the same j-invariant over an algebraic closure while having different point counts over F_p.
Therefore after constructing a curve with the desired j, one must select and verify the twist whose Frobenius trace is the intended t.
14. Worked twist contrast at j=1728
Over F101, both
E1:y²=x³+x E2:y²=x³+2x
have j=1728.
But their point counts differ:
#E1(F101)=100, t1=2 #E2(F101)=82, t2=20.
The same algebraic-closure j-invariant supports different finite-field twists and traces.
15. Both traces satisfy CM norm relations
For t=20:
404=20²+4·1²=400+4.
Thus the D=−4 norm equation admits both trace magnitudes2 and20 through different representations.
Twist selection determines which Frobenius conjugacy class is realised by a particular finite-field model.
16. Class number controls polynomial degree
When h(D)>1, H_D has several roots.
Each root corresponds to a different complex CM j-invariant associated with an ideal class. Modulo p, roots may split, merge through reduction phenomena or lie in extension fields depending on how p behaves in the ring class field.
Computational complexity rises rapidly because H_D coefficients can become enormous.
17. Why Hilbert class polynomials can be expensive
The coefficients of H_D grow roughly exponentially with √|D| in bit size.
For large class numbers, storing and manipulating the integer polynomial can dominate the CM construction.
Practical methods therefore use analytic approximation with rigorous rounding, Chinese-remainder reconstruction, p-adic methods or alternative class invariants with smaller coefficients.
18. Alternative class invariants
Weber functions and other modular functions can produce class polynomials with much smaller coefficients than the j-based Hilbert class polynomial.
After finding a root of the smaller class polynomial, a rational transformation recovers the corresponding j-invariant.
This changes representation, not the underlying CM order.
19. Binary quadratic forms compute the class group
Primitive reduced binary quadratic forms of discriminant D represent ideal classes of the imaginary quadratic order.
Thus the same reduced-form list from Guide17 determines the class number and provides the class-group structure controlling CM j-invariants.
Complex multiplication is one place where quadratic-form composition becomes an explicit elliptic-curve algorithmic tool.
20. Isogenies among CM curves
Ideal classes act on CM elliptic curves through isogenies.
Multiplying by an invertible ideal class corresponds to moving to an isogenous curve with the same endomorphism order.
This creates a class-group action on CM j-invariants and explains the close relationship among Hilbert class polynomials, isogeny graphs and ideal arithmetic.
21. Ordinary isogeny volcanoes and CM orders
Within an ordinary finite-field isogeny class, different vertices may have different endomorphism orders between Z[π] and the maximal order.
Small-degree isogenies move horizontally or vertically through this order lattice.
CM construction can target curves with specified endomorphism orders; volcano methods can then navigate or certify those orders.
22. CM and ECPP
Atkin–Morain ECPP uses CM to find elliptic curves over Z/NZ with candidate orders suitable for primality certificates.
The broad discovery route is:
choose D solve a CM norm equation construct a CM j-invariant modulo N build a curve / twist factor enough of its candidate order find a point satisfying the certificate criterion.
This is why ECPP depends simultaneously on quadratic forms, class polynomials, elliptic curves and integer factorisation.
23. CM and cryptographic curve generation
The CM method can construct curves with prescribed or nearly prescribed group order.
One may choose p and desired trace t so that
#E(F_p)=p+1−t
has the required factorisation pattern, then search for a discriminant D satisfying the norm equation.
After construction, the final curve should still undergo independent parameter validation and subgroup checks.
24. Verifying H_D rather than trusting a file
A stored class polynomial is high-value mathematical data. A corrupted coefficient can construct the wrong object.
Verification options include checking known discriminant/class-number data, independent CRT reconstruction, evaluating CM relations numerically with certified precision or using modern polynomial-recognition routines.
For small D, direct tables and symbolic checks are easy.
25. The D=−4 verification receipt
For the worked example retain:
D=−4 h(D)=1 H_D(X)=X−1728 p=101 j=1728 mod101=11 E:y²=x³+x t=2 #E(F101)=100 4p=t²−Dv² with v=10.
Every line can be checked independently.
26. Common mistakes
1. Confusing the Frobenius discriminant t²−4p with the chosen order discriminant D when the order has nontrivial conductor. 2. Assuming one j determines one finite-field curve. 3. Forgetting twist selection.
4. Assuming every root of H_D lies in F_p. 5. Treating a numerical approximation of H_D coefficients as exact without certified rounding. 6. Assuming Z[π] always equals the full endomorphism ring. 7. Ignoring special j=0 and1728 automorphisms/twists. 8. Skipping the final point-count or order verification.
27. Practice set
1. What type of ring is the endomorphism ring of an ordinary elliptic curve over a finite field? 2. What is the degree of H_D? 3. State H_−4. 4. Reduce1728 modulo101.
5. Give a curve over F101 with j=1728. 6. State the D=−4 trace norm equation for p=101. 7. Verify t=2,v=10. 8. Compute the point count from t=2.
9. Why is Cornacchia relevant? 10. Why are twists necessary? 11. Give the point count of y²=x³+2x over F101 from the worked example. 12. What does the class group control in CM theory?
28. Answers
1. An order in an imaginary quadratic field for an ordinary curve. 2. h(D). 3. X−1728. 4. 11.
5. y²=x³+x. 6. 404=t²+4v². 7. 4+400=404. 8. 100.
9. It solves the quadratic norm-form equation used to obtain CM trace data. 10. The same j can have several finite-field forms with different traces. 11. 82. 12. CM ideal classes/j-invariants and the isogeny action among them.
Sources and further study
SageMath’s Complex multiplication for elliptic curves documentation exposes Hilbert class polynomial and CM j-invariant computation. Standard references include David Cox’s treatment of primes, forms and imaginary quadratic class fields, and algorithmic treatments in computational algebraic number theory.
Computational Number Theory — Batch 09
Guide 33: Schoof’s Algorithm, Frobenius Traces and Elliptic-Curve Point Counting
Guide 34: Schoof–Elkies–Atkin, Elkies/Atkin Primes and Modular Polynomials
Guide 35: Elliptic-Curve Isogenies, Vélu Formulas and Isogeny Graphs
Guide 36: Complex Multiplication, Hilbert Class Polynomials and CM Curve Construction