🔢 mathematics

Geometric construction of modular polynomials with level structures

This paper presents a purely algebraic approach to constructing modular polynomials for higher-level invariants directly related to elliptic curve models (such as Montgomery and Hessian curves), proving their integer coefficients and symmetry while providing an algorithm based on the deformation method to compute them.

Original authors: Hiroshi Onuki, Yukihiro Uchida, Ryo Yoshizumi

Published 2026-01-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hiroshi Onuki, Yukihiro Uchida, Ryo Yoshizumi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master architect working with a very special kind of building: Elliptic Curves. These aren't buildings you can walk into; they are complex mathematical shapes that look like twisted loops. For a long time, mathematicians have had a "blueprint" called the Modular Polynomial. Think of this blueprint as a giant rulebook that tells you exactly how two of these curves are connected. If Curve A and Curve B are linked by a specific type of bridge (called an isogeny), this rulebook has a formula that says, "If you plug in the coordinates of A, you must get the coordinates of B."

For decades, this rulebook only existed for the most famous version of these curves, known as the j-invariant. But mathematicians knew there were other ways to describe these curves—like the Montgomery and Hessian forms—which are popular in modern cryptography because they are faster to compute. The problem? No one had a rulebook for these specific forms.

This paper, written by Onuki, Uchida, and Yoshizumi, is like a construction crew finally building those missing rulebooks. Here is how they did it, explained simply:

1. The Problem: Missing Blueprints

Imagine you have a set of Lego instructions for a standard castle (the classical curves). You also have a different set of instructions for a futuristic spaceship (Montgomery curves) and a sleek skyscraper (Hessian curves). You know the spaceships and skyscrapers are connected to the castles by bridges, but you don't have the specific instructions on how to translate a spaceship's design into a skyscraper's design using those bridges.

The authors wanted to create the "translation rulebooks" (modular polynomials) specifically for these spaceship and skyscraper designs.

2. The Solution: A New Way to Build

Usually, to build these rulebooks, mathematicians use heavy machinery from a field called "Modular Forms" (think of this as using a high-tech 3D printer that requires a PhD in physics to operate).

The authors took a different approach. They used pure algebra, which is more like using a hammer and a saw. They didn't need the fancy 3D printer. Instead, they looked at the specific "ingredients" (coefficients) that define these curves and asked: "If I have a bridge connecting two of these shapes, can I write a simple equation that links their ingredients?"

They proved that:

Yes, the rulebooks exist.
They are clean: The numbers in these rulebooks are whole integers (no messy fractions).
They are symmetrical: If you swap the two curves in the equation, the rule still works (like a two-way bridge).
They are unique: There is only one correct rulebook for each type of bridge.

3. The "Good Model" Concept

To make this work, the authors introduced a concept they call a "Good Model."

Imagine you are trying to describe a car. You could describe it by its engine size, its color, or its license plate. But to build a rulebook for how cars connect, you need a description that makes it easy to see how the parts move.

A "Good Model" is a specific way of describing the curve (like using the "x-coordinate" for Montgomery curves or a special "t-coordinate" for Hessian curves) that comes with a built-in manual.
This manual tells you exactly how to:
- Multiply points on the curve (Scalar Multiplication).
- Find points that act like "zero" (Division Polynomials).
- Build the bridges between curves (Isogeny Formulas).

The authors showed that for Montgomery and Hessian curves, these "Good Models" exist. Because they have these manuals, they could mathematically prove the rulebooks (polynomials) must exist and have nice properties.

4. The Construction Method (The Algorithm)

Once they proved the rulebooks could exist, they needed to actually write them down. They couldn't just guess; the numbers are huge.

They used a clever trick based on deformation theory. Imagine you have a clay model of a curve.

You take a tiny, almost invisible amount of "magic dust" (a mathematical variable called $\epsilon$ ) and mix it into the clay.
You stretch the clay slightly (deforming it).
You build a bridge between the original clay and the stretched clay.
By watching how the bridge changes as you add more dust, you can reverse-engineer the entire rulebook.

They did this on a computer using a method called the Chinese Remainder Theorem. Think of this as building a giant puzzle. Instead of trying to solve the whole puzzle at once (which would take too much memory), they solved small pieces of the puzzle in different "worlds" (different prime numbers) and then stitched the pieces together to form the complete, massive rulebook.

5. What They Actually Found

The authors didn't just say "it's possible." They actually built the rulebooks for:

Montgomery Curves: Used widely in secure communications (like the Curve25519).
Hessian Curves: Another efficient shape for cryptography.

They wrote a computer program to generate these polynomials for various sizes of bridges (prime numbers). They tested the results and confirmed that the rulebooks work perfectly: if you use them to build a bridge, the bridge actually connects the curves as predicted.

Summary

In short, this paper is about democratizing the blueprints.

Before: We had a master rulebook for one type of curve, but the popular "Montgomery" and "Hessian" types were left out in the cold, with no clear way to link them mathematically.
Now: The authors built a new, purely algebraic method to generate the rulebooks for these specific curves. They proved these rulebooks are mathematically sound (integers, symmetric) and provided a fast computer algorithm to create them.

They didn't invent new curves or change how cryptography works; they simply filled in the missing pages of the instruction manual that mathematicians and cryptographers had been looking for.

Technical Summary: Geometric Construction of Modular Polynomials with Level Structures

