Computing modular polynomials by deformation

We present an unconditional CRT algorithm to compute the modular polynomial \(\Phi _\ell (X,Y)\) ${\mathrm{\Phi }}_{\ell }(X,Y)$ in quasi-linear time. The main ingredients of our algorithm are: the embedding of \(\ell \) $\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 \(\Phi _{\ell }\) ${\mathrm{\Phi }}_{\ell }$ modulo p in quasi-linear time (with respect to \(\ell \) $\ell$ ) \(\tilde{O}(\ell ^2 (\log p + \log \ell )^{\mathfrak {O}})\) $\tilde{O}({\ell }^2{(logp+log\ell )}^{\mathfrak{O}})$ .