Faster computation of isogenies of large prime degree

Let E/𝔽_q be an elliptic curve, and P a point in E(𝔽_q) of prime order . Vélu's formulae let us compute a quotient curve E' = E/〈P〉 and rational maps defining a quotient isogeny ϕ : E → E' in Õ(ℓ) 𝔽_q-operations, where the Õ is uniform in q. This article shows how to compute E', and ϕ(Q) for Q in E(𝔽_q), using only Õ(√ℓ) 𝔽_q-operations, where the Õ is again uniform in q. As an application, this article speeds up some computations used in the isogeny-based cryptosystems CSIDH and CSURF.