Computing modular polynomials by deformation

We present an unconditional CRT algorithm to compute the modular polynomial Φ₍X,Y) in quasi-linear time. The main ingredients of our algorithm are: the embedding of -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 Φ_ modulo p in quasi-linear time (with respect to ) Õ(²(log p + log )O).