About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ANTS 2020
Conference paper
Faster computation of isogenies of large prime degree
Abstract
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.