Elliptic Curves
Modular Equations and the j-Invariant
Modular functions, modular equations relating j-invariants of isogenous curves, and their use in locating isogenies.
Engineering / MathematicsElliptic Curves2 min readKV-MATH-0640
The j-invariant is a modular function on the upper half plane. Modular equations relate the j-invariants of isogenous curves, which turns isogeny-finding into root-finding.
The j-function
Viewing a lattice as normalised with one period equal to one, the j-invariant becomes a function of the other period, which lies in the upper half plane. That function is invariant under the modular group.
Modular polynomials
For each level, a two-variable polynomial with integer coefficients vanishes exactly on pairs of j-invariants of curves related by an isogeny of that degree.
| Level | Degree in each variable | Coefficient size |
|---|---|---|
| 2 | 3 | Small |
| 3 | 4 | Modest |
| Larger primes | One more than the level | Grows very rapidly |
Using them
Finding isogenies via modular polynomials
- Fix a curveCompute its j-invariant.
- SubstituteSubstitute into the modular polynomial, giving a one-variable polynomial.
- Find rootsIts roots are the j-invariants of the isogenous curves.
- ConstructBuild each isogenous curve from its j-invariant and recover the isogeny.
Applications
Point counting
The SEA improvements to Schoof's algorithm use modular polynomials to work with small-degree factors of division polynomials.
Primality proving
Atkin's variant uses modular equations to obtain class invariants with small coefficients — see ECPP.
Isogeny graphs
Repeated application maps out the graph of curves connected by small isogenies.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 7.2.5. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.