Modular polynomials for elliptic curves

For a positive integer $\ell$, the classical modular polynomial ${\mathrm{\Phi }}_{\ell }\in \mathbf{Z}[X,Y]$ is characterized by the property that its zero set is exactly the set of pairs of $j$-invariants connected by a cyclic $\ell$-isogeny.

AUTHORS:

• Lorenz Panny (2023)

sage.schemes.elliptic_curves.mod_poly.classical_modular_polynomial(l, j=None)

Return the classical modular polynomial ${\mathrm{\Phi }}_{\ell }$, either as a “generic” bivariate polynomial over $\mathbf{Z}$, or as an “instantiated” modular polynomial where one variable has been replaced by the given $j$-invariant.

Generic polynomials are cached up to a certain size of $\ell$, which significantly accelerates subsequent invocations with the same $\ell$. The default bound is $\ell \le 100$, which can be adjusted using classical_modular_polynomial.set_cache_bound() with a different value. Beware that modular polynomials are very big objects and the amount of memory consumed by the cache will grow rapidly when the bound is set to a large value.

INPUT:

• l – positive integer

• j – either None or a ring element:

  • if None is given, the original modular polynomial is returned as an element of $\mathbf{Z}[X,Y]$

  • if a ring element $j\in R$ is given, the evaluation ${\mathrm{\Phi }}_{\ell }(j,Y)$ is returned as an element of the univariate polynomial ring $R[Y]$

ALGORITHMS:

• The Kohel database ClassicalModularPolynomialDatabase

• pari:polmodular

EXAMPLES:

Sage

sage: classical_modular_polynomial(2)
-X^2*Y^2 + X^3 + 1488*X^2*Y + 1488*X*Y^2 + Y^3 - 162000*X^2 + 40773375*X*Y - 162000*Y^2 + 8748000000*X + 8748000000*Y - 157464000000000
sage: j = Mod(1728, 419)
sage: classical_modular_polynomial(3, j)
Y^4 + 230*Y^3 + 84*Y^2 + 118*Y + 329

Python

>>> from sage.all import *
>>> classical_modular_polynomial(Integer(2))
-X^2*Y^2 + X^3 + 1488*X^2*Y + 1488*X*Y^2 + Y^3 - 162000*X^2 + 40773375*X*Y - 162000*Y^2 + 8748000000*X + 8748000000*Y - 157464000000000
>>> j = Mod(Integer(1728), Integer(419))
>>> classical_modular_polynomial(Integer(3), j)
Y^4 + 230*Y^3 + 84*Y^2 + 118*Y + 329

Sage Live

classical_modular_polynomial(2)
j = Mod(1728, 419)
classical_modular_polynomial(3, j)

Increasing the cache size can be useful for repeated invocations:

Sage

sage: %timeit classical_modular_polynomial(101)                              # not tested
6.11 s ± 1.21 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit classical_modular_polynomial(101, GF(65537).random_element())  # not tested
5.43 s ± 2.71 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

sage: classical_modular_polynomial.set_cache_bound(150)                      # not tested
sage: %timeit classical_modular_polynomial(101)                              # not tested
The slowest run took 10.35 times longer than the fastest. This could mean that an intermediate result is being cached.
1.84 µs ± 1.84 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
sage: %timeit classical_modular_polynomial(101, GF(65537).random_element())  # not tested
59.8 ms ± 29.4 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Python

>>> from sage.all import *
>>> %timeit classical_modular_polynomial(Integer(101))                              # not tested
6.11 s ± 1.21 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit classical_modular_polynomial(Integer(101), GF(Integer(65537)).random_element())  # not tested
5.43 s ± 2.71 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>> classical_modular_polynomial.set_cache_bound(Integer(150))                      # not tested
>>> %timeit classical_modular_polynomial(Integer(101))                              # not tested
The slowest run took 10.35 times longer than the fastest. This could mean that an intermediate result is being cached.
1.84 µs ± 1.84 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit classical_modular_polynomial(Integer(101), GF(Integer(65537)).random_element())  # not tested
59.8 ms ± 29.4 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Sage Live

%timeit classical_modular_polynomial(101)                              # not tested
%timeit classical_modular_polynomial(101, GF(65537).random_element())  # not tested
classical_modular_polynomial.set_cache_bound(150)                      # not tested
%timeit classical_modular_polynomial(101)                              # not tested
%timeit classical_modular_polynomial(101, GF(65537).random_element())  # not tested

Make live