Geometric construction of modular polynomials with level structures
Hiroshi Onuki, Yukihiro Uchida, Ryo Yoshizumi · 2026
Read Geometric construction of modular polynomials with level structures by Hiroshi Onuki, Yukihiro Uchida, Ryo Yoshizumi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-17338.txt.
Introduction
Hiroshi Onuki, Yukihiro Uchida, and Ryo Yoshizumi build modular polynomials with level structures. The classic modular polynomial links two elliptic curves joined by an isogeny. It has wide use in computational number theory. Point counting on curves is one such use. Computing the polynomial itself is a hard task in its own right.
The authors give a geometric construction for the level case. Level structures add data that many modern algorithms need. A clean construction can make those algorithms faster and safer. Curve-based cryptography rests on such tools. So does research on curve families. The work adds a firm base for both.
Catalog record
| CREATOR | Hiroshi Onuki, Yukihiro Uchida, Ryo Yoshizumi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 74 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-17338
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Geometric construction of modular polynomials with level structures Thanks: Authors are listed in alphabetical order; see https://www.ams.org/profession/leaders/culture/JointResearchandItsPublicationfinal.pdf . The authors would like to thank Yuya Murakami for helpful correspondence regarding an issue in the proof of [ 22 , Proposition 2.12] , and for confirming that the argument can be corrected. The first author was supported by JST K Program Grant Number JPMJKP24U2, Japan. The second author was supported by JSPS KAKENHI Grant Number JP24K21512. The third author was supported by WISE program (MEXT) at Kyushu University. Hiroshi Onuki, Yukihiro Uchida, Ryo Yoshizumi Abstract . The classical modular polynomial for j j -invariants describes the relation between two elliptic curves connected by isogenies. This polynomial has been applied to various algorithms in computational number theory, such as point counting on elliptic curves. In addition, computing the modular polynomial itself is also an important problem, and various algorithms to compute it have been proposed. On the other hand, modular polynomials for other invariants of higher level structures have also been studied. For example, the modular polynomials for the Legendre λ \lambda -invariant and the Weber functions are well-known. In this paper, we give another approach to construct modular polynomials of higher level purely algebraically. In particular, we show the existence of modular polynomials for invariants directly related to models of elliptic curves, such as the coefficients of Montgomery and Hessian curves. We also show that these modular polynomials have integer coefficients and are symmetric and irreducible in certain cases, and give an algorithm to compute them, which is based on the deformation method by Kunzweiler and Robert. 2010 Mathematics Subject Classification Primary 14H52; Secondary 11G20, 11Y16 1. Introduction For a positive integer m , the classical modular polynomial \Phi_{m}(X,Y)\in\mathbb{Z}[X,Y] is a polynomial that describes the relation between two m -isogenous j -invariants. More precisely, for \tau in the upper half plane \mathbb{H} of the complex number field, we denote by E_{\tau} the elliptic curve over \mathbb{C} defined by \mathbb{C}/(\mathbb{Z}+\mathbb{Z}\tau) , and by j(\tau) the j -invariant of E_{\tau} . Then, we have \Phi_{m}(j(\tau),j(\tau^{\prime}))=0 if and only if there exists a cyclic isogeny of degree m between the elliptic curves E_{\tau} and E_{\tau^{\prime}} . The polynomial \Phi_{m}(X,Y) is symmetric, i.e., \Phi_{m}(X,Y)=\Phi_{m}(Y,X) , and monic of degree \psi(m) in both X and Y , where \psi is the Dedekind function, i.e., \psi(m)=m\prod_{p\mid m}\left(1+\frac{1}{p}\right) with the product over all prime divisors p of m . 1.1. Algorithms for computing modular polynomials Computing the classical modular polynomials is a well-studied problem. The algorithms to compute them include a method using Fourier expansion [ 11 ] and a method using isogenies between supersingular elliptic curves with the Chinese Remainder Theorem (CRT) [ 7 ] . Enge [ 12 ] provides an algorithm in O(\ell^{3}(\log\ell)^{4+\epsilon}) using interpolation and floating-point evaluation under some heuristics. However, this algorithm needs an excessive amount of memory for large \ell . Then, Bröker, Lauter, and Sutherland [ 3 ] provided an algorithm in O(\ell^{3}\log^{3}\ell\log\log\ell) using isogeny volcanoes with the CRT method under Generalized Riemann Hypothesis (GRH), which requires a practical amount of memory. Recently, Kunzweiler and Robert [ 16 ] proposed an algorithm in the same complexity without GRH. Their algorithm also uses the CRT method, and is based on the deformation theory and a higher dimensional representation of isogenies between elliptic curves based on Kani’s work [ 15 ] , developed by [ 6 , 19 , 26 ] . 1.2. Modular polynomials of higher level Another characterization of the classical modular polynomial is that \Phi_{m}(X,j(\tau)) is the minimal polynomial of j(m\tau) over \mathbb{Q}(j(\tau)) for \tau\in\mathbb{H} such that j(\tau) is transcendental over \mathbb{Q} . Note that E_{m\tau} is the codomain of the isogeny defined by z\mapsto mz , whose kernel is the cyclic subgroup of order m generated by \frac{1}{m} in E_{\tau} . This characterization allows us to define modular polynomials of higher level as follows: Let f be a modular function for a congruence subgroup \Gamma of level N in \mathrm{SL}_{2}(\mathbb{Z}) , and let \tau be an element in \mathbb{H} such that f(\tau) is a transcendental number. Let m be a positive integer prime to N , and \Phi^{\prime}(X) be the minimal polynomial of f(m\tau) over \mathbb{Q}(f(\tau)) . Then, we define the modular polynomial of order m for f to be the polynomial \Phi_{m}^{f}(X,Y)\in\mathbb{Q}[X,Y] obtained by replacing f(\tau) by Y in \Phi^{\prime}(X) , and denote it by \Phi_{m}^{f}(X,Y) . For example, it is known that there exist the modular polynomials for the Weber function and the Legendre \lambda -invariant (see [ 5 , 3 ] and [ 2 , Chap. 4.4] for example). As mentioned in [ 3 ] , if the Fourier expansion of f has integer coefficients then \Phi_{m}^{f}(X,Y) has integer coefficients. In addition, the modular polynomial \Phi_{\ell}^{f}(X,Y) for a prime \ell\nmid N is symmetric if f is invariant under the action of certain matrices [ 5 , Lemma 5.5] . 1.3. Geometric viewpoint of modular polynomials of higher level From geometric viewpoints, the modular polynomial \Phi_{m}^{f}(X,Y) describes the relation between isomorphism classes of enhanced elliptic curves of level \Gamma connected by isogenies of degree m which preserve the level structure. By observing the images of \tau/N and 1/N under the isogeny E_{\tau}\to E_{m\tau} , we can define isogenies between enhanced elliptic curves as follows: • An enhanced elliptic curve of level \Gamma(N) is a pair (E,(P,Q)) of an elliptic curve E over \mathbb{C} and a basis (P,Q) of the N -torsion subgroup E[N] of E such that e_{N}(P,Q)=e^{2\pi i/N} , where e_{N} is the Weil pairing on E[N] . An isogeny of degree m between enhanced elliptic curves (E,(P,Q)) and (E^{\prime},(P^{\prime},Q^{\prime})) of level \Gamma(N) is an isogeny \varphi:E\to E^{\prime} of degree m such that \varphi(P)=[m]P^{\prime} and \varphi(Q)=Q^{\prime} . • An enhanced elliptic curve of level \Gamma_{1}(N) is a pair (E,P) of an elliptic curve E over \mathbb{C} and a point P\in E[N] of order N . An isogeny of degree m between enhanced elliptic curves (E,P) and (E^{\prime},P^{\prime}) of level \Gamma_{1}(N) is an isogeny \varphi:E\to E^{\prime} of degree m such that \varphi(P)=P^{\prime} . • An enhanced elliptic curve of level \Gamma_{0}(N) is a pair (E,C) of an elliptic curve E over \mathbb{C} and a cyclic subgroup C of E[N] of order N . An isogeny of degree m between enhanced elliptic curves (E,C) and (E^{\prime},C^{\prime}) of level \Gamma_{0}(N) is an isogeny \varphi:E\to E^{\prime} of degree m such that \varphi(C)=C^{\prime} . To simplify the notation, we denote by (E,\ast) an enhanced elliptic curve of level \Gamma , where \Gamma is one of \Gamma(N) , \Gamma_{1}(N) , and \Gamma_{0}(N) if we do not need to specify the level structure. The main target of this paper is (geometric) modular polynomials of higher level, which we define as follows: Definition 1.1 . Let \Gamma be \Gamma(N) , \Gamma_{1}(N) , or \Gamma_{0}(N) , let f be an embedding from the set of isomorphism classes of enhanced elliptic curves of level \Gamma to \mathbb{C} , and m be a positive integer prime to N . A modular polynomial of order m for f is the polynomial \Phi_{m}^{f}(X,Y)\in\mathbb{C}[X,Y] such that • \Phi_{m}^{f}(f(E,\ast),f(E^{\prime},\ast))=0 if and only if there exists a cyclic isogeny of degree m between the enhanced elliptic curves (E,\ast) and (E^{\prime},\ast) , •