A Subexponential Algorithm for Evaluating Large Degree Isogenies

Details A Subexponential Algorithm for Evaluating Large Degree Isogenies A Subexponential Algorithm for Evaluating Large Degree Isogenies

2010-02-23

arxiv.org/abs/1002.4228v2

Mathematics

Number Theory

Final version, to appear in ANTS IX

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

A Subexponential Algorithm for Evaluating Large Degree Isogenies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Subexponential Algorithm for Evaluating Large Degree Isogenies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Subexponential Algorithm for Evaluating Large Degree Isogenies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-169311