Computing modular polynomials by deformation

Abstract

We present an unconditional CRT algorithm to compute the modular polynomial $\hat{I}{¦}_{\ell }(X,Y)$ in quasi-linear time. The main ingredients of our algorithm are: the embedding of $\ell$-isogenies in smooth-degree isogenies in higher dimension, and the computation of $m$-th order deformations of isogenies. We provide a proof-of-concept implementation of a heuristic version of the algorithm demonstrating the practicality of our approach. Our algorithm can also be used to compute the reduction of $\hat{I}{¦}_{\ell }$ modulo $p$ in quasi-linear time (with respect to $\ell$) $\tilde{O}({\ell }^2(\log p+\log \ell {)}^{\mathfrak{O}})$.

accepted for presentation at the Sixteenth Algorithmic Number Theory Symposium (ANTS XVI)