Problem Statement
The classical modular polynomial $\Phi_m(X, Y)$ describes the algebraic relation between $j$ -invariants of two elliptic curves connected by a cyclic isogeny of degree $m$ . While algorithms exist to compute these polynomials (e.g., via Fourier expansion, supersingular isogenies, or deformation theory), there is a need to extend this framework to "higher level" structures. Specifically, the paper addresses the construction of modular polynomials for invariants associated with specific models of elliptic curves, such as Montgomery and Hessian curves, which correspond to enhanced elliptic curves with level structures $\Gamma_0(4)$ and $\Gamma(3)$ , respectively. Prior to this work, the existence of such modular polynomials for these specific forms was not rigorously proven in the literature, nor was a purely algebraic construction method established without relying on the theory of modular forms.

Methodology
The authors propose a purely algebraic approach to construct modular polynomials for invariants of higher level. The methodology relies on the following core concepts:

Invariants and Good Models: The authors define an "invariant of level $\Gamma$ " as an injection from the set of isomorphism classes of enhanced elliptic curves to $\mathbb{C}$ , accompanied by a rational function relating the invariant to the $j$ -invariant. Crucially, they introduce the concept of a "good model," which requires the existence of explicit formulas for:
- Scalar multiplication ( $[m]P$ ).
- Division polynomials (identifying points of order $m$ ).
- Isogeny formulas (computing the target curve's invariant from the source curve and the kernel generator).
  These formulas must have coefficients in specific rings (e.g., $\mathbb{Z}[X]$ or $\mathbb{Z}[1/m][X]$ ) to ensure integrality.
Existence Proof via Deformation Theory: To prove the existence of the modular polynomial $\Phi^\alpha_m(X, Y)$ for an invariant $\alpha$ , the authors utilize deformation theory (specifically the Kunzweiler–Robert framework). They consider the minimal splitting field of the division polynomial over a rational function field. By analyzing the action of the Galois group on the roots of the division polynomial (which correspond to cyclic subgroups), they construct a polynomial whose roots are the invariants of the target curves connected by isogenies.
Algorithmic Construction: The paper adapts the Kunzweiler–Robert algorithm for computing classical modular polynomials. The algorithm operates over finite fields $\mathbb{F}_{p^2}$ and uses the Chinese Remainder Theorem (CRT) to lift results to $\mathbb{Z}[X, Y]$ .
- It selects primes $p$ such that the curve has complex multiplication properties allowing for efficient isogeny computation.
- It deforms the curve and the invariant over an Artinian ring $R = \mathbb{F}_{p^2}[\epsilon]/(\epsilon^{\ell+2})$ .
- It computes isogenies and lifts the target invariant $\alpha(E', P')$ using Newton iteration (Hensel lifting), ensuring the lifted invariant satisfies the defining rational function of the model.

Key Contributions

Existence and Properties: The paper proves that for any invariant $\alpha$ possessing a "good model" (satisfying specific integrality and formula conditions), the modular polynomial $\Phi^\alpha_m(X, Y)$ exists, has integer coefficients, and is monic of degree $\psi(m)$ in $Y$ .
Symmetry and Irreducibility:
- The polynomial is shown to be symmetric ( $\Phi^\alpha_m(X, Y) = \Phi^\alpha_m(Y, X)$ ) if $m > 1$ and either the level is $\Gamma_0(N)$ or $m \equiv \pm 1 \pmod N$ .
- If the invariant is "computable" (expressible as a rational function of the $j$ -invariant and level structure coordinates independent of the specific curve), the polynomial is irreducible over $\mathbb{C}(X)$ .
Specific Examples: The authors demonstrate that the coefficient $A$ of Montgomery curves (level $\Gamma_0(4)$ ) and the coefficient $d$ of Hessian curves (level $\Gamma(3)$ ) satisfy the conditions of a good model. Consequently, modular polynomials for these coefficients exist and possess the stated properties.
Congruence Properties: The paper establishes congruence conditions for the coefficients of these polynomials. For Montgomery curves, the coefficient of $X^i Y^j$ is zero unless $i+j \equiv 0 \pmod 2$ . For Hessian curves, similar modular constraints apply based on $m \pmod 3$ .
Algorithm Implementation: An algorithm is provided to compute these polynomials with a complexity of $\tilde{O}(\ell^3 \log^3 \ell \log \log \ell)$ bit operations, matching the efficiency of the best-known algorithms for classical modular polynomials.

Results

The authors implemented the algorithm in SageMath and computed modular polynomials for Montgomery and Hessian curves for all primes $\ell < 150$ .
Experimental results confirmed that the computed polynomials satisfy the isogeny conditions on finite fields.
The experiments verified the symmetry and specific congruence properties of the coefficients.
The logarithmic height of the computed polynomials generally adhered to a conjectured bound related to the classical case, with minor exceptions for small primes in the Hessian case.
The study of the permutation $\sigma$ (related to the evaluation of the polynomial at points outside the image of the invariant) showed that for Montgomery curves, $\sigma$ is the identity, while for Hessian curves, it is a non-trivial permutation.

Significance and Claims
The authors explicitly state that their primary contribution is providing another approach to construct modular polynomials of higher level that is purely algebraic and does not rely on the theory of modular forms. They do not claim that the examples (Montgomery/Hessian coefficients) are not modular functions; rather, they assert that their algebraic method offers a distinct and potentially useful pathway to construct modular polynomials for other forms of elliptic curves where modular form theory might be difficult to apply or where explicit formulas for scalar multiplication and isogenies are known but the modular nature is not immediately obvious.

The paper emphasizes that the existence of these polynomials was previously unproven in the literature for these specific curve forms. By establishing the "good model" criteria, the authors provide a general framework to verify the existence and integrality of modular polynomials for a broader class of elliptic curve models.