2010/01/01 by David Jao, Vladimir Soukharev · 1 citation
Computer Science · Mathematics · #Algebraic Geometry and Number Theory #Coding theory and cryptography #Cryptography and Residue Arithmetic #math.NT #msc:11Y16
paper · pdf · doi:10.1007/978-3-642-14518-6_19
published as ANTS-IX, LNCS 6197, pp. 219-233, 2010 · Final version, to appear in ANTS IX
openalex publication_date 2010/01/01 · arxiv created 2010/04/13 · arxiv updated 2014/02/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
An isogeny between elliptic curves is an algebraic morphism which is a group homomorphism. Many applications in cryptography require evaluating large degree isogenies between elliptic curves efficiently. For ordinary curves of the same endomorphism ring, the previous best known algorithm has a worst case running time which is exponential in the length of the input. In this paper we show this problem can be solved in subexponential time under reasonable heuristics. Our approach is based on factoring the ideal corresponding to the kernel of the isogeny, modulo principal ideals, into a product of smaller prime ideals for which the isogenies can be computed directly. Combined with previous work of Bostan et al., our algorithm yields equations for large degree isogenies in quasi-optimal time given only the starting curve and the kernel.