Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

An isogeny between elliptic curves is an algebraic morphism which is simultaneously a group homomorphism. As such, isogenies play the role of morphisms in the category of elliptic curves. For elliptic curves themselves, many efficient algorithms have been developed for handling computations on curves and on points, but progress on the corresponding algorithms for handling isogenies have lagged behind. In this work we present the first ever subexponential time algorithm for evaluating isogenies of a given degree on an elliptic curve, improving on the cubic exponential time of the previous best method. As is common with subexponential algorithms, our algorithm is conditional on certain heuristic assumptions and technical conditions, which we will present, along with an explanation of why they hold in most cases. Time permitting, we will also present applications to elliptic curve cryptography and the discrete logarithm problem. No knowledge of cryptography or algebraic geometry is assumed.

Joint work with Vladimir Soukharev.