UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Evaluating isogenies on elliptic curves in subexponential time

Algebra & Discrete Mathematics

Speaker: David Jao, University of Waterloo
Location: 1147 MSB
Start time: Fri, Feb 26 2010, 1:10PM

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.