Computing modular polynomials by deformation


Seminar AMAC: CASC

20/02/2024 - 13:30 Sabrina Kunzweiler (Inria Bordeaux & Institut de Mathématiques de Bordeaux) IMAG 106

The classical modular polynomial $\phi_\ell(X,Y) \in \mathbb{Z}[X,Y]$ parametrizes pairs of elliptic curves connected by an isogeny of degree $\ell$.
They play an important role in algorithmic number theory, and are used in many applications, for example in the SEA point counting algorithm.

In this talk, I present a new method for computing modular polynomials. It has the same asymptotic time complexity as the currently best known algorithms, but does not rely on any heuristics.
The main ideas of our algorithm are:  the embedding of $\ell$-isogenies in smooth-degree isogenies in higher dimension, and the computation of deformations of isogenies.

The talk is based on a joint work with Damien Robert.