Evaluating isogenies on elliptic curves in subexponential timeAlgebra & Discrete Mathematics
|Speaker:||David Jao, University of Waterloo|
|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.