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) O (² (p +) ^O